# REALBIN - Editorial

Setter: Divyam Singal
Tester: Felipe Mota
Editorialist: Aman Dwivedi

Easy

Observation

# PROBLEM:

Chef and Divyam are playing a game. They start with a rational number X, such that 0<X<1.

In each turn, Chef chooses a positive real number Y. Then Divyam either adds or subtracts Y to X. So X is replaced with either X+Y or X−Y. If this number becomes 0 or 1, then Chef wins. Otherwise, the game continues.

You are given X, and you have to determine whether Chef can win in a finite number of moves. More formally, does there exist a finite number N so that Chef has a strategy that is guaranteed to win in at most N moves?

Here, X will be given in the form \frac{A}{B}, where A and B are positive integers, A<B and gcd(A,B)=1.

# HINT

Spoiler

Chef will win only and only if the denominator B can be expressed in the form of 2^X.

# EXPLANATION:

As we know Divyam can either adds or subtracts Y to X. If Chef wants to win in only one move then the result of X-Y should be 0 and the result of X+Y should be 1, then only Chef could win. In all other cases, Divyam is able to perform the operation which doesn’t result in 0 or 1.

Let us find the value of X:

X-Y =0 \\ X+Y = 1

Solving these two equations we get:

X = \frac{1}{2}

Hence our ultimate goal is to make X=\frac{1}{2}. Let us see when we will be able to achieve this value.

Let us represent the given denominator B in prime factorization format. Then there will be two cases possible:

Case 1: There exists some prime number p greater than 2 which is a factor of B

As our ultimate goal is to reduce the denominator to 2. Let us see if we would be able to make the denominator equal to 2. Since A and B are coprime to each other it means that p is not a factor of A

But we would be only able to vanish this p from the denominator only and only when the numerator becomes divisible by p. Hence the goal of Divyam would be to never make the numerator divisible by p while Chef goal is opposite to that of Divyam.

Let us see what happens when Chef gives Divyam a number Y. Let us represent this number Y in the form \Large\frac{A_1}{B}

Why Denominator is B

Although we can use any value in the denominator other than B. But the most optimal choice for Chef is to choose such a number Y whose denominator is the same as that of number X. Because choosing value other than B would unnecessarily increase the prime factors of denominator while we are looking to vanish those prime factors;

Now suppose Chef chooses a number \Large\frac{A_1}{B} and gives it to Chef such that A-A_1 is divisible by X. It means that:

(A-A_1) \hspace{0.1cm} mod \hspace{0.1cm} p = 0 \\ A \hspace{0.1cm} mod \hspace{0.1cm} p -A_1 \hspace{0.1cm} mod \hspace{0.1cm}p =0 \\

That means:

A \hspace{0.1cm} mod \hspace{0.1cm} p = A_1 \hspace{0.1cm} mod \hspace{0.1cm} p \hspace{1cm} -- \hspace{0.1cm} (i)

Let us see what happens if Divyam decides to add Y, then whether (A+A_1) is divisible by p or not. The new numerator will be:

A \hspace{0.1cm} mod \hspace{0.1cm} p + A_1 \hspace{0.1cm} mod \hspace{0.1cm} p

Substituting the value of A_1 mod p from equation (i), we get:

2 *A\hspace{0.1cm} mod \hspace{0.1cm} p

The maximum value that A mod p can achieve is p-1 and the minimum value that it can get is 1. Hence we can rewrite it as:

2 \le 2*A \hspace{0.1cm} mod \hspace{0.1cm} p \le 2*(p-1)

Since there exists no number which is even and less than p and is divisible by p. It means that Divyam had a choice to perform addition when (A-A_1) is divisible by p.

Similarly, we can prove that when (A+A_1) is divisible by p, then Divyam has a choice to perform subtraction.

Therefore, in this case, we won’t be able to reduce the denominator to 2 and hence Chef won’t be able to win.

Case 2: The only prime number that divides the denominator is 2

Let us see the same thing here too. Suppose Chef chooses a number \Large\frac{A_1}{2} and gives it to Chef such that A-A_1 is divisible by 2. Then using the above proof we can say that:

A \hspace{0.1cm} mod \hspace{0.1cm} 2 = A_1 \hspace{0.1cm} mod \hspace{0.1cm} 2 \hspace{1cm} -- \hspace{0.1cm} (ii)

Let us again see what happens if Divyam decides to add Y, then whether (A+A_1) is divisible by 2 or not. The new numerator will be:

A \hspace{0.1cm} mod \hspace{0.1cm} 2 + A_1 \hspace{0.1cm} mod \hspace{0.1cm} 2

Substituting the value of A_1 mod 2 from equation (ii), we get:

2 *A\hspace{0.1cm} mod \hspace{0.1cm} 2

The only possible value of A mod 2 is 1. When we multiply A mod p by 2 we get 2 and hence that is divisible by 2. Hence Divyam has no choice left to prevent the denominator from getting divisible by 2. Hence after a finite number of moves, we would be able to reduce the denominator to 2.

Therefore Chef will win in this case.

# TIME COMPLEXITY:

O(log2(N)) per test case

# SOLUTIONS:

Setter
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define vll vector<ll>
#define ld long double
#define pll pair<ll,ll>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define oset tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define osetll tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ook order_of_key
#define fbo find_by_order
const int MOD=1000000007; //998244353;
long long int inverse(long long int i){
if(i==1) return 1;
return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
if(b==0) return 1;
if(b==1) return a%MOD;
ll temp=POW(a,b/2);
if(b%2==0) return (temp*temp)%MOD;
else return (((temp*temp)%MOD)*a)%MOD;
}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll t;
cin>>t;
for(int i=0;i<t;i++)
{
ll a,b;
cin>>a>>b;
ll flag=0;
for(int i=1;i<60;i++)
{
if(b==(1ll<<i))
{
flag=1;
break;
}
}
if(flag==1) cout<<"Yes";
else cout<<"No";
cout<<"\n";
}
}


Tester
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
long long readInt(long long l,long long r,char endd){
long long v;
cin >> v;
return v;
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}
long long TEN(int p){ long long r = 1; while(p--) r *= 10; return r; }
long long gcd(long long a, long long b){
while(b) a %= b, swap(a, b);
return a;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
while(t--){
long long a = readIntSp(1, TEN(18));
long long b = readIntLn(1, TEN(18));
assert(a < b && gcd(a, b) == 1);
while(b % 2 == 0) b /= 2;
cout << (b == 1 ? "Yes\n" : "No\n");
}
return 0;
}


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

#define int long long

void solve()
{
int a,b;
cin>>a>>b;

while(b%2==0)
b/=2;

if(b==1)
cout<<"Yes"<<"\n";
else
cout<<"NO"<<"\n";
}

int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);

int t;
cin>>t;

while(t--)
solve();

return 0;
}

3 Likes

My first code was very similar to the editorialist’s solution, yet I was getting a TLE. I had wasted a lot of time on this question finding shorter ways to find if a number is of form 2^x and did around 10 submissions every one of which was a TLE. Can anyone explain why I was getting TLE every time.

#include<iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
ll t;
cin >> t;
while(t--){
ll a,b;
cin >> a >> b;

while(b%2==0){b /= 2;}
if(b == 1){cout << "Yes";}
else{cout << "No";}
cout << endl;
}

return 0;
}



fastIO

1 Like

Have you tried using Fast I/O
ios_base::sync_with_stdio(false);
cin.tie(0);

1 Like

The endl is causing the problem as it causes the cout buffer to flush before every output which takes a lot of time. Use \n instead of endl.

2 Likes

I think the number can be as high as 10^18 so the only possible way was to calculate all powers of 2 upto 10^18 as prefix at start of program and using that you we can evaluate .
But i am not sure if it can work without it also.

I did the exactly same thing and stored the values in a map, but its giving me wrong answer although my logic is absolutely correct.

yeah… I’ve used that in my next submission, but no use

yeah… even tried that way… but no use

But can’t we make it 1 in one move everytime by selecting (b-a) /b as we had to make it 1 Or 0 any one of this so why this does not work?

basically dont use endl it will cause flush operation and since A and B were <= 10^18 which is a very big number it was taking a lot time to accept input
cin wastes time synchronizing itself with the underlying C-library’s stdio buffer

3 Likes

I don’t understand Codechef. While all this time, I have never got a TLE in Codeforces , I get that only in Codechef.

6 Likes

True

Omg it worked.
Using “\n” instead of endl actually worked.
Cant believe this
using endl - TLE
using “\n” - 0.2 sec

i got ac in python after probably 10 tries using this way.

yep, it worked. Thanks

denominator should be in formate of 2^x 5^y
in editorial solution why only 2 is considered
a=1 b=5
a/b = 0.2
5 also should be considered right?