SPLST - Editorial

editorial
, , , ,
1

Problem Link

Practice

Contest

Author: Ivan Fekete

Tester: Misha Chorniy

Editorialist: Bhuvnesh Jain

Difficulty

CAKEWALK

Prerequisites

None

Problem

You are 3 piles of stones containing a, b, c stones respectively. You can chose one of the piles and split it into 2 parts (possibly empty) and put the stones for the first part in one pile and the second one in another. Is it possible to have 2 piles with x, y stones?

Explanation

Author’s Solution

Let us first sort the piles in increasing number of stones. So, a <= b <= c. Also, assume x <= y. The first condition which should be satisfied is that the number of stones in the beginning and the end should remain same as none of the stones is thrown away, they are just rearranged into different piles.

Condition 1: a + b + c == x + y

Next thing is to observe is that the size of a pile can only increase and if it decreases it becomes 0 only. So, if the number of stones in the smallest pile, in the beginning, is more is than the number of stones in the smallest pile, in the end, we can’t achieve our target.

Condition 2: a <= x

Similar case applies to the second smallest pile as well.

Condition 3: b <= y

The above 3 conditions are necessary for us to have a solution. But are they sufficient? Apparently yes, as we can always achieve our target as follow when the above 3 conditions hold:

Consider the third pile (c) as the pile with excess stones. Move the required number of stones to the first pile and the remaining stones to the second pile. As the total number of stones is same and the number of stones in both remaining piles can only increase, such a move will exist.

For more details, you can refer to the author’s or tester’s solution below.

Editorialist Solution

Since the constraints are small, we can simply simulate the above process, by trying to eliminate each pile and moving the required number of stones to the other 2 piles. Writing the cases for this can be tedious and some cases might not be handled as well if not implemented correctly. So, one idea is to try each possible pairing using permutations of the piles such that you always consider the last piles as the one with excess stones which would be removed by splitting stones into other piles. The conditions to check are simply:

  1. Find the number of stones required in the first and second pile.
  2. Check if the required number of stones is non-negative or not.
  3. Check if the sum of the number of required stones can be exactly satisfied by the excess pile.

Once, you are clear with the above idea, you can see the editorialist implementation below for help.

Feel free to share your approach, if it was somewhat different.

Time Complexity

O(1)

Space Complexity

O(1)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.

2

what’s wrong with my code, please check it https://pastebin.com/t34g52bL . I have explained as much as I can with comments.

3

@ayush4, your condition p <= a[1] is not required. Please read editorial again for the proof.

1 Like
4

Thanks for the response. It would be great if you can provide me with 1 test case for better understanding because it was working for all the test cases on codechef and the ones I made.

5

@ayush4 try 2 3 20 12 13. According to your code it’ll print NO as your condition “if(p <= a[1])” will become false but the correct answer is YES.

6

In my code I have only implemented the first and the second conditions only. May I know why the third condition is also necessary? It would also be great if you can share a testcase where the third condition not satisfied but the first two are satisfied.

7

My Solution https://www.codechef.com/viewsolution/20259606

8

Assuming sorted as a <= b <= c and x <= y
By cond 1 : a + b + c = x + y
By cond 2 : a <= x
=> even when a = x, b + c = y ==> b < y, and c < y always. So no need to check b < y

9

Why is my code not working? I’ve used a basic approach of checking permutations. I can work on the time limit but the compiler is giving the ‘wrong answer’ error.

enter code here
#include<iostream>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
    int a,b,c,x,y,d,e,f,i;
    cin>>a>>b>>c>>x>>y;
    if(x+y==a+b+c)
    {
        if(a>b&&a>c)
        {
            d=a;
            e=b;
            f=c;
        }
        if(b>a&&b>c)
        {
            d=b;
            e=c;
            f=a;
        }
        if(c>a&&c>b)
        {
            d=c;
            e=a;
            f=b;
        }
        for(i=0; i<=d; i++)
        {
            e+=i;
            f+=(d-i);
            if((e==x&&f==y)||(e==y&&f==x))
            {
                cout<<"YES\n";
                break;
            }
            e-=i;
            f-=(d-i);
        }
        if(i==d+1)
            cout<<"NO\n";
    }
    else
    cout<<"NO\n";
}
return 0;

}

10

In my code I implemented only 2 contain
https://www.codechef.com/viewsolution/21679289
First sort a,b,c.
let sorting are in sequence of a,b,c
or select last two elements of ascending
sorted sequence

  1. if((a+b+c)==(x+y))
    { if((b+c)>=max(x,y))

     Print NO

else 

print YES

}

else

print NO