PROBLEM LINK:
Author: Tapas Jain
Tester: Sergey Kulik
Editorialist: Kevin Atienza
PREREQUISITES:
Arithmetic series, greedy, ad hoc
PROBLEM:
Consider a single-player game on two piles of stones. One has n_1 stones and the other has n_2 stones. Before the start of the game, we choose an integer m.
In a move, we choose a number between 1 and m, and remove that number of stones from both piles. (this is only possible when both the piles have at least that many stones). Also, the number of stones to remove at each step must be unique. The game ends when there are no more moves.
What is the minimum number of stones that could remain, among all possible games?
QUICK EXPLANATION:
The answer is n_1 + n_2 - 2x, where x is the maximum number of stones we can remove from both piles.
We can only remove up to 1 + 2 + \cdots + m = \frac{m(m+1)}{2} stones from both piles. If n_1 and n_2 are both at least \frac{m(m+1)}{2}, then this is the maximum number we can remove. Otherwise, we can remove up to \min(n_1,n_2) from both piles. Therefore, x = \min(\frac{m(m+1)}{2}, n_1, n_2).
The answer can also be expressed as a single expression:
EXPLANATION:
At any point in the game, the number of stones we have removed from both piles are always equal. Suppose we remove x stones from both piles. Then there are n_1 - x stones remaining in the first pile and n_2 - x in the second. Therefore, the number of stones remaining is:
The answer is the minimum value of this expression. n_1 and n_2 are fixed throughout the game, but we can control x depending on how we play. But a higher x corresponds to a lower n_1 + n_2 - 2x, so we actually want to maximize x, the number of stones we remove from both piles!
Maximum number of removed stones
Next, let’s consider the requirement that “the number of stones to remove at each step must be unique”. What does this mean for us? Well, since there are only m unique numbers from 1 to m, namely 1, 2, \ldots, m, this means that the game ends after at most m moves, and that the maximum number of stones we can remove is simply:
This is actually a pretty famous sum, and the formula is \frac{m(m+1)}{2}. (A derivation is given in the appendix.) Therefore, we can only remove between 0 to \frac{m(m+1)}{2} stones.
Removing a given number of stones
Now we know that we can only remove between 0 to \frac{m(m+1)}{2} stones. The next question is: given some number r between 0 and \frac{m(m+1)}{2}, can we remove exactly r stones? In other words, is it possible to express r as a sum of distinct numbers from 1 to m? For example, can you try to express the number 31 as the sum of distinct numbers from 1 to 10?
Let’s try. Since 31 is huge, we try adding the large addends first. Say 10. Then 31 - 10 = 21 remains. The next largest addend is 9, so we try that. 21 - 9 = 12 remains. The next one is 8, so we try that, and 12 - 8 = 4 remains. Our number is small now, and in fact since it’s already \le 7, we can just use 4 as our final addend. Therefore:
Does this greedy algorithm always work? Amazingly, yes! (as shown in the appendix) Therefore, given any r, we can always remove exactly r stones.
Maximizing the number of removed stones
We’re almost there! We want to maximize the number of stones to remove. Clearly, regardless of the size of the piles, the absolute maximum number we can remove is \frac{m(m+1)}{2} as shown above. Thus, if n_1 and n_2 are both at least \frac{m(m+1)}{2}, then this is the maximum.
Now, what if one of n_1 and n_2 are smaller than \frac{m(m+1)}{2}? In other words, \min(n_1,n_2) < \frac{m(m+1)}{2}. In this case, we can no longer remove \frac{m(m+1)}{2} stones, because there aren’t enough stones in one of the piles. In fact, we can’t remove more than \min(n_1,n_2), because this is the size of the smaller pile. But since \min(n_1,n_2) is smaller \frac{m(m+1)}{2}, as shown above we can always remove exactly \min(n_1,n_2) stones. Therefore, the maximum stones we can remove is actually \min(n_1,n_2)!
We now have the whole solution! It is:
where
As a side note, we can actually substitute x to n_1 + n_2 - 2x to get the following expression:
which gives us the following one-liner Python code (excluding the part of code that takes the input from stdin):
print max(n1 + n2 - m*(m+1), n1 - n2, n2 - n1)
Appendix: Showing that 1 + 2 + 3 + 4 + \cdots + m = \frac{m(m+1)}{2}
We want to find a formula S := 1 + 2 + 3 + 4 + \cdots + m. I’ll show a derivation here that is slightly different from the usual reverse and add method.
Let’s begin:
Now, consider the sum in the brackets. Notice the pattern:
These are just the perfect squares! Thus, we conjecture that 1 + 3 + 5 + \cdots + (2m-1) = m^2. In fact, this can easily be visualized as follows:
m=1 m=2 m=3 m=4 m=5
1 1 2 1 2 3 1 2 3 4 1 2 3 4 5
2 2 2 2 3 2 2 3 4 2 2 3 4 5
3 3 3 3 3 3 4 3 3 3 4 5
4 4 4 4 4 4 4 4 5
5 5 5 5 5
Note that the m th figure contains m^2 items, but at each step we’re adding 1, then 3, then 5, etc., items, to the previous figure!
Therefore:
which is what we wanted to show.
Appendix: Summing a number between 0 and \frac{m(m+1)}{2}
Finally, we want to show why the greedy algorithm above works for expressing a number r between 0 and \frac{m(m+1)}{2} as a sum of distinct numbers from the set \{1, 2 \ldots m\}.
The greedy algorithm first proceeds to check whether m \le r, and if so, adds m to the list of addends. Then we proceed by expressing the number r - m as a sum of numbers from the set \{1, 2 \ldots m-1\}. However, by assumption:
By transposing the m, we get:
Therefore, by doing an induction argument, we can see that the number r - m can be expressed as a sum of numbers from the set \{1, 2 \ldots m-1\}!
This only works when m \le r though. What if m > r? Then in that case, we can simply use r as the lone addend in the sum, because r \in \{1, 2 \ldots m\}! Thus, we have just shown that the greedy algorithm works.
Time Complexity:
O(1)
