PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: emptypromises
Tester and Editorialist: iceknight1093
DIFFICULTY:
2577
PREREQUISITES:
Familiarity with bitwise operations and binary representations
PROBLEM:
Given L and R, find the number of integers x such that there exist L \leq a \leq b \leq R satisfying a+b = a\oplus b = x.
EXPLANATION:
First off, a + b = a\oplus b means that a and b must have completely disjoint binary representations, i.e, a\ \&\ b = 0.
With that in mind, let’s go over the subtasks.
Subtask 1
The limits here are very small, simply iterate over all pairs of (a, b), and if they satisfy the condition insert their sum into a set.
The answer is the size of the set.
The trivial implementation of this takes \mathcal{O}((R - L)^2 \log {(R - L)}) time, which is good enough.
Subtask 2
Here, we have L = 0 and R = 2^k - 1, i.e, all numbers with at most k significant bits.
It’s possible to make every number from L to R here, since to make x we can choose a = 0 and b = x.
Making anything \gt R is impossible, because the xor of two k-bit numbers cannot have \gt k significant bits.
So, the answer is the length of the range [0, R], which is R+1.
Note that R+1 = 2^k, so the answer essentially says we can make all k-bit strings.
Subtask 3
Here, we still have L = 0, though we might not have R = 2^k - 1.
With the same logic as the previous subtask, we can certainly make all x in the range [0, R].
However, we might now be able to reach x \gt R as well (for example, if R = 2 we can reach 3 = 1+2 = 1\oplus 2).
In fact, if R is a k-bit number, we can reach all the k-bit numbers!
Proof
Let R be a k-bit number, i.e, k is the smallest integer such that R \leq 2^k - 1.
Then, certainly we must have 2^{k-1} \leq R.
Any k-bit integer x\geq 2^{k-1} can be reached by choosing b = 2^{k-1} and a = x - b.
Note that this works because a \lt 2^{k-1}.
Numbers \leq R can be formed trivially by (0, x) as noted eariler; and this method allows us to form all the numbers from R+1 to 2^k - 1, so we’re done.
This gives us a simple solution: if R is a k-bit integer, the answer is just 2^k.
Finding k requires us to find the highest set bit in R, which can be done by just iterating k from 0 — it’ll take \mathcal{O}(\log R) time which is good enough.
Subtask 4
The constraints here allow for a linear (or close to linear) solution.
Note that any valid x must be \leq 2R.
So, let’s iterate over each x from 0 to 2R and see if we can make it.
If x = 0, then we can make it with (0, 0) if L = 0, and can’t make it otherwise.
If x \gt 0, then we can write its binary representation as x = 2^{p_1} + 2^{p_2} + \ldots + 2^{p_m} where p_1 \gt p_2 \gt \ldots \gt p_m.
To write x = a\oplus b = a + b, we need to distribute the bits p_1, p_2, \ldots, p_m to a and b.
Clearly, since b is the larger one, it must receive 2^{p_1}.
After this, it’s best to give all remaining 2^{p_i} to a, since:
- Increasing b too much might make it exceed R
- Keeping a too small might leave it \lt L
So, the best chance we have is with a = 2^{p_2} + 2^{p_3} + \ldots + 2^{p_m} and b = 2^{p_1}.
That is, b = 2^{p_1} and a = x \oplus b.
Form these a and b, and check if they both lie in [L, R].
If they do, increase the answer by 1.
The check for each x can be done in \mathcal{O}(1) or \mathcal{O}(\log x), and we check upto 2R different values of x so this takes \mathcal{O}(R\log R) time, which is good enough.
Subtask 5
Now, L and R are too large for any linear-type solutions to work.
Let’s look back at how we solved subtask 4:
- We fixed a value of x between 1 and 2R (0 was special-cased out)
- We found the highest bit of x and gave it to b; and gave all the other bits of x to a
- Then, we checked if this a and b were in range [L, R].
Notice the second point in particular: the only b we care about are powers of 2.
So, let’s fix b as a power of 2 in the range [L, R] and see which values of a are valid, as per our algorithm.
- First off, by our construction we must have a \lt b.
- We also must have a \geq L.
- It’s not hard to see that any such a is valid; i.e, we can choose any a in the range [L, b-1].
The length of this range is b - L.
This gives us a pretty simple algorithm:
- Fix the value of b to some power of 2 that lies in [L, R].
- Then, add b - L to the answer.
If L = 0, add 1 to the answer since we can also form x = 0.
Since we only care about powers of 2 that don’t exceed R, we check \log R of them.
So, this algorithm takes \mathcal{O}(\log R) time, which is fast enough to get AC.
TIME COMPLEXITY
\mathcal{O}(\log R) per test case.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
assert(1 <= T && T <= 1e5);
while (T--) {
long long l, r;
cin >> l >> r;
assert(0 <= l && l <= r && r <= 1e18);
long long ans = 0;
for (int b = 0; b < 60; b++) {
long long msb = (1LL << b);
if (l <= msb && msb <= r) {
ans += msb - l;
}
}
if (l == 0) {
ans++;
}
cout << ans << '\n';
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
l, r = map(int, input().split())
ans = 1 if l == 0 else 0
for pw in range(60):
if 2**pw > r: break
if 2**pw < l: continue
ans += 2**pw - l
print(ans)