REALBIN - Editorial

It’s given that gcd(a, b) = 1 so A=3, B=12 is an invalid input.

2 Likes

didn’t understand the full proof for case 1,
but got the intuition that
a/b, gcd(a,b)=1
we cant vanish the prime factor from denominator other than 2

I am not able to get one thing that why they are taking X - Y = 0 and X + Y= 1.
Because chef will still win if X - Y is not equal to 0 and X + Y = 1.
If somebody knows what wrong with this then plz tell

2/5=0.4 now 0.4+0.6=1 so a=2, b=5 as input shouldn’t give ans as yes?

1 Like

can’t this be also true, if initially we have X = 1/3 and we have to make X = 1/2 so we take Y=1/6 and we get X = 1/3+1/6 =3/6=1/2 and then X will be a multiple of 1/2 hence we will get our answer

can someone tell me what is wrong with my code?

#include <bits/stdc++.h>
using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t,i,a,b;
cin>>t;

for(i=0;i<t;i++)
{
    cin>>a>>b;
   while(b%2==0)
            b=b/2;
   if(b==1)
            cout<<"Yes"<<'\n';
   else
            cout<<"No"<<'\n';
}
return 0;

}

1 Like

Are you certain that with the choice of 1/6 Chef is guaranteed to win? What about the case when rather than adding, Divyam subtracts 1/6 from 1/3 as it is his call not Chef’s whether the number chosen is added or subtracted. The question asks whether there is a strategy where Chef is guaranteed to win, which means he shall win irrespective of Divyam’s decision. In the example you are insisting upon, if Divyam subtracts the chosen number Chef will be left with 1/6 rather than 1/5. Divyam can prevent Chef from reaching 1 or 0 in all cases except the ones with the denominator a power of 2.

1 Like

umm okay but how do i resolve it? I tried to declare b in long long int too still it gives me wrong answer

The question asks whether or not there is a strategy that guarantees that Chef will win in a finite number of turns. This means winning irrespective of Divyam’s decision to add or subtract the chosen number. In the case of 0.4, if Chef chooses 0.6 and Divyam chooses to subtract rather than add, then Chef shall be left with another non binary number. This means that the choices you mentioned do not guarantee that Chef will win, thus the answer should be no.

1 Like

Link to your updated solution?

ahh, never mind I forgot to declare a as long long int, silly mistake! :sweat_smile: Thanks BTW!

1 Like

yes, I got that wrong, thankyou for clarification, the test cases were weak my wrong answer passed during the contest.

Well a much better way would be to use Bit Manipulation to check whether its power of 2 or not
(b&(b-1)) == 0 then its a power of two
if (b&(b-1)) cout << “NO\n”;
else cout << “YES\n”;