Hey guys,

Need some help understanding the solution of this problem.

The question is straight forward but the submissions I went through are confusing and there’s no official editorial for this problem as well.

Any help is appreciated.

Hey guys,

Need some help understanding the solution of this problem.

The question is straight forward but the submissions I went through are confusing and there’s no official editorial for this problem as well.

Any help is appreciated.

We can calculate the number of moves needed for each player seperately.

Let the finish circle be at position 0. Then we start at position x+1, where x is the number of circles in front of us. In each move we can reduce our position by 2^k. So we need to write x+1 as a sum of distinct powers of 2. In fact there exists only one such solution, which is the binary representation of x+1. The number of jumps we have to make is the number of set bits in the binary representation of x+1. C++ gives us an inbuilt function to count set bits `__builtin_popcount(x)`

. So we just need to count the number of set bits in x+1 and y+1, and compare them.

```
#include <iostream>
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
void solve(){
int x,y;
cin>>x>>y;
x = __builtin_popcount(x+1);
y = __builtin_popcount(y+1);
if(x==y){
cout<<"0 0\n";
return;
}
if(x<y){
cout<<"1 "<<y-x<<"\n";
}
if(y<x){
cout<<"2 "<<x-y<<"\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
solve();
}
}
```

2 Likes

Got it. Thanks for the explanation mate.