PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: munch_01
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Bitwise XOR
PROBLEM:
You’re given an array A, which you can rearrange as you like.
After rearranging, define an array B where B_i = A_1 \oplus A_2 \oplus \ldots \oplus A_i.
Find any rearrangement that ensures that B_i\neq 0 for every i \geq 1.
EXPLANATION:
Let’s start by trying to exclude some cases where there is obviously no solution.
First, if A_1 \oplus A_2\oplus\ldots\oplus A_N = 0, i.e the XOR of the entire array is already 0, then obviously no solution can exist.
Another case where no solution exists is when A contains only a single element (and has length \gt 1). That is, when A = [x, x, x, \ldots, x] for some integer x.
Here, there’s only one rearrangement, and the prefix XORs are [x, 0, x, 0, \ldots]; there’s no way to avoid getting a 0 at the second position.
That leaves us with the remaining cases, that is:
- N = 1, or
- N \gt 1, the XOR of A isn’t zero, and A contains at least two distinct elements.
N = 1 is trivial, so let’s focus on the second case.
As it happens, in this case a valid rearrangement always exists!
There are several constructions, below I’ll describe one of them.
Let C denote the answer array we’re creating. Initially, this is empty.
Suppose you take some random element x from A and append it to C.
There are a few things that can happen.
- It’s possible that the new prefix XOR is non-zero.
This is ideal, and if it happens, we’re happy - just continue on. - If the new prefix XOR is zero, we can’t append x.
Note that this means that the current prefix XOR must itself be x.
To deal with the ‘bad’ case, we once again look at a couple of situations.
First, suppose A contains some element other than x.
Here, we can choose any such element y\neq x from A and append it to C - since x\neq y we know that x\oplus y \neq 0, i.e the new prefix XOR isn’t 0.
Now that the length of C has increased by 1, we continue on.
Finally, we’re left with the case when there’s no choice: every remaining element is x.
Observe that the whatever element was appended in the previous step definitely cannot have been x - since the current prefix XOR (before we append our x) is itself x, if the last element was x then the prefix ending just before it would have a XOR of 0, which by construction we haven’t allowed.
So, let y\neq x be the last element.
Now, you can simply delete y from C, append every copy of x to C, and then append that single copy of y to the end!
This works because:
- The prefix XOR till just before y was x\oplus y.
- So, appending several copies of x to C keeps shifting the prefix XOR between x\oplus y and y, both of which we know to not be 0.
- Appending y at the end also can’t make the prefix XOR 0, since at that point we have the whole array (whose XOR we know to not be 0).
Notice that this construction allows us to really choose any remaining element x (and if it fails, any other element y).
For ease of implementation, you can for example always choose the minimum remaining element; and if it fails, the second minimum (or maximum).
To do this quickly, you’ll need a data structure that supports quick lookup of the minimum/maximum element, along with quick deletion - which is what a (multi)set does, for example.
It’s also possible to implement this in linear time without any data structures, which can be seen in the editorialist’s code below.
There are alternate constructions, which you may see in the author’s and tester’s code.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
int random(int l, int r){
return l + (RNG() % (r - l + 1));
}
void Solve()
{
int n; cin >> n;
vector <int> a;
set <int> s;
int xo = 0;
vector <int> ok;
map <int, int> cnt;
set <int> s1;
for (int i = 0; i < n; i++){
int x; cin >> x;
xo ^= x;
ok.push_back(x);
cnt[x]++;
s1.insert(x);
if (s.count(x)){
s.erase(x);
a.push_back(x);
} else {
s.insert(x);
}
}
if (xo == 0){
cout << -1 << "\n";
return;
}
if (n != 1 && s1.size() == 1){
cout << -1 << "\n";
return;
}
if (n == 1){
cout << xo << "\n";
return;
}
if (s.size() == 1){
// cout << 1 << "\n";
// return;
cout << xo << " ";
for (auto x : a){
if (x != xo){
cout << x << " ";
break;
}
}
for (auto x : a){
if (x == xo){
cout << x << " " << x << " ";
}
}
for (auto x : a){
if (x != xo){
cout << x << " ";
break;
}
}
bool skip = false;
for (auto x : a){
if (x != xo){
if (!skip){
skip = true;
} else {
cout << x << " " << x << " ";
}
}
}
cout << "\n";
return;
}
vector <int> b;
int curr = 0;
while (s.size()){
int h1 = *s.begin();
int h2 = *(--s.end());
if (curr != h1){
b.push_back(h1);
curr ^= h1;
s.erase(h1);
continue;
}
if (curr != h2){
b.push_back(h2);
curr ^= h2;
s.erase(h2);
continue;
}
curr ^= b.back();
s.insert(curr);
s.erase(h1);
curr ^= h1;
b.pop_back();
b.push_back(h1);
}
curr = 0;
vector <int> c;
for (auto x : b){
c.push_back(x);
curr ^= x;
vector <int> na;
for (auto y : a){
if (curr != y){
c.push_back(y);
c.push_back(y);
} else {
na.push_back(y);
}
}
a = na;
}
if (a.size()){
assert(false);
}
// cout << 1 << "\n";
// return;
for (auto x : c){
cout << x << " ";
}
cout << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Tester's code (C++)
#include<bits/stdc++.h>
using namespace std;
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;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
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);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
input_checker inp;
int T = inp.readInt(1, (int)2e4); inp.readEoln();
int NN = 0;
while(T-- > 0) {
int N = inp.readInt(1, (int)2e5); inp.readEoln(); NN += N;
vector<int> A = inp.readInts(N, 1, (int)1e9); inp.readEoln();
map<int, int> count;
int tot = 0;
for(auto &x: A) count[x]++, tot ^= x;
sort(A.begin(), A.end());
if(tot == 0 || (N > 1 && A.front() == A.back())) {
cout << -1 << '\n'; continue;
}
vector<int> B;
for(auto &[x, y]: count) if (y & 1) {
B.push_back(x);
}
A.clear();
int l = 0, r = (int)B.size() - 1;
int s = 0;
while(l <= r) {
if(s != B[l]) s ^= B[l], A.push_back(B[l++]);
else s ^= B[r], A.push_back(B[r--]);
}
for(int inc = 1 ; inc >= 0 ; --inc) {
for(auto &[x, y]: count) if((y & 1) ^ inc) {
int last = -1;
if(tot == x) last = A.back(), A.pop_back();
for(int i = 0 ; i < y / 2 ; ++i) {
A.push_back(x); A.push_back(x);
}
if(tot == x) A.push_back(last);
}
}
for(int i = 0 ; i < N ; ++i) {
cout << A[i] << " \n"[i == N - 1];
}
}
assert(NN <= (int)2e5);
inp.readEof();
return 0;
}
Editorialist's code (Python)
def check(a):
x = 0
for y in a:
x ^= y
if x == 0: return 0
return 1
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
x = 0
for i in range(n):
found = 0
for j in range(i, n):
if a[j] != x:
a[j], a[i] = a[i], a[j]
found = 1
break
if found:
x ^= a[i]
continue
a[i-1], a[-1] = a[-1], a[i-1]
break
if check(a): print(*a)
else: print(-1)