REALBIN - Editorial

Can someone please tell me what are the moves for the following
A=5 B=16?

use fast io in int main function and “\n” in place of endl rest everything is ok.

@pm_5289 First, you have to either add or subtract 1/16 then it would either become 1/4 or 3/8. Then if it becomes 1/4 and we add 1/4 to it it would become 1/2 (we can’t subtract as it would then become zero). then if once we got 1/2 we can take 1/2 and no matter what operation we do we would get either 0 or 1. Now moving on to the second case i.e, 3/8, we can give another 3/8, and then it would become 3/4 (as we can’t subtract as it would give us zero) then if we take 1/4 then it would become 1/2 (as if we would add 1/4 it would have become 1) then once it becomes 1/2 we can simply take the other number as 1/2 and then no matter what the operation would be it’s the guarantee that it would give either zero or 1.

1 Like

why didn’t it worked with the concept of prime numbers.
Like all primes expect 2 will cause “No”.

Yes prime numbers other than 2 will give no but numbers which arent prime will also give no
Ex:-
9/10 7/40

public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) 
        {
            int a = sc.nextInt();
            int b = sc.nextInt();
            System.out.println((b&(b-1)) == 0 ? "Yes":"No");
        }
    }

what is wrong with my code, it is giving TLE…I couldn’t reduce after this…CC OP!

@surajkrmohanty use fast Input & output, I did the same mistake and hence wasn’t able to solve this problem during the contest but when i checked other’s people solution having correct verdict they all have used the fast input &output. you can also check my solution : CodeChef: Practical coding for everyone

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