You are not logged in. Please login at www.codechef.com to post your questions!

×

XORAGN - Editorial

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.

This question is marked "community wiki".

asked 19 May, 07:42

tncks0121's gravatar image

2★tncks0121
138
accept rate: 0%

edited 10 Aug, 19:39

admin's gravatar image

0★admin ♦♦
19.5k348496535

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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

question asked: 19 May, 07:42

question was seen: 103 times

last updated: 10 Aug, 19:39