PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: rainb0ysimp
Tester: jay_1048576
Editorialist: iceknight1093
DIFFICULTY:
2501
PREREQUISITES:
Observation
PROBLEM:
A special permutation of length N is a sequence of N non-negative integers that contains every integer in [L, L+N-1] exactly once.
You have a permutation of length N.
An integer x is called valid if [A_1\oplus x, A_2\oplus x, \ldots, A_N\oplus x] is a special permutation of length N.
Answer Q queries. In each query, you’re given L and R — find the number of valid integers in the range [L, R].
EXPLANATION:
N is way too large for anything other than \mathcal{O}(\log N) or \mathcal{O}(1) per query to be viable.
In counting problems like this, often it is useful to be able to nicely characterize the items we’re counting — that is, we should first attempt to figure out what a valid x looks like.
Given that the operation at hand is bitwise XOR, it makes sense to look at binary representations.
So, suppose N is a k-bit integer.
Then, it’s not hard to notice that:
- If x is such that all of its last k bits are 0, then x is valid.
This is because for such an x, we have x\oplus i = x + i for i \leq N.
So, the sequence we end up with is [x+1, x+2, \ldots, x+N] which is a special permutation. - If x is such that all of its last k bits are 1, again x is valid.
For such an x, we have x\oplus i = x-i for i \leq N; once again giving us a special permutation.
In fact, these are the only valid types of x.
Proof
Only the first k bits of x matter here; so let’s discard the higher ones and consider x to be a k-bit integer, i.e, 0 \leq x \lt 2^k.
We’ve already shown that x = 0 and x = 2^k - 1 are valid; with our claim being that no others are valid.
First, if k = 1 then no other x exists since 2^k-1 = 1; so the claim is already true.
Now let’s look at k \geq 2.
Consider two separate cases: either x has the (k-1)-th bit set; or it doesn’t.
That is, either 0 \lt x \lt 2^{k-1}; or 2^{k-1} \leq x \lt 2^k-1.
Case 1: 0 \lt x \lt 2^{k-1}
In particular, notice that this means x \lt N.
So, we’ll definitely have x\oplus x = 0 in our xor-ed sequence.
This means the only way it could form a special permutation is if we had everything in range [0, N-1].
However, we can see that we’re missing x itself from that range, since it can only be formed by 0\oplus x = x which we don’t have.
Such an x is thus invalid.
Case 2: 2^{k-1} \leq x \lt 2^{k}-1
Once again, the proof is similar.
It can be seen that our xor-ed sequence will contain 2^k - 1; and so once again the only way for it to form a special permutation is if we had the N consecutive integers ending at 2^k - 1.
However, x itself is one of these integers; and again we don’t have 0\oplus x = x in the xor-ed sequence.
Once again, such an x is invalid.
This completes the proof.
Now, given L and R, we need to count for each of the two types above, how many of them lie in range [L, R].
That’s not too hard with the following observations:
- The last k bits of x are 0 if and only if x is a multiple of 2^k.
The number of multiples of 2^k in [L, R] can be found using the formula \left\lfloor \frac{R}{2^k} \right\rfloor - \left\lfloor \frac{L-1}{2^k} \right\rfloor
This follows from the fact that for any a, b, there are \lfloor \frac{a}{b} \rfloor multiples of b that are \leq a. - The last k bits of x are 1 if and only if x+1 is a multiple of 2^k.
To count such numbers, we can instead just count multiples of 2^k in the range [L+1, R+1] using the above formula.
So, knowing k, each query can be answered in \mathcal{O}(1) time.
Finding k is easy in \mathcal{O}(\log N): just find the smallest integer k such that 2^k \gt N.
TIME COMPLEXITY
\mathcal{O}(\log N + Q) per testcase.
CODE:
Author's code (C++)
#include "bits/stdc++.h"
using namespace std;
#define int long long
void anubhav(){
int n, q;
cin >> n >> q;
int cnt = log2l(n) + 1;
int x = (1LL << cnt);
while(q--){
int l, r;
cin >> l >> r;
int rr = r / x;
int ll = l / x - (l % x == 0);
int ans = 2 * (rr - ll);
int u = ((l + x - 1) / x) * x;
int v = ((r + x - 1) / x) * x;
if(u - 1 < l || (u) == n) ans--;
if(v - 1 <= r && v - 1 >= l && v > r) ans++;
cout << max(0LL, ans) << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T = 1;
cin >> T;
while(T--) anubhav();
return 0;
}
Tester's code (C++)
/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 1000000007
int count(int n,int p,int x)
{
if(x<n)
return 0;
int ans = 2*(x/p);
if((x+1)%p==0)
ans++;
return ans;
}
void solve(int tc)
{
int n,q;
cin >> n >> q;
int p=1;
while(p<=n)
p*=2;
while(q--)
{
int l,r;
cin >> l >> r;
cout << count(n,p,r)-count(n,p,l-1) << '\n';
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tc=1;
cin >> tc;
for(int ttc=1;ttc<=tc;ttc++)
solve(ttc);
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, q = map(int, input().split())
p = 2 ** len(bin(n)[2:])
while q > 0:
L, R = map(int, input().split())
q -= 1
ans = 0
# Multiples of p in [L, R]
ans += R//p - (L-1)//p
# k*p - 1 in [L, R] -> multiples of p in [L+1, R+1]
ans += (R+1)//p - L//p
print(ans)