PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Sorting, prefix XORs
PROBLEM:
You have an array A and an index P.
You can modify A as follows:
- Choose an index i (1 \lt i \lt N)
- Then XOR both A_{i-1} and A_{i+1} by A_i.
Find the minimum possible final value of A_P.
EXPLANATION:
The first course of action is, naturally, to figure out exactly how A_P can be modified.
When dealing with operations of this kind (as in, modifying a small number of indices in close proximity), it’s often useful to work with prefixes.
So, let’s define X_i = A_1 \oplus A_2 \oplus\ldots\oplus A_i to be the i-th prefix XOR of A.
We also define X_0 = 0.
Let’s see how the array X changes when we apply the operation on index i.
The only values of A that change are A_{i-1} and A_{i+1}.
Let Y denote the new prefix XOR array.
For all 0 \le j \lt i-1, note that there are no changes to elements whatsoever.
So we simply have Y_j = X_j.
For index i-1 itself, note that the only change comes from the value at index i-1, which has been XOR-ed by A_i.
So, Y_{i-1} = X_{i-1} \oplus A_i.
However, observe that this is exactly X_i.
Thus, we simply have Y_{i-1} = X_i.
For index i, again the only change is that A_{i-1} has been XOR-ed by A_i, because the value at index i didn’t change.
So, Y_i = X_i \oplus A_i.
But X_i = X_{i-1} \oplus A_i, so we obtain Y_i = X_{i-1} \oplus A_i \oplus A_i = X_{i-1} because of the involutory property of bitwise XOR (i.e. x\oplus x= 0 for any x.)
Thus, Y_i = X_{i-1}.
For indices j\ge i+1, the changes are that both A_{i-1} and A_{i+1} have been XOR-ed by A_i.
This means that we have Y_j = X_j \oplus A_i \oplus A_i = X_j, i.e. the prefix XOR remains unchanged for these indices.
Observe that almost all the prefix XORs have remained unchanged.
The only ones that changed are the ones corresponding to indices i-1 and i, and they simply swapped positions!
Thus, our operation really just allows us to do the following with the prefix XOR array X:
- Choose an index i (1 \lt i \lt N), and swap X_i and X_{i-1}.
Swapping any adjacent elements of an array is a powerful tool, and in fact allows us to rearrange the array however we like!
Thus, using our operations, we can rearrange the elements [X_1, X_2, \ldots, X_{N-1}] in whatever order we like.
Note however that X_0 = 0 is always fixed; and X_N cannot be moved (because we cannot choose i = N in our operation.)
Let’s use this to solve the original problem of minimizing the value of A_P.
Note that by reversing the definition of prefix XORs, we see that A_P = X_P \oplus X_{P-1}, so this is what we want to minimize.
To do this, we will require a bit of casework on the index P to account for the fixed values.
Case 1: P = 1
We want to minimize X_1 \oplus X_0.
However, X_0 = 0 is fixed, so we really just want to minimize X_1.
Our operation allows us to rearrange [X_1, \ldots, X_{N-1}] however we like.
So, the answer is simply \min(X_1, \ldots, X_{N-1}).
Case 2: P = N
We want to minimize X_N \oplus X_{N-1}.
However, X_N is fixed, while the power of rearrangement allows us to freely bring any one of [X_1, \ldots, X_{N-1}] to index N-1.
So, the answer here is the minimum value of X_N \oplus X_i across all 1 \le i \lt N.
This can be easily found in linear time; just try all values of i.
Case 3: 1 \lt P \lt N.
We want to minimize X_P \oplus X_{P-1}.
Neither value is fixed, and recall that we can freely rearrange [X_1, \ldots, X_{N-1}].
So, in this case the answer is simply the minimum XOR of some pair in [X_1, \ldots, X_{N-1}].
We now have a sub-problem: given a (multi)set of values, how to quickly compute the minimum XOR of some pair of them?
The solution to this is in fact quite simple: the optimal pair will always be some pair of adjacent elements in sorted order!
That is, sort the values [X_1, \ldots, X_{N-1}] in ascending order, and then the answer will be the minimum of (X_i \oplus X_{i+1}) across all i.
Proof
Clearly, sorting X in ascending order isn’t going to change the minimum pairwise XOR; so it doesn’t hurt to do this.
We now have X_1 \le\ldots\le X_{N-1}.Now consider three indices i \lt j \lt k.
We’ll prove that \min(X_i\oplus X_j, X_k\oplus X_j) \le X_i\oplus X_k.If X_i = X_k, then X_j must also be equal to them, and all three pairwise XORs are just 0.
So, our claim trivially holds.Otherwise, X_i \lt X_k, so there exists a bit where they differ in binary representation.
Let b be the highest bit where they differ.
Note that this means all bits higher than b are equal in X_i and X_k, i.e. this is their “longest common prefix”.
Further, the highest set bit in X_i \oplus X_k is b.Because X_j lies between X_i and X_k, it will also share their prefix of bits above b.
There are now two cases:
- X_j has b set.
In this case, X_j \oplus X_k won’t have b (or any higher bit) set, so that X_j \oplus X_k \lt 2^b \le X_i \oplus X_k.- X_j doesn’t have b set.
In this case, X_j \oplus X_i won’t have b (or any higher bit) set, so that X_j \oplus X_i \lt 2^b \le X_i \oplus X_k.So in either case, one of the “inner” XORs is strictly smaller than X_i \oplus X_k.
This proves that the minimum XOR is attained by some adjacent pair, as claimed (since if not, we’d be able to find some inner pair with smaller XOR, contradicting minimality.)
This gives a solution in \mathcal{O}(N\log N) time.
Alternately, you can use a trie to achieve similar complexity; though it’s of course much more code.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, p = map(int, input().split())
a = list(map(int, input().split()))
pref = [0]
for x in a: pref.append(pref[-1] ^ x)
if p == 1:
print(min(pref[1:n]))
continue
if p == n:
print(min(pref[n] ^ pref[i] for i in range(1, n)))
continue
s = sorted(pref[1:n])
print(min(s[i] ^ s[i+1] for i in range(len(s)-1)))