PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Ildar Gainullin
Tester: Nikolay Budin
Editorialist: Alei Reyes
DIFFICULTY:
Simple
PREREQUISITES:
Bitwise operations
PROBLEM:
You are given three non-negative integers x, y, n.
Find the number of integers z, such that 0 \leq z \leq n and (x \oplus z) < (y \oplus z).
QUICK EXPLANATION:
- Brute force all possible suffixes for which z[i] \neq n[i], and z[j]=n[j] for all j \gt i.
- If z[i..31] \oplus x[i..31] \lt z[i..31] \oplus y[i..31], then there are 2^i ways of filling the first i bits of z.
- If z[i..31] \oplus x[i..31] = z[i..31] \oplus y[i..31], then there are 2^{i-1} ways of filling the first i bits of z.
EXPLANATION:
In problems involving bitwise operations is useful to consider the binary representation of intergers. From now on we’ll represent the integers as binary strings of length 32, for example B = 13 = 1011000..000 and B[0]=1, B[1]=0, B[2..4]=110. Note that the string is given from least significant bit to most significant bit.
For simplicity let’s assume that z \lt n. We can check the case z=n as an special case. Also we can consider that x \neq y, because there is no valid z when x = y.
Let i be the rightmost (most significant) position in which z[i] \neq n[i], then the following holds:
- z[j]=n[j] for each j \gt i, i.e z and n have the same suffix starting from i+1.
- z[i]=0 and n[i]=1, because z \lt n
To find the number of possible z, we can brute force all possible i from most significant bit to less significant bit.
The problem is now reduced to count the number of distinct values of z, such that x \oplus z \lt y \oplus z, given that we know a suffix (with length 32-i) of z.
We don’t know the first i bits of z, but is possible that given the last 32-i bits we can be sure that z \oplus x is greater or smaller than z \oplus y, For example in the following picture we can be sure that z \oplus x \gt z \oplus y because it has a bit of higher order.
i
n = [*********][110]
z = [?????????][010]
x = [010110110][101]
y = [101010100][011]
P = z^x = [?????????][111]
Q = z^y = [?????????][001]
Let P= z \oplus x and Q=z \oplus y, there are three cases:
- P[i..31] \gt Q[i..31], it doesn’t matter how we fill the first i bits of z, is not possible to make P \lt Q.
- P[i..31] \lt Q[i..31], it doesn’t matter how we fill the first i bits of z, P will always be smaller than Q, there are 2^i ways of filling the first i bits.
-
P[i..31] = Q=[i..31], that means x and y have the same suffix, to make P smaller than Q, we have to look for the largest index j in which x[j] \neq y[j]. There are two possibilities:
- x[j]=1, y[j]=0: we can set z[j]=1.
-
x[j]=0, y[j]=1: we can set z[j]=0.
We have the freedom to set an arbitrary value to the other indices different than j, so there are 2^{i-1} different ways.
SOLUTIONS:
Setter's Solution
int main() {
auto f = [&] (int n, int i) {
return ((n >> (i + 1)) << i) + max(0, n % (1 << (i + 1)) - (1 << i) + 1);
};
int t;
cin >> t;
while (t--) {
int x, y, n;
cin >> x >> y >> n;
if (x == y) {
cout << 0 << '\n';
} else {
for (int i = 30; i >= 0; i--) {
if (((x ^ y) >> i) & 1) {
if (x > y) {
cout << f(n, i) << '\n';
} else {
cout << n + 1 - f(n, i) << '\n';
}
break;
}
}
}
}
}
Tester's Solution
void solve() {
int x, y, n;
cin >> x >> y >> n;
if (x == y) {
cout << "0\n";
return;
}
auto calc = [&](int pref, int left_len) {
if ((x & ~((1 << left_len) - 1)) != (y & ~((1 << left_len) - 1))) {
if (((x & ~((1 << left_len) - 1)) ^ pref) < ((y & ~((1 << left_len) - 1)) ^ pref)) {
return 1 << left_len;
}
return 0;
}
return 1 << (left_len - 1);
};
int ans = 0;
int pref = 0;
for (int i = 29; i >= 0; --i) {
if (n & (1 << i)) {
ans += calc(pref, i);
pref |= 1 << i;
}
}
ans += calc(pref, 0);
cout << ans << "\n";
}
