PROBLEM LINK:
Practice
Contest Link
Author: Abhas Jain
Tester: Jatin Yadav
Editorialist: Abhas Jain
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
None
PROBLEM:
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.
EXPLANATION:
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.