REALBIN - Editorial


Contest Division 1
Contest Division 2
Contest Division 3

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






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.



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


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.


O(log2(N)) per test case


#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()
    ll t;
    for(int i=0;i<t;i++)
        ll a,b;
        ll flag=0;
        for(int i=1;i<60;i++)
        if(flag==1) cout<<"Yes";
        else cout<<"No";

#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;
		char g=getchar();
		if('0'<=g && g<='9'){
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);

			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
				x= -x;
			assert(l<=x && x<=r);
			return x;
		} else {
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
		char g=getchar();
	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(){
	int t = readIntLn(1, TEN(6));
		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;

using namespace std;

#define int long long

void solve()
  int a,b;



int32_t main()

  int t;


return 0;

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 <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
     ll t;
     cin >> 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;


1 Like

Have you tried using Fast I/O

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.


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


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



“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


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