REALBIN - Editorial

How can X=15/16 can result in a win for Chef? Please explain. I only figured out that we can use Y=-1/16 for getting the chef to win, but ATQ Y must be positive. So can does 15/16 reduce to 0 or 1?

I haven’t checked this (nor read the Editorial :blush:), but given X={a \over 2^k}, where a and 2^k are co-prime (and so a is odd) and a<2^k, Chef’s strategy is always to pick Y={1 \over 2^k}: then no matter if Divyam chooses to add or subtract Y, the result is either 0, 1, or {a' \over 2^{k-1}}, where a' is coprime to 2^{k-1}, a' < 2^{k-1} etc. Try it out with your example!

2 Likes

For fast io in python, use this -

Define iobio at start of your program once -
iobio = io.BytesIO(os.read(0, os.fstat(0).st_size))

Then, read each line of the input as follows -
line1 = iobio.readline().decode().strip()
line2 = iobio.readline().decode().strip()
line3 = iobio.readline().decode().strip()

int main() {
	ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
	ios_base::sync_with_stdio(false);
cin.tie(0);
	int c;
	cin>>t;

     while(t--)
     {
         cin>>a>>b;
         ans=0;
         a=b;
         while(b>0)
         {
             ans++;
             b/=2;
         }
      //ans=floor(log2(b));
      
     ans--;
    // cout<<(1<<ans)<<"\n";
      if(a==(1<<ans))
      cout<<"Yes\n";
      else
      cout<<"No\n";
       }

Can you please tell me why it is giving wrong answer?
https://www.codechef.com/viewsolution/48253449
Thanks

int main() {
	ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
	ios_base::sync_with_stdio(false);
cin.tie(0);
	int c;
	cin>>t;

     while(t--)
     {
         cin>>a>>b;
         ans=0;
         a=b;
         while(b>0)
         {
             ans++;
             b/=2;
         }
      //ans=floor(log2(b));
      
     ans--;
    // cout<<(1<<ans)<<"\n";
      if(a==(1<<ans))
      cout<<"Yes\n";
      else
      cout<<"No\n";
       }

Can you please tell me why it is giving wrong answer?
https://www.codechef.com/viewsolution/48253449

Thanks

Consider the test input:

1
1 8589934592

Yes it is giving No
but correct answer is Yes

Can you tell me the reason?
Is it due to (1<<ans) became out of range?
Thanks

Yes:

[simon@simon-laptop][13:39:58]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh                                       
Compiling garvit2013-REALBIN.cpp
+ g++ -std=c++14 garvit2013-REALBIN.cpp -O3 -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG -fsanitize=undefined -ftrapv
garvit2013-REALBIN.cpp: In function ‘int main()’:
garvit2013-REALBIN.cpp:11:7: warning: unused variable ‘i’ [-Wunused-variable]
  ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
       ^
garvit2013-REALBIN.cpp:11:9: warning: unused variable ‘j’ [-Wunused-variable]
  ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
         ^
garvit2013-REALBIN.cpp:11:11: warning: unused variable ‘n’ [-Wunused-variable]
  ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
           ^
garvit2013-REALBIN.cpp:11:13: warning: unused variable ‘m’ [-Wunused-variable]
  ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
             ^
garvit2013-REALBIN.cpp:11:15: warning: unused variable ‘q’ [-Wunused-variable]
  ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
               ^
garvit2013-REALBIN.cpp:11:17: warning: unused variable ‘k’ [-Wunused-variable]
  ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
                 ^
garvit2013-REALBIN.cpp:11:19: warning: unused variable ‘d’ [-Wunused-variable]
  ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
                   ^
garvit2013-REALBIN.cpp:11:21: warning: unused variable ‘l’ [-Wunused-variable]
  ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
                     ^
garvit2013-REALBIN.cpp:11:27: warning: unused variable ‘h’ [-Wunused-variable]
  ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
                           ^
garvit2013-REALBIN.cpp:11:29: warning: unused variable ‘y’ [-Wunused-variable]
  ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
                             ^
garvit2013-REALBIN.cpp:11:31: warning: unused variable ‘x’ [-Wunused-variable]
  ll t,i,j,n,m,q,k,d,l,a,b,h,y,x,ans;
                               ^
garvit2013-REALBIN.cpp:14:6: warning: unused variable ‘c’ [-Wunused-variable]
  int c;
      ^
+ set +x
Successful
[simon@simon-laptop][13:40:03]
[~/devel/hackerrank/otherpeoples]>echo "1                                                       
1 8589934592" | ./a.out
garvit2013-REALBIN.cpp:31:15: runtime error: shift exponent 33 is too large for 32-bit type 'int'
No

Easy way if someone wants, (n & (n - 1)) gives us 0 if n^k is possible, or just do a bit count, if bit count is equal to 1 then print Yes else No because a single set bit is equal to power of 2

void solve(){

long long a,b;
cin>>a>>b;


if( (b &(b - 1)) ==  0){
    cout<<"Yes"<<endl;
}
else
    cout<<"No"<<endl;

}

@admin @cherry0697 in Case 1, “is divisible by X.” this should be p instead of X.

Please read the question properly. Chef can give any positive number but it’s Divyam’s choice to add or subtract.
Let me show how we’ll reach 0 or 1 from 15/16.
If X = 15/16 and chef gave 1/16, then upon addition it will become 1 and 7/8 if subtracted.
Once we reach 7/8, then chef will give 1/8. Add → 1, Subtract ->3/4
From 3/4 (chef can give 1/4), Add → 1, Subtract → 1/2
From 1/2 (chef can give 1/2), Add → 1, Subtract → 0.
This is how we are reaching 0 or 1 at the end. At every step, we have 2 choices i.e add or subtract, addition will lead convergence to 1 and subtraction to 0.
I hope you got the point. You may try for other cases like 15/32, 3/16 etc.

1 Like

How the new numerator will be A mod p+A1 mod p in case 1 of editorial.Could u explain?

I am wondering if the testcase was A= 3 and B= 12 so in that casr our code will gives answer no for this and it should be YES for this because 3/12 = 1/4 that is 0.25 which is valid answer. Our code is only dividing denominator continuously by 2 and checking . How it would be considering this case where there is a common factor between numerator and denominator

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