Problem LinkAuthor: Ivan Fekete Tester: Misha Chorniy Editorialist: Bhuvnesh Jain DifficultyCAKEWALK PrerequisitesNone ProblemYou 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? ExplanationAuthor's SolutionLet 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 SolutionSince 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:
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".
asked 28 Jul '18, 16:56

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
1
@ayush4, your condition $p <= a[1]$ is not required. Please read editorial again for the proof.
(29 Jul '18, 12:53)
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)

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
My Solution https://www.codechef.com/viewsolution/20259606
(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)

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.
} answered 23 Sep '18, 11:35

In my code I implemented only 2 contain
else print NO
link
This answer is marked "community wiki".
answered 23 Nov '18, 14:42
