RRGAME - Editorial

Problem Link:

Practice

Contest

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.

Solutions:

Setter’s solution
Tester’s Solution

7 Likes

Why modulo was required in this problem?

6 Likes

Hey I guess your Test Cases are WEAK, For the case : n = 4, m = 10, k = 1, and A[] = {10,10,10,2}, many of the Accepted solutions are giving ans = 5, or ans = 1, but the ans = 2.

http://www.codechef.com/viewsolution/2703372

http://www.codechef.com/viewsolution/2705602

http://www.codechef.com/viewsolution/2705244

http://www.codechef.com/viewsolution/2705276

http://www.codechef.com/viewsolution/2705206

http://www.codechef.com/viewsolution/2705204

http://www.codechef.com/viewsolution/2705168

and these are not all of them.

10 Likes

can you please explain how do you get min =ceil( (sum-bi0)/2) (leaving the other case)…
for ex if i have values of n m k as 5 16 2 and the array is 2 5 7 12 14 than B array is 8 6 5 3 2 and min=(24-8)/2 ==> min=8 but i can not get 8 by any means … the best i can get is 9 … can you please explain this and also the same regarding max

3 10 3 4 1 8

I can’t see why the answer for this case is 3, could someone help me? The minimum number of moves in the accepted code is 2, but I can’t find a sequence of moves :confused:

I think the test cases used by online judge are weak. The below solution is accepted
http://www.codechef.com/viewsolution/2705244

He considered max number of steps as ⌊s/2⌋ not min(⌊S/2⌋, S - maxi Bi)

1 Like

Please explain the meaning of "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 decremented exactly Bi times."

why decremented? aren’t we incrementing the numbers?

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.

Please somebody explain me this?

cannot get why "Therefore, the game will not end before (S - Bi0)/2 moves" ?

8 can be obtained:
2 7 9 12 14
2 9 11 12 14
2 11 13 12 14
2 13 15 12 14
2 15 17 12 14
2 15 17 14 16
2 15 17 16 18
2 17 17 18 18

according to the above formula it is not 2 …
it is max(2,3) so it is 3 … and you can see that it can be done in 3 moves

1 Like

And the maximum would be 4? So the answer for this test case is 2?

Yeah, you are right. Actually, when you increment A[i], you decrement B[i], because B[i] gives the number of times you can apply the operation on ith element.

I kind of think it as decreasing B[i]'s(till all of them become 0) rather than increasing A[i]'s that why I messed up at two places. corrected them now.

Thanks for pointing.

Can anyone please explain the solution once again as the language used by the author is quite tricky ???

In each move, you select a pair and increment both of them,i.e, in one move you increment 2 values. Suppose there are 3 elements so we’ll have S=B[1]+B[2]+B[3]. Suppose min no of moves is 3. Here are the 3 possible moves: 1) elements 1&2 selected so B[1]=1 & B[2]=1. 2)elements 2&3 selected so B[2]=2&B[3]=1. 3) elements 1&3 selected so B[1]=2&B[3]=2…now as you can see, S=B[1]+B[2]+B[3] = 2+2+2 = 6. But min no of moves are 3 = S/2. Of course, here Bi0=0 since we do not have any more elements. But you can easily see if we had an element left then min no of moves would have been (S-Bi0)/2.

1 Like

Thanks i_wanna_rokk , that really helped!