# 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
**A**can be incremented at most_{i}**1 + ⌊ (M-A**times. If it has been incremented fewer times, its value will be at most_{i})/K ⌋**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. Therefore, the game ends with different arrays if and only if the operation is applied different number of times.**initial sum + 2 T K** - When the game ends, at most one entry is less than equal to
**M**. All others must be more than**M**.

Define **B _{i} = 1 + ⌊ (M-A_{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**entry, for

^{th}**i ≠ i**should be incremented exactly

_{0}**B**times.

_{i}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**. But is it always possible to end the game in

_{i0})/2 ⌉**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**and increment both of them once.

_{0}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**). It is clear that

_{i ≠ i0}B_{i}**L**steps is also sufficient to end the game because we can pair off all other

**i ≠ i**guys with this one. However, if

_{0}**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**is minimum. It is clear that if we choose

_{i0})/2 ⌉, max_{i ≠ i0}B_{i})**i**then both the terms feeded to max above are minimum.

_{0}= argmax B_{i}### 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 = 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 solutions

If the game can last a maximum of **S _{max}** moves and a minimum of

**S**moves, then we can make it last exactly

_{min}**S**moves for any

**S**. This is because if we have a game that lasts

_{min}≤ S ≤ S_{max}**S**steps and

**S < S**then we can construct a game which lasts

_{max}**S+1**steps as follows: in the game that lasts

**S**steps, lets say

**i**was the only element which did not become greator than

_{0}**M**. At some stage we must have paired two element

**i, j**such that

**i ≠ i**and

_{0}**j ≠ i**(if not then

_{0}**S = S**). we can remove this pairing and add two pairings

_{max}**(i, i**, thus ending the game in

_{0}), (j, i_{0})**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.

_{i}B

_{i}≤ 1/2 * sum

_{i}B

_{i}

**Proof:** Let **S = sum _{i} B_{i}**. Consider all

**B**’s sorted in descending order. There exists an index

_{i}**i**such that

**sum**and

_{j ≤ i}B_{j}≤ S/2**sum**. Let

_{j ≤ i+1}B_{j}> S/2**S’ = sum**. Then first

_{j ≤ i+1}B_{j}**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.