PROBLEM LINK:Author: Tapas Jain PREREQUISITES:Arithmetic series, greedy, ad hoc PROBLEM:Consider a singleplayer 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: $$\max(n_1 + n_2  m(m+1), n_1  n_2, n_2  n_1)$$ 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: $$(n_1  x) + (n_2  x) = n_1 + n_2  2x$$ 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 stonesNext, 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: $$1 + 2 + 3 + 4 + \cdots + m$$ 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 stonesNow 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: $$31 = 10 + 9 + 8 + 4$$ 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 stonesWe'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: $$n_1 + n_2  2x$$ where $$x = \min\left(\frac{m(m+1)}{2},n_1,n_2\right)$$ As a side note, we can actually substitute $x$ to $n_1 + n_2  2x$ to get the following expression: $$\max(n_1 + n_2  m(m+1), n_1  n_2, n_2  n_1)$$ which gives us the following oneliner Python code (excluding the part of code that takes the input from stdin):
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: $$\begin{align*} S &= 1 + 2 + 3 + 4 + \cdots + m \\\ 2S &= 2 + 4 + 6 + 8 + \cdots + 2m \\\ 2S &= [1 + 3 + 5 + 7 + \cdots + (2m1)] + \underbrace{1 + 1 + 1 + 1 + \cdots + 1}_{m} \\\ 2S &= [1 + 3 + 5 + 7 + \cdots + (2m1)] + m \end{align*}$$ Now, consider the sum in the brackets. Notice the pattern: $$\begin{align*} 1 &= 1 \\\ 4 &= 1 + 3 \\\ 9 &= 1 + 3 + 5 \\\ 16 &= 1 + 3 + 5 + 7 \\\ 25 &= 1 + 3 + 5 + 7 + 9 \\\ 36 &= 1 + 3 + 5 + 7 + 9 + 11 \end{align*}$$ These are just the perfect squares! Thus, we conjecture that $1 + 3 + 5 + \cdots + (2m1) = m^2$. In fact, this can easily be visualized as follows:
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: $$\begin{align*} 2S &= [1 + 3 + 5 + 7 + \cdots + (2m1)] + m \\\ 2S &= m^2 + m \\\ S &= \frac{m(m+1)}{2} \end{align*}$$ 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 m1\}$. However, by assumption: $$1 + 2 + 3 + \cdots + m \ge r$$ By transposing the $m$, we get: $$1 + 2 + 3 + \cdots + (m1) \ge r  m$$ 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 m1\}$! 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)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 13 Dec '15, 00:05

@durwasa_jec: U need to use llabs() for long long int and not abs(). Here's the correct code: https://www.codechef.com/viewsolution/8975993 answered 18 Dec '15, 18:41

@author @admin Why does abs(n1n2) only solve the first two tasks (here) , while calculating the difference and multiplying a Regards answered 14 Dec '15, 23:28
@shahbaz_23 :: thank you so much :) :)
(18 Dec '15, 19:13)

can some please check this solution and point the error : https://www.codechef.com/viewsolution/8950590 Thanks !! answered 28 Jan '16, 00:19
