XORAGN - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice

Contest

Author: Abishek Saini

Tester: Suchan Park

Editorialist: Suchan Park

DIFFICULTY:

Easy

PREREQUISITES:

Properties of XOR

PROBLEM:

Given an integer sequence A_{1}, A_{2}, \cdots, A_{n}, a new sequence B is defined by:

B_{i\cdot N + j + 1} = A_{i+1} \oplus A_{j+1} \forall 0 \le i, j < N

Compute the value of B_{1} \oplus B_{2} \oplus \cdots \oplus B_{N^2}.

QUICK EXPLANATION:

Note that there are some duplicate elements in the sequence B. B_{x \cdot N + y + 1} = A_{x} + A_{y}, and B_{y \cdot N + x + 1} = A_{y} + A_{x}. Also, for any X, X \oplus X = 0 holds. Therefore, for x \neq y, B_{x \cdot N + y + 1} \oplus B_{y \cdot N + x + 1} = 0. Iterate over every x and y, then we can see that only B_{0 \cdot N + 0 + 1}, B_{1 \cdot N + 1 + 1}, \cdots, B_{(N-1) \cdot N + (N-1) + 1} are left, an the answer equals to 2A_{1} \oplus 2A_{2} \oplus \cdots \oplus 2A_{N}.

EXPLANATION:

From the definition of the sequence B, let’s write our goal:

\begin{aligned} & (& A_{1} + & A_{1}) \oplus (& A_{1} + & A_{2}) \oplus (& A_{1} \oplus & A_{3}) \oplus \cdots \oplus (& A_{1} + & A_{N-1}) \oplus (& A_{1} + & A_{N}) \\ \oplus & (& A_{2} + & A_{1}) \oplus (& A_{2} + & A_{2}) \oplus (& A_{2} \oplus & A_{3}) \oplus \cdots \oplus (& A_{2} + & A_{N-1}) \oplus (& A_{2} + & A_{N}) \\ \oplus & (& A_{3} + & A_{1}) \oplus (& A_{3} + & A_{2}) \oplus (& A_{3} \oplus & A_{3}) \oplus \cdots \oplus (& A_{3} + & A_{N-1}) \oplus (& A_{3} + & A_{N}) \\ & \cdots \\ \oplus & (& A_{N-1} + & A_{1}) \oplus (& A_{N-1} + & A_{2}) \oplus (& A_{N-1} \oplus & A_{3}) \oplus \cdots \oplus (& A_{N-1} + & A_{N-1}) \oplus (& A_{N-1} + & A_{N}) \\ \oplus & (& A_{N} + & A_{1}) \oplus (& A_{N} + & A_{2}) \oplus (& A_{N} \oplus & A_{3}) \oplus \cdots \oplus (& A_{N} + & A_{N-1}) \oplus (& A_{N} + & A_{N}) \end{aligned}

I wrote like this N \times N matrix form, because B was defined by iterating all 0 \le i, j < N.

Let’s denote the element of the x-th row and the y-th column here as C_{x, y}. (1-indexed)

By looking at this matrix, we can notice that the matrix is symmetric. This comes from the commutativity of additions:

C_{x, y} = A_{x} + A_{y} = A_{y} + A_{x} = C_{y, x}

So we are certain that the same elements are included twice. This is important, because for all integers X,

X \oplus X = 0

holds, which means

C_{x,y} \oplus C_{y,x} = 0.

Since 0 \oplus X = X also holds too, we can apply this formula for all x \neq y. The elements left will be on the diagonal.

\begin{aligned} (A_{1} + A_{1}) \oplus \\ & (A_{2} + A_{2}) \oplus \\ & & (A_{3} + A_{3}) \oplus \\ & & & \cdots \\ & & & & (A_{N-1} + A_{N-1}) \oplus \\ & & & & & (A_{N} + A_{N}) \end{aligned}

Now, it is easy to compute this value by a simple for loop.

AUTHOR’S AND TESTER’S SOLUTIONS:

Tester’s solution can be found here.