Coin Piles problem from cses

help
4

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

2 Likes
5

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;
5 Likes
6

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.

19 Likes
7

how did you come up?

8

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.

1 Like
10

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: Competitive-Programming/CSES/Coin-Piles at master · strikersps/Competitive-Programming · GitHub

3 Likes
11

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;
    }
12

I am confused by what you mean when you say the following

I do not understand what you mean by x number of times and y number of times, and also I am confused as to why taking 1 coin from pile b affects the a equation (i.e. a = 2x + y).

Any sort of clarification would be very helpful. Thank you.

13

This is what I did :slight_smile: :

void solve(){
ll a, b;
cin >> a >> b;
if ((a + b) % 3 == 0 && 2 * a >= b && 2 * b >= a )
{
	cout << "YES";
}
else cout << "NO";

}

14

It means …When we reduce “a” by 2 then we must reduce “b” by 1 and when we reduce “a” by 1 the we must reduce “b” by 2. So if We assume that we take x times 2 and y times 1 to reach a to 0 then we must take x times 1 and y times 2 to reduce “b” to 0. i.e
a=2x+1y
b=1x+2y

15

Thanks for the clear explanation!!

16

My sol:
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
int main()
{
long long unsigned int t,a,b;

cin>>t;
while(t--)
{
    cin>>a>>b;
    if((2*a-b)%3==0 and (2*b-a)%3==0)
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
}

return 0;

}

17

Thank you for explaining it in detail

18

thanks">

19

?>

20

why you are doing this

if(a>2*b){
    cout<<"NO\n";
}
21

Hey, In the first line, he swaps a,b if a is smaller. So now, a will always be greater than equal to b.
In the worst case, if a is very large (as compared to b). We will always remove 2 from a and 1 from b (as a is the larger one).
eg - 24 12.
but if a is greater than 24 in this case - say 25,26,100 etc and b is 12.
The best you can do is keep removing 2 from a and 1 from b. but if a > 24, b will become 0 and a will still be nonzero.

22

if((a+b)%3==0)
how is this true

23

I solved it using binary search, but it seems like it had a way simpler solution.

void solve() {
    ll n, temp, a, b, ans = 0;
    cin >> a >> b;

    if(a == 2 * b || b == 2 * a) {
         cout << "YES" << endl;
         return;
    }
    if(a == 0 || b == 0) {
         cout << "NO" << endl;
         return;
    }
    ll start = 0, end = max(a, b);
    while(start < end) {
        ll mid = (start + end)/2;
        if(a - mid == 2 * (b - 2 * mid) && a - mid > 0) {
            cout << "YES" << endl;
            return;
        }
        if(a - mid > 2 * (b - 2 * mid)) end = mid;
        else start = mid + 1;
    }
    cout << "NO" << endl;
}
24

@prashant2020
let’s think about extreme condition , everytime you take 2 coin from a and 1 from b .
then also, a ratio b will be exact 2;
or else, their ratio will be less than 2; hence, it can never succeed 2;
Hope it helps.