PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Jeevan Jyot Singh
Tester: Harris Leung
Editorialist: Trung Dang
DIFFICULTY:
1507
PREREQUISITES:
XOR
PROBLEM:
JJ has three integers A, B, and N. He can apply the following operation on A:
- Select an integer X such that 1 \le X \lt N and set A := A \oplus X. (Here, \oplus denotes the bitwise XOR operation.)
JJ wants to make A equal to B.
Determine the minimum number of operations required to do so. Print -1 if it is not possible.
EXPLANATION:
Let X = A \oplus B, and for the sake of editorialist’s sanity we decrease N by 1. We now want to achieve X from XOR-ing as few elements no greater than N as possible.
There are 4 cases:
- X = 0. Answer is 0.
- X \le N. Answer is 1.
- \lfloor \log_2(X) \rfloor = \lfloor \log_2(N) \rfloor . Answer is 2. This semantically means the largest bit of X is equal to the largest bit of N, which means we can construct X by 2^{\lfloor \log_2(X) \rfloor} with some other value less than 2^{\lfloor \log_2(X) \rfloor}.
- Otherwise. Answer is -1. This happens in the case where the largest bit of X is larger to the largest bit of N, which means we cannot create this largest bit by any means.
TIME COMPLEXITY:
Time complexity is O(1).
SOLUTION:
Setter's Solution
#ifdef WTSH
#include <wtsh.h>
#else
#include <bits/stdc++.h>
using namespace std;
#define dbg(...)
#endif
#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;
const long long INF = 1e18;
const int N = 1e6 + 5;
// -------------------- Input Checker Start --------------------
long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, fi = -1;
bool is_neg = false;
while(true)
{
char g = getchar();
if(g == '-')
{
assert(fi == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9')
{
x *= 10;
x += g - '0';
if(cnt == 0)
fi = g - '0';
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if(g == endd)
{
if(is_neg)
x = -x;
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(false);
}
return x;
}
else
{
assert(false);
}
}
}
string readString(int l, int r, char endd)
{
string ret = "";
int cnt = 0;
while(true)
{
char g = getchar();
assert(g != -1);
if(g == endd)
break;
cnt++;
ret += g;
}
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, ' '); }
void readEOF() { assert(getchar() == EOF); }
vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[i] = readIntSp(l, r);
a[n - 1] = readIntLn(l, r);
return a;
}
// -------------------- Input Checker End --------------------
void solve()
{
int a = readIntSp(0, (1 << 30) - 1);
int b = readIntSp(0, (1 << 30) - 1);
int n = readIntLn(1, (1 << 30));
int z = a ^ b;
if(z == 0)
cout << 0 << endl;
else if(z < n)
cout << 1 << endl;
else
{
int msb = -1;
for(int i = 30; i >= 0; i--)
{
if(z >> i & 1)
{
msb = i;
break;
}
}
if((1 << msb) < n)
cout << 2 << endl;
else
cout << -1 << endl;
}
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T = readIntLn(1, 1000);
for(int tc = 1; tc <= T; tc++)
{
// cout << "Case #" << tc << ": ";
solve();
}
readEOF();
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=2e5+5;
int n;
ll a[N];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;
while(t--){
ll a,b,n;cin >> a >> b >> n;
ll z=1;
while(z<n) z*=2;
if((a^b)==0) cout << "0\n";
else if((a^b)<n) cout << "1\n";
else if((a^b)<z) cout << "2\n";
else cout << "-1\n";
}
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int a, b, n; cin >> a >> b >> n; --n;
int x = a ^ b;
if (x == 0) {
cout << "0\n";
} else if (x <= n) {
cout << "1\n";
} else if (n != 0 && __lg(x) == __lg(n)) {
cout << "2\n";
} else {
cout << "-1\n";
}
}
}