REALBIN - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

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

DIFFICULTY

Easy

PREREQUISITES

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 readString(int l,int r,char endd){
	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){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,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);
	int t = readIntLn(1, TEN(6));
	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 :expressionless:

yeah… even tried that way… but no use :frowning:

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

for more info Cin-Cout vs Scanf-Printf - GeeksforGeeks

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

“I saw your answer before it was withdrawn”
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 :slight_smile:

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?
check this link:-

yup it worked

Its so unfair i used the right logic but using endl instead of /n cost me a question :sob:
And also is it just me that the question were easier than previous ones or maybe i was lucky to come up with good observation

2 Likes

Problem: From Rational to Binary
Submission
Please can anybody point out what is wrong in my solution. May be i am missing something!!