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

×

CHEFST - Editorial

0
1

PROBLEM LINK:

Contest
Practice

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: $$\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 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: $$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 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: $$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 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: $$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 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: $$\begin{align*} S &= 1 + 2 + 3 + 4 + \cdots + m \\\ 2S &= 2 + 4 + 6 + 8 + \cdots + 2m \\\ 2S &= [1 + 3 + 5 + 7 + \cdots + (2m-1)] + \underbrace{1 + 1 + 1 + 1 + \cdots + 1}_{m} \\\ 2S &= [1 + 3 + 5 + 7 + \cdots + (2m-1)] + 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 + (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: $$\begin{align*} 2S &= [1 + 3 + 5 + 7 + \cdots + (2m-1)] + 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 m-1\}$. However, by assumption: $$1 + 2 + 3 + \cdots + m \ge r$$ By transposing the $m$, we get: $$1 + 2 + 3 + \cdots + (m-1) \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 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)$

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter
Tester
Editorialist

This question is marked "community wiki".

asked 13 Dec '15, 00:05

kevinsogo's gravatar image

7★kevinsogo
1.7k472135
accept rate: 11%

edited 13 Jan '16, 13:40

admin's gravatar image

0★admin ♦♦
15.9k347484508


@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

link

answered 18 Dec '15, 18:41

shahbaz_23's gravatar image

4★shahbaz_23
212
accept rate: 0%

@author @admin Why does abs(n1-n2) only solve the first two tasks (here) , while calculating the difference and multiplying a -1 accordingly (like diff=(diff if greater than 0)?diff:diff*-1) solve the problem (here) Or there is something

-Regards

link

answered 14 Dec '15, 23:28

durwasa_jec's gravatar image

2★durwasa_jec
32
accept rate: 0%

@shahbaz_23 :: thank you so much :) :)

(18 Dec '15, 19:13) durwasa_jec2★

can some please check this solution and point the error : https://www.codechef.com/viewsolution/8950590

Thanks !!

link

answered 28 Jan '16, 00:19

ashusingla's gravatar image

1★ashusingla
1
accept rate: 0%

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:

×11,590
×1,049
×777
×716
×173
×79

question asked: 13 Dec '15, 00:05

question was seen: 2,251 times

last updated: 28 Jan '16, 00:19