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 ), 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!
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;
}
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.
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.
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?
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;
}