Problem Link:
Author: Roman Rubanenko
Tester/Editorialist: Utkarsh Lath
Difficulty:
Medium
Pre-requisites:
None
Problem:
You start with an array, all whose entries are initially at most M. You can keep following operation:
- Choose any two distinct entries, such that both are at most M, and increase both by K.
You stop when you can no longer apply the above operation. Find how many different arrays can you end up with. Two arrays are different iff their sum is different.
Explanation:
Important observations:
- An array entry Ai can be incremented at most 1 + ⌊ (M-Ai)/K ⌋ times. If it has been incremented fewer times, its value will be at most M, and can still be used in the operation.
- If the operation is applied T number of times before the procedure stops, then the final sum is initial sum + 2 T K. Therefore, the game ends with different arrays if and only if the operation is applied different number of times.
- When the game ends, at most one entry is less than equal to M. All others must be more than M.
Define Bi = 1 + ⌊ (M-Ai)/K ⌋, and S = Σi Bi.
Lets first try to find out the minimum of steps in which the game can end.
When the game ends, at most one entry can be less than equal to M, and let this entry be i0. Then, ith entry, for i ≠ i0 should be incremented exactly Bi times.
Therefore, the game will not end before (S - Bi0)/2 moves. And since the number of moves cannot be a fraction, lower bound becomes S’ = ⌈ (S - Bi0)/2 ⌉. But is it always possible to end the game in S’ moves ?
Suppose we did not had the restriction to choose two distinct array elements for increment. Then it is obvious that the game could be made to finish in S’ steps. This is because if two distinct elements less than M are not available, we could increment the same element twice, until we reach the stage where either all array elements (except i0) become greater than M, or only one of them is left and it can be incremented only once, in which case, pair it with i0 and increment both of them once.
Therefore, only the restriction of choosing distinct pairs can prevent us from ending the game in S’ steps. It can be seen that if maxi ≠ i0 Bi > S’, then we can never end the game in S’ steps because even if we use this maximum element in all pairings we would still need L steps(where L = maxi ≠ i0 Bi). It is clear that L steps is also sufficient to end the game because we can pair off all other i ≠ i0 guys with this one. However, if L ≤ S’, it can be proved that we can always end the game in S’ steps(proof at the end).
Now, we need to choose i0 so that the above quantity, max(S’, L) = max(⌈ (S - Bi0)/2 ⌉, maxi ≠ i0 Bi) is minimum. It is clear that if we choose i0 = argmax Bi then both the terms feeded to max above are minimum.
Now lets try to find the maximum number of steps the game can last
The game cannot last more than S/2 steps because S is the maximum number of times we can increment array elements. Since the number of rounds is integer, maximum number of rounds is at most ⌊S/2⌋. Let X = maxi Bi. If X ≤ S/2 then it is again possible to stretch the game till ⌊S/2⌋ moves. Otherwise, it is clear that even if we use the maximum guys in all our pairings, we cannot pair more than S - X times. Therefore, the maximum number of steps is min(⌊S/2⌋, S - maxi Bi)
Total number of solutions
If the game can last a maximum of Smax moves and a minimum of Smin moves, then we can make it last exactly S moves for any Smin ≤ S ≤ Smax. This is because if we have a game that lasts S steps and S < Smax then we can construct a game which lasts S+1 steps as follows: in the game that lasts S steps, lets say i0 was the only element which did not become greator than M. At some stage we must have paired two element i, j such that i ≠ i0 and j ≠ i0 (if not then S = Smax). we can remove this pairing and add two pairings (i, i0), (j, i0), thus ending the game in S+1 steps.
Given the array B such that maxi Bi ≤ 1/2 * sumi Bi, we can construct a game where at most one element is unexhausted(less than equal to M) and the unexhausted element can be increased at most once before it gets exhausted.
Proof: Let S = sumi Bi. Consider all Bi’s sorted in descending order. There exists an index i such that sumj ≤ i Bj ≤ S/2 and sumj ≤ i+1 Bj > S/2. Let S’ = sumj ≤ i+1 Bj. Then first S’ - S/2 steps can be pairing 0 with i+1. After that, sum of first i+1 element in array B becomes half the total sum, so we can keep constructing pairs (i’, j’) such that i’≤ i+1 < j’ till at most one entry is left unexhausted.
