GAMENUM - Editorial

PROBLEM LINK:

Contest
Practice

Author : John Zakkam
Testers : Jaymeet Mehta, Smit Mandavia, Taranpreet Singh and Aneesh D H.
Editorialist : John Zakkam

DIFFICULTY:

EASY

PREREQUISITES:

STL, Basic Mathematics.

PROBLEM:

Given two numbers A and B, you have to perform operations on only B, to get max value of A^B. Where ^ is bitwise XOR. The operation here is circular right shift.
Before performing any operation, you have to pad the binary representations of both A and B.

EXPLANATION:

The solution is just go on doing the given operation on B (as given in the question), keep a dummy variable for the operation in which max of A^B occurs.
In the end, just print the number of operations and max value of A^B.
There could be many ways of implementing the above approach, one is given below.

SOLUTIONS:

Setter's Solution in C++
    #include<bits/stdc++.h>
    #define nl cout << endl
    #define MAX 10e9
    #define e 1e-9
    #define ll unsigned long int
    #define ull unsigned long long ll
    #define vi vector<int>
    #define vl vector<ll>
    #define vc vector<vc>
    #define vs vector<string>
    #define vpl vector<pair<ll,ll>>
    #define vpc vector<pair<char,char>>
    #define vll vector<vector<ll>,ll>
    #define adj_list vector<vl>
    #define pll pair<ll,pair<ll, ll>>   
    #define clr(x) memset(x,0,sizeof(x))
    #define F first
    #define S second
    ll gcd(ll a,ll b) { if(a==0) return b; else return gcd(b%a,a);}
    ll factorial(ll n){return (n==1 || n==0) ? 1: n * factorial(n - 1);}
    #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    using namespace std;
     
    string binary(ll n)
    {
        string r;
        while(n!=0) {r=(n%2==0 ?"0":"1")+r; n/=2;}
        return r;
    }
     
    string padd(string x,ll max)
    {
        string y=x;
        ll s = max - x.length();
        for(ll i=0;i<s;i++)
            y="0"+y;
        return y;
    }
     
    ll xxor(string a,string b)
    {
        ll ans=0,y=0;
        string s;
        for(ll i=0;i<a.length();i++)
            s += (a[i]-'0')^(b[i]-'0')+'0';
        for(int i=0;i<s.length();i++) {
            ll x = s.length()-(i+1);
            ans = ans+(s[i]-'0')*(1ll<<x);
        }
            
        return ans;
    }
     
    void check()
    {
        ll a,b;
        cin >> a >> b;
        string aa,bb;
        aa = binary(a);
        bb = binary(b);
        int m = max(aa.length(),bb.length());
        aa=padd(aa,m);
        bb=padd(bb,m);
        ll maxx = 0,mini=0;
        for(ll i=0;i<bb.length();i++)
        {
            ll xx = xxor(aa,bb);
            if(maxx < xx)
                {maxx = xx;mini=i;}
            *rotate(bb.begin(),bb.begin()+(bb.length()-1),bb.end());
        }
        cout << mini << " " << maxx ;nl;
        return ;
    }
     
    int32_t main()
    {
        //auto start = chrono::steady_clock::now();
        fastio;
        ll t;
        cin >> t;
        while(t--)
            check();
        // auto end = chrono::steady_clock::now();
        // auto diff = end - start;
        // cout << chrono::duration <double, milli> (diff).count()*0.001 << "s" << endl;
        return 0;
    } 
Tester's Solution in Python
from sys import stdin,stdout
import time
test=int(stdin.readline())
start=time.time()
def permute(a):
    return a[-1]+a[:-1]
def padd(x,y):
    lx,ly=len(x),len(y)
    max_len=max(lx,ly)
    for i in range(lx,max_len):
        x="0"+x
    for i in range(ly,max_len):
        y="0"+y
    return x,y
for _ in range(test):
    A,B = map(int,stdin.readline().split())
    if (A<=100000 or B<=100000) :
        a=bin(A).replace("0b","")
        b=bin(B).replace("0b","")
        a,b=padd(a,b)
        perm_b=[b]
        for i in range(len(b)-1):
            perm_b.append(permute(perm_b[-1]))
        min_op=0
        a=int(a,2)
        max_xor=0
        for i in range(len(b)):
            xor=a^int(perm_b[i],2)
            if xor>max_xor:
                max_xor=xor
                min_op=i
        print(min_op,max_xor)
    else :
        print(1)

Another way of implementing in a different way can be found here.

Cool, If you find anything ambiguous or not-in-detail , please comment below.

2 Likes

The solution can be implemented using primitive data-types also in C++.
Refer to my solution here: Competitive-Programming/Code-Chef/Another-Game-of-Numbers at master · strikersps/Competitive-Programming · GitHub

1 Like

Thanks @striker22 for sharing.

1 Like