PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: nskybytskyi
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Find a permutation P of the integers 1 to N such that P_i \neq i and \max_{i=1}^N \left( P_i \oplus i\right) is minimized.
For full score, also find the lexicographically maximum permutation.
EXPLANATION:
Let f(P) = \max_{i=1}^N \left( P_i \oplus i\right).
By looking at a couple extreme values of i, we can find lower bounds on this:
- Since P_N \neq N, there must be some index i \lt N such that P_i = N.
In particular, this means the minimum value of (i\oplus N) for 1 \leq i \lt N is a lower bound on the answer. - Looking at 1 and 2, we see that at least one of P_1\oplus 1 and P_2\oplus 2 should be \geq 3.
- This is because P_1\oplus 1 cannot be 0 or 1; and if it is 2 that would mean P_1 = 3.
But then P_2\oplus 2 cannot be 1 or 2, and so must be \geq 3.
- This is because P_1\oplus 1 cannot be 0 or 1; and if it is 2 that would mean P_1 = 3.
Let M = \displaystyle\min_{1\leq i\lt N}(i\oplus N).
From the above observations, we know for sure that f(P) \geq \max(M, 3) for any permutation P.
It turns out that this lower bound is tight.
To construct a valid permutation however, we need to understand what the value of M is a bit better.
Analysis on M
If N = 2^k, i.e N is a power of 2, then M = 2^k + 1 = N+1.
This is because, since N doesn’t share any set bits with numbers smaller than it, N\oplus i = N+i for all i \lt N.
To minimize this, of course we choose i = 1.
If N is not a power of 2, it can instead be seen that M = 2^x, where x is the lowest set bit in N. (Note that 2^x is equivalently the largest power of 2 that divides N.)
To see why: if we wanted to ensure that all bits \geq x are switched off in N\oplus i, then N and i must share the same set bits \geq x.
But x is the lowest set bit in N, meaning all of N's set bits are \geq x.
If i has all of these set too, i must be \geq N - a contradiction.
So, we certainly must have M \geq 2^x.
To achieve M = 2^x, choose i = N \oplus 2^x (which is \lt N since N has bit x set).
With that, we are ready to construct a permutation P.
The analysis on M gives us two cases already: either N is a power of 2, or it isn’t.
When N is a power of 2, almost any construction works - we’re forced to have P_1 = N and P_N = 1, but P_2, P_3, \ldots, P_{N-1} can be anything at all!
That leaves us with non-powers of 2.
Recall that we want to have f(P) = \max(M, 3), so once again we have two cases to consider: M \leq 3 and M \gt 3.
Let’s look at them separately.
Case 1: M <= 3
N isn’t a power of 2, so recall that M will be a power of 2 - the largest one dividing N, in fact.
This means M = 1 or M = 3, meaning either N is odd, or N = 4k+2 for some integer k\geq 1.
A useful fact to note here is that 2x \oplus (2x + 1) = 1 for any x \geq 0.
That is, an even integer xor-ed with its successor is 1 - this is easy to prove.
Using this, we obtain a simple construction:
- Arrange the first three elements appropriately - for example [3, 1, 2].
- Then, for each even integer \geq 4, set P_{2x} = 2x+1 and P_{2x+1} = 2x.
When N is odd, this construction already works.
When N is even (meaning it’s of the form 4k+2), we’ll have P_N = N+1 which isn’t allowed.
However, in this case, you may observe that N, N-1, N-2 can be arranged appropriately at the last three positions similar to [3, 1, 2] at the start, obtaining a XOR of \leq 3 and completing the construction.
Case 2: M > 3
Here, let M = 2^k for k \geq 2.
Set P_N = N \oplus M and P_{N\oplus M} = N, taking care of those positions.
Now, note that the part [1, 2, \ldots, (N \oplus M) - 1] will have odd length, so using the previous case we can force it to have XOR \leq 3 (which is \lt M).
Further, elements from (N\oplus M) + 1 to N-1 can in fact be arranged in any order at those indices (as long as P_i \neq i holds) - no two of these values can have a XOR that’s \gt M anyway.
This completes the construction, and we’re done!
The solution to XIN2, i.e, finding the lexicographically maximum permutation, can be found here.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
if ((n & (n-1)) == 0) { // Power of 2
cout << n << ' ';
for (int i = 2; i+1 < n; ++i) cout << i+1 << ' ';
if (n > 2) cout << 2 << ' ';
cout << 1 << '\n';
}
else {
vector<int> ans(n+1);
ans[1] = 2, ans[2] = 3, ans[3] = 1;
for (int i = 4; i <= n; i += 2) ans[i] = i+1, ans[i+1] = i;
if (n%4 == 2) {
ans[n] = n-1, ans[n-1] = n-2, ans[n-2] = n;
}
if (n%4 == 0) {
int shift = __builtin_ctz(n);
int k = n - (1 << shift);
ans[k] = n, ans[n] = k;
ans[k+1] = k+2, ans[k+2] = k+3, ans[k+3] = k+1;
}
for (int i = 1; i <= n; ++i) {
cout << ans[i] << ' ';
}
cout << '\n';
{
int bound = max(3, (1 << __builtin_ctz(n)));
for (int i = 1; i <= n; ++i)
assert((ans[i] ^ i) <= bound);
}
}
}
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
// For debugging and verification
int score(const vector<int>& p) {
int mx = 0;
const int n = p.size();
for (int i = 0; i < n; ++i) {
mx = max(mx, (i + 1) ^ p[i]);
}
return mx;
}
bool good(const vector<int>& p) {
const int n = p.size();
string seen(n, 0);
for (int i = 0; i < n; ++i) {
if (p[i] == i + 1 || p[i] < 1 || p[i] > n || seen[p[i] - 1]) {
return false;
}
seen[p[i] - 1] = 1;
}
return true;
}
vector<int> solve_mod_four(int n) {
// Lemma: max(p[i] xor i) >= 3
// Proof: assume p[i] xor i <= 2 for all i then
// - p[1] is either 1 xor 1 = 0 (invalid) or 1 xor 2 = 3
// - p[2] is either 2 xor 1 = 3 or 2 xor 2 = 0 (invalid)
// However, both p[1] and p[2] cannot be 3 at the same time
// The following construction achieves this lower bound for n != 0 (mod 4)
vector<int> p = {2, 3, 1};
// (n & 1) ? n : (n - 3) leaves last three elements for n = 4k+2
for (int k = 2; 2 * k < ((n & 1) ? n : (n - 3)); ++k) {
// (2k) xor (2k+1) = 1
p.push_back(2 * k + 1);
p.push_back(2 * k);
}
if (n % 4 == 2) {
// (4k) xor (4k+1) = 1
p.push_back(n - 1);
// (4k+1) xor (4k+2) = 3
p.push_back(n);
// (4k+2) xor (4k) = 2
p.push_back(n - 2);
}
assert(good(p) && score(p) == 3);
return p;
}
vector<int> solve_lsb(int n) {
// Lemma: max(p[i] xor i) >= lsb(n)
// where lsb denotes the least significant bit
// Proof: assume p[n] xor n < lsb(n)
// then p[n] >= n because its bits are equal to those of n
// in all positions greater than or equal to lsb
// However, the only number >= n in the permutation is n itself
// but having p[n] = n is invalid
// The following construction achieves this lower bound for all n != 2^k
const auto lsb = n & -n;
const auto small = solve_mod_four(n - lsb - 1);
const auto large = solve_mod_four(lsb - 1);
vector<int> p = small;
p.push_back(n);
for (const auto pi : large) {
p.push_back(pi + n - lsb);
}
p.push_back(n - lsb);
assert(good(p) && score(p) == lsb);
return p;
}
vector<int> solve_power_of_two(int n) {
// Lemma: max(p[i] xor i) >= n + 1 for n = 2^k
// Proof: p[n] xor n > n + 1
// The following construction achieves this lower bound for all n = 2^k
vector<int> p = {n};
for (int k = 1; 2 * k < n; ++k) {
// (2k) xor (2k+1) = 1
p.push_back(2 * k + 1);
p.push_back(2 * k);
}
p.push_back(1);
assert(good(p) && score(p) == n + 1);
return p;
}
vector<int> solve(int n) {
// casework
if (n == 2) {
return {2, 1};
} if (n % 4) {
return solve_mod_four(n);
} else if (n & (n - 1)) {
return solve_lsb(n);
} else {
return solve_power_of_two(n);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t; cin >> t; while (t--) {
int n;
cin >> n;
const auto p = solve(n);
for (auto pi : p) {
cout << pi << ' ';
}
cout << '\n';
}
}