PROBLEM LINK:
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.