# XSORT - Editorial

Authors: dannyboy1204
Testers: tabr, yash_daga
Editorialist: iceknight1093

TBD

None

# PROBLEM:

You have an array A of length N.
In one move, you can pick i and j such that A_i \neq A_j and set them both to A_i \oplus A_j.

Find a sequence of at most 20\cdot N moves that results in a sorted array.

# EXPLANATION:

The XOR operation is a bit of a red herring: there exists a solution that is completely independent of the replacement function.

### A simpler case

First, let’s deal with a simpler version of the problem, where N is always a power of two; say N = 2^K.

In this case, we can not only sort the array, we can make all the array elements equal using K\cdot 2^{K-1} operations:

• First, recursively make the first and second halves of the array equal, since they’re also power-of-two sized.
• Then, perform the operations (1, N/2+1), (2, N/2+2), (3, N/2+3), \ldots, (N/2, N).
Since the first half is equal and the second half is equal, the entire array is now equal.

It’s easy to see that this uses K\cdot 2^{K-1} moves: there are K levels of the recursion, and each one uses N/2 = 2^{K-1} operations in total.

### Solving for any N

When N isn’t a power of 2, we can in fact use the above method as a subroutine.

First, perform N/2 operations to make A a palindrome: (1, N), (2, N-1), (3, N-2), \ldots, (N/2, N/2+1)

Now, let x be the largest power of 2 that’s \leq N.

Let’s first make the first x elements equal using the earlier method, and then make the last x elements equal.
Note that this gives us either a sorted array or a reverse-sorted array, with at most two distinct elements.

if it’s sorted, we’re done.
If it’s reverse-sorted, note that our method for powers of 2 is symmetric with respect to reversing the array.
So, we can instead make the last x elements equal, then make the first x elements equal: this is guaranteed to give us a sorted array.

This way, we use the K\cdot 2^{K-1} method twice, with a further N/2 operations.
N \leq 10^5 gives us K \leq 16, so the number of operations we use is bounded by 2\cdot 16\cdot N/2 + N/2 \leq 17N, which is good enough.

# TIME COMPLEXITY

\mathcal{O}(N\log N) per test case.

# CODE:

Setter's code (C++)
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define fi first
#define se second
#define mat vector<vector<ll>>
using namespace std;
void db() {cout << '\n';}
template <typename T, typename ...U> void db(T a, U ...b) {cout << a << ' ', db(b...);}
#ifdef Cloud
#define file freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define file ios::sync_with_stdio(false); cin.tie(0)
#endif
mt19937 rng(SEED);
const int N = 1e5 + 1, mod = 998244353, inf = 1ll << 60;
int a[N];
vector<pair<int, int>> v;
void work(int l, int r){
if (l == r) return;
int mid = l + r >> 1;
work(l, mid), work(mid + 1, r);
for (int i = 0; i < r - mid; i++) {
if (a[l + i] == a[mid + 1 + i]) continue;
a[l + i] = a[mid + 1 + i] = a[l + i] ^ a[mid + 1 + i];
v.push_back({l + i, mid + 1 + i});
}
}
int f(int n){
return __lg(n) * n / 2;
}
void solve(){
int n;
cin >> n;
vector<pair<int, int>> ans;
for (int i = 0; i < n; i++) cin >> a[i];
int k = 1;
while (k * 2 < n) k *= 2;
int mid = k * 2 - n;
for (int i = 0; i < n - 1 - i; i++){
if (a[i] == a[n - 1 - i]) continue;
ans.push_back({i + 1, n - i});
a[i] = a[n - 1 - i] = a[i] ^ a[n - 1 - i];
}
work(0, k - 1);
work(n - k, n - 1);
for (auto i : v){
if (a[0] > a[n - 1]){
ans.push_back({n - i.fi, n - i.se});
}
else{
ans.push_back({i.fi + 1, i.se + 1});
}
}
v.clear();
cout << ans.size() << '\n';
for (auto i : ans) cout << i.fi << ' ' << i.se << '\n';
}
signed main(){
file;
int t;
cin >> t;
while (t--) solve();
}

Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct input_checker {
string buffer;
int pos;

const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";

input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}

int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
now++;
}
return now;
}

assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
// cerr << res << endl;
return res;
}

string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}

int readInt(int minv, int maxv) {
assert(minv <= maxv);
assert(minv <= res);
assert(res <= maxv);
return res;
}

long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
assert(minv <= res);
assert(res <= maxv);
return res;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}

assert((int) buffer.size() == pos);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
input_checker in;
int sn = 0;
while (tt--) {
vector<int> a(n);
for (int i = 0; i < n; i++) {
}
int k = 1;
while (2 * k <= n) {
k *= 2;
}
vector<pair<int, int>> ans;
auto F = [&](int x, int y) {
if (a[x] == a[y]) {
return;
}
ans.emplace_back(x, y);
a[x] = a[y] = a[x] ^ a[y];
};
function<void(int, int)> D = [&](int l, int r) {
if (l + 1 >= r) {
return;
}
int m = (l + r) >> 1;
for (int i = l; i < m; i++) {
F(i, i + m - l);
}
D(l, m);
D(m, r);
};
for (int i = 0; i < n - 1 - i; i++) {
F(i, n - 1 - i);
}
auto ansb = ans;
D(0, k);
D(n - k, n);
if (!is_sorted(a.begin(), a.end())) {
assert(is_sorted(a.rbegin(), a.rend()));
for (int i = (int) ansb.size(); i < (int) ans.size(); i++) {
ans[i].first = n - 1 - ans[i].first;
ans[i].second = n - 1 - ans[i].second;
}
}
cout << ans.size() << '\n';
for (auto [x, y] : ans) {
cout << x + 1 << " " << y + 1 << '\n';
}
}
assert(sn <= 1e5);