CRCLJUMP: Need help

help
1

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.

2

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.

Code 
#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
3

Got it. Thanks for the explanation mate.