You are not logged in. Please login at www.codechef.com to post your questions!

×

SPLST - Editorial

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.

This question is marked "community wiki".

asked 28 Jul '18, 16:56

likecs's gravatar image

6★likecs
3.7k2380
accept rate: 9%

edited 28 Jul '18, 23:37

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 29 Jul '18, 08:36

ayush4's gravatar image

3★ayush4
162
accept rate: 11%

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★

@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.

link

answered 30 Jul '18, 16:32

shinchan6599's gravatar image

4★shinchan6599
312
accept rate: 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.

link

answered 21 Sep '18, 19:18

sarath127's gravatar image

2★sarath127
1
accept rate: 0%

edited 21 Sep '18, 19:19

(21 Sep '18, 19:28) sarath1272★

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) sarath1272★

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;

}

link

answered 23 Sep '18, 11:35

awwalboparai's gravatar image

0★awwalboparai
11
accept rate: 0%

edited 23 Sep '18, 11:37

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

link
This answer is marked "community wiki".

answered 23 Nov '18, 14:42

its__nishant's gravatar image

3★its__nishant
11
accept rate: 0%

edited 23 Nov '18, 14:49

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,682
×1,652
×593
×81
×51

question asked: 28 Jul '18, 16:56

question was seen: 1,474 times

last updated: 23 Nov '18, 14:50