Hey Guys
I need your help in solving http://www.codechef.com/problems/ARRAYTRM/
I’m not able to arrive at a straight logic to solve this problem.
I could only infer the following:
The difference of difference b/w the elements of chosen set and left-out elements could differ by k+1 after each operation.
I don’t know how to approach this problem. Would really appreciate any help, specially how to attacked the problem and used the intermediate inferences to reach to the logic.
@sanjayk You made the most important observation, that the difference between two elements can only ever be changed by a multiple of (k+1). So, taking the given values \bmod (k{+}1), only those in the same residue class can be zero at the same time. Thus we need at least n{-}1 of the values in the same residue class \bmod (k{+}1) to allow “YES”.
To show that this condition is sufficient, select all such values except those with maximum value to increase, and repeat until all have the same value. Then decrease to zero.