ICM2002(Are These Equal) - Editorial


Contest Link
Author: Abhas Jain
Tester: Jatin Yadav
Editorialist: Abhas Jain






Convert an integer array into the zero array by performing some moves. A move consists of choosing k distinct elements and decreasing them by 1 each.


Decreasing elements of B is the same as increasing A.

The obvious necessary condition is that sum % k == 0 and max[B[i]] <= sum / k (Number of moves required).

Let’s prove that it is also sufficient. In every move take the biggest k elements of B and decrease them by 1.

sum % k == 0 will hold after each move.

Now, after some move sum will be decreased by k so (sum / k) will decrease by 1. Now max[B[i]] will also decrease by 1. (How?)

Statement 1 - We know we cannot have more than k elements equal to sum / k. (Otherwise sum \geq (k + 1) * (sum / k) which is not possible.)

Let’s say in the worst case max[B[i]] == sum / k before some move, now we will decrease the first k elements, (k + 1)th element cannot be equal be max[B[i]] in this case (using Statement 1), so max[B[i]] \leq sum / k will also hold after that move.

So the necessary conditions will hold after every move.

Also, to prove that at least k elements will remain non-zero after every move, assume the contradiction that kth element becomes 0 and at least one element remained non-zero during our process. This is also not possible because then at least one element will be greater than sum / k.

This shows that we can perform every move successfully and it completes the proof.


Solution Link


Such a beautiful Question and Editorial


In this, I think we also need to check whether the number sum/k is occurring less than or equal to k times or not. If it is coming more than k times then answer should be NO. Where is that part in solution link code?
Correct me if I am wrong.

sum/k cannot appear more than k times in any array.
Let’s assume sum/k appears (k + 1) times, then our sum will be >= (k + 1) * (sum / k) which means sum > sum. That is never possible.


Ok I just left that statement in editorial. Thank You