Author: Ivan Fekete
Tester: Misha Chorniy
Editorialist: Bhuvnesh Jain
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?
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.
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:
- Find the number of stones required in the first and second pile.
- Check if the required number of stones is non-negative or not.
- 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.
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.