×

# XORAGN - Editorial

Practice

Contest

Author: Abishek Saini

Tester: Suchan Park

Editorialist: Suchan Park

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.

This question is marked "community wiki".

138
accept rate: 0%

19.5k348496535

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,026
×280
×106