×

SPLST - Editorial

Practice

Contest

Author: Ivan Fekete

Tester: Misha Chorniy

Editorialist: Bhuvnesh Jain

CAKEWALK

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.

This question is marked "community wiki".

6★likecs
3.7k2481
accept rate: 9%

19.8k350498541

 0 what's wrong with my code, please check it https://pastebin.com/t34g52bL . I have explained as much as I can with comments. answered 29 Jul '18, 08:36 3★ayush4 16●3 accept rate: 10% 1 @ayush4, your condition $p <= a[1]$ is not required. Please read editorial again for the proof. (29 Jul '18, 12:53) likecs6★ 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. (29 Jul '18, 19:45) ayush43★
 0 @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. answered 30 Jul '18, 16:32 31●2 accept rate: 0%
 0 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. answered 21 Sep '18, 19:18 1 accept rate: 0% (21 Sep '18, 19:28) 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 (21 Sep '18, 19:32)
 0 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 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;  } answered 23 Sep '18, 11:35 1●1 accept rate: 0%
 0 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 if((a+b+c)==(x+y)) { if((b+c)>=max(x,y))  Print NO else print YES  } else print NO link This answer is marked "community wiki". answered 23 Nov '18, 14:42 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,852
×1,688
×593
×81
×51

question asked: 28 Jul '18, 16:56

question was seen: 1,541 times

last updated: 23 Nov '18, 14:50