REALBIN - Editorial

editorial
, , ,
57 
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

58 
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

59

Consider the test input:

1
1 8589934592
60

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

61

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
62

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;

}

63

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

64

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
65

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

66

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

67

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

2 Likes
68

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

69

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

70

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
71

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

73

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;

}

74
1 Like
75

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
76

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

77

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