CHEFST - Editorial

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{aligned} 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{aligned}

Now, consider the sum in the brackets. Notice the pattern:

\begin{aligned} 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{aligned}

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{aligned} 2S &= [1 + 3 + 5 + 7 + \cdots + (2m-1)] + m \\\ 2S &= m^2 + m \\\ S &= \frac{m(m+1)}{2} \end{aligned}

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

5 Likes

@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

@durwasa_jec: U need to use llabs() for long long int and not abs(). Here’s the correct code: CodeChef: Practical coding for everyone

1 Like

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

Thanks !!

Great editorial! Checkout this brilliant wiki also: Greedy

Hi All,
Please help me finding the error in the below implementation:

cook your dish here

t = int(input())
for i in range(0,t):
n1,n2,m = map(int,input().split())
flag = 1
s1 = int(m*(m+1)0.5)
while(flag == 1):
if(n1>=s1 and n2 >=s1):
ans = n1 + n2 - (2
s1)
flag = 0
else:
s1 = min(n1,n2)
print (ans)

@shahbaz_23 :: thank you so much :slight_smile: :slight_smile:

Line 5
s1 = int(m*(m+1)*0.5)
Similiarly check line 8

Easy problem:
Here is the simple python solution. I initially forgot to add abs() :stuck_out_tongue:

for _ in range(int(input())):
n1,n2,m = map(int,input().split())
mini = min(n1,n2)
s = (m*(m+1))//2
if s>=mini:
    print(abs(n2-n1))
else:
    print(n2 + n1 - 2*s)

Please help me out. Im getting WA.

https://www.codechef.com/viewsolution/28784874
why i am getting partially wright answer

What is wrong with this answer?..maybe ill get tle …but should get first two tasks right?

#include <bits/stdc++.h>

using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);

int t;
cin>>t;
while(t--)
{
    long long int n1,n2,m,ans1=0,ans2=0;
    cin>>n1>>n2>>m;
    long long int i,sum=0;
    for(i=m;i>=1;--i)
     {
         sum+=i;
         if(sum>n1 || sum>n2)
          {
              sum-=i;
              break;
          }
     }
     
    ans1=(n1-sum)+(n2-sum); 
     sum=0;
    for(i=1;i<=m;++i)
    {
        sum+=i;
         if(sum>n1 || sum>n2)
          {
              sum-=i;
              break;
          }
    }
     
     ans2=(n1-sum)+(n2-sum);
    cout<<min(ans1,ans2)<<endl; 
}
  


 return 0;

}

1 Like

The Question doesn’t mention that we can not do the M-some number actions like
according to this solutions M=15;
but If N1=12 and N2=16 and M=5 without the AP.
then if we cannot remove from both then the answer of the remaining should be 2+6.
instead what we did is
M = 1,2,3,4,2 == 12 so this is actually contradicting the question statement .

Bro did the same instead of abs used Max and Min …giving WA in case 3

you have to start With value to solve

for _ in range(int(input())):
n1,n2,m = map(int,input().split())
mini = min(n1,n2)
s = (m*(m+1))//2
if s>=mini:
print(abs(n2-n1))
else:
print(n2 + n1 - 2*s)

why this is giving WA.