Problem Link:Author: Roman Rubanenko Difficulty:Medium Prerequisites:None Problem:You start with an array, all whose entries are initially at most M. You can keep following operation: Explanation:Important observations: Define B_{i} = 1 + ⌊ (MA_{i})/K ⌋, and S = Σ_{i} B_{i}. 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 i_{0}. Then, i^{th} entry, for i ≠ i_{0} should be incremented exactly B_{i} times. Therefore, the game will not end before (S  B_{i0})/2 moves. And since the number of moves cannot be a fraction, lower bound becomes S' = ⌈ (S  B_{i0})/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 i_{0}) become greater than M, or only one of them is left and it can be incremented only once, in which case, pair it with i_{0} 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 max_{i ≠ i0} B_{i} > 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 = max_{i ≠ i0} B_{i}). It is clear that L steps is also sufficient to end the game because we can pair off all other i ≠ i_{0} 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 i_{0} so that the above quantity, max(S', L) = max(⌈ (S  B_{i0})/2 ⌉, max_{i ≠ i0} B_{i}) is minimum. It is clear that if we choose i_{0} = argmax B_{i} then both the terms feeded to max above are minimum. Now lets try to find the maximum number of steps the game can lastThe 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 = max_{i} B_{i}. 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  max_{i} B_{i}) Total number of solutionsIf the game can last a maximum of S_{max} moves and a minimum of S_{min} moves, then we can make it last exactly S moves for any S_{min} ≤ S ≤ S_{max}. This is because if we have a game that lasts S steps and S < S_{max} then we can construct a game which lasts S+1 steps as follows: in the game that lasts S steps, lets say i_{0} 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 ≠ i_{0} and j ≠ i_{0} (if not then S = S_{max}). we can remove this pairing and add two pairings (i, i_{0}), (j, i_{0}), thus ending the game in S+1 steps. Given the array B such that max_{i} B_{i} ≤ 1/2 * sum_{i} B_{i}, 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 = sum_{i} B_{i}. Consider all B_{i}'s sorted in descending order. There exists an index i such that sum_{j ≤ i} B_{j} ≤ S/2 and sum_{j ≤ i+1} B_{j} > S/2. Let S' = sum_{j ≤ i+1} B_{j}. 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:
This question is marked "community wiki".
asked 23 Sep '13, 00:12

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. answered 23 Sep '13, 00:43

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) answered 24 Sep '13, 19:08
