You are not logged in. Please login at www.codechef.com to post your questions!

×

RRGAME - Editorial

7
3

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

This question is marked "community wiki".

asked 23 Sep '13, 00:12

admin's gravatar image

0★admin ♦♦
19.7k350498541
accept rate: 35%

edited 25 Sep '13, 11:19

utkarsh_lath's gravatar image

5★utkarsh_lath ♦♦
255385251


10

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.

link

answered 23 Sep '13, 00:43

adurysk's gravatar image

4★adurysk ♦
92852428
accept rate: 11%

edited 23 Sep '13, 00:44

Why modulo was required in this problem?

link

answered 23 Sep '13, 00:41

witua's gravatar image

4★witua
9112
accept rate: 0%

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)

link

answered 24 Sep '13, 19:08

anil09's gravatar image

1★anil09
36149
accept rate: 0%

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

link

answered 23 Sep '13, 04:50

gauravdrocker's gravatar image

3★gauravdrocker
91246
accept rate: 0%

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

(23 Sep '13, 06:34) utkarsh_lath ♦♦5★

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 :/

link

answered 24 Sep '13, 00:17

brunoja's gravatar image

6★brunoja
764
accept rate: 0%

1

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

(24 Sep '13, 03:08) gauravdrocker3★

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

(24 Sep '13, 17:43) brunoja6★

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?

link

answered 25 Sep '13, 09:14

narrow001's gravatar image

2★narrow001
1
accept rate: 0%

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.

(25 Sep '13, 11:22) utkarsh_lath ♦♦5★

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?

link

answered 27 Sep '13, 11:43

jaskaran_1's gravatar image

3★jaskaran_1
525233550
accept rate: 0%

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

(16 Oct '13, 16:14) shar2ad01_123★

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

link

answered 17 Oct '13, 23:05

mjnovice's gravatar image

3★mjnovice
1343513
accept rate: 0%

1

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.

(17 Oct '13, 23:33) i_wanna_rokk4★

Thanks i_wanna_rokk , that really helped!

(18 Oct '13, 19:23) mjnovice3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,629
×2,575
×7
×2

question asked: 23 Sep '13, 00:12

question was seen: 4,582 times

last updated: 18 Oct '13, 19:23