Coin Piles problem from cses

Hi all
I am trying to solve this problem but unable to find the solution.
Any kind of hint would be great.
https://cses.fi/problemset/task/1754/

This is what I did:
Try removing coins from bottom, It’s more intuitive that way.

if(a<b)swap(a,b);
if(a>2*b){
    cout<<"NO\n";
}else{
    a%=3,b%=3;
    if(a<b)swap(a,b);
    if((a==2 && b==1) || (a==b && b==0)){
        cout<<"YES\n";
    }else{
        cout<<"NO\n";
    }
}
2 Likes

I really wish they had solutions for cses, It has really good problems.

1 Like

got your idea thanks.
I was also thinking this way but couldn’t come with a%=3,b%=3; this step.

1 Like

Here is my solution.

  if(a<b) swap(a,b);

  if(a>2*b) 
  {
     cout<<"NO" << endl;
     return 0;
   }

  if((a+b)%3==0) 
  {
    cout<<"YES"<< endl;
  }
  else cout<<"NO"<< endl;

I know this is from a while ago, but i thought there wasn’t sufficient explanations in any of the other answers.

Lets say x times we take 2 from a , and 1 from b
and y times we take 2 from b and 1 from a

meaning:
a = 2x + 1y
b = 1x + 2y

on solving for a and b

2a - b = 3x
2b - a = 3y

x and y should be non negative , and from here we can derive (a+b)%3==0.

2 Likes

how did you come up?

since he swaps a and b if a is less than b,so a must be atmost 2b if we want to empty both piles as 2 coins from a and 1 coin from b will be used but if a > 2b then whole pile of b will become empty and some coins will still be left in a.

Let’s assume that we are removing x number of times 2 coins from pile a and 1 coin from pile b.

Let’s assume that we are removing y number of times 1 coin from pile a and 2 coins from pile b.

Mathematically we can write our assumptions as:
a = 2x + y \;\;\cdots (i)
b = x + 2y \;\; \cdots (ii)

We have two equations and we have two unknowns, means we can solve for x and y.
After solving the above equations for x and y, you will get:
x = \frac{2a - b}{3}
y = \frac{2b - a}{3}

Clearing x and y \in Z^{+} and they must be a multiple of 3.

One more important information we will get when we subtract (ii) from (i) i.e.
|a - b| = |x - y|

Source Code: https://github.com/strikersps/Competitive-Programming/tree/master/CSES/Coin-Piles

My solution.

   #include<iostream>
    void swap(int *,int *);
    int main(){
    	int t, a, b, x;
    	std::cin >> t;
    	while ( t-- ) {
    		bool flag = false;
    		std::cin >> a >> b;
    		if (b>a) swap(&a , &b) ;
    		x = a-b;
    		if (x > b) flag = true;
    		a -= 2 * x;
    		b -= x;
    		if (a != b) flag = true;
    		if (a % 3 != 0) flag = true;
    		if (flag) std::cout << "NO\n" ;
    		else std :: cout << "YES\n" ;
    	}
    	return 0;
    }
    void swap (int *a, int *b){
    	int temp = *a;
    	*a = *b;
    	*b = temp;
    }