ALR20E - EDITORIAL

PROBLEM LINK:
Practice
Contest

Author: conan_0
Tester: shivansh7
Editorialist: conan_0

DIFFICULTY: Easy

PRE-REQUISITES: Bit-manipulation

PROBLEM:

Let S={a_1,a_2....a_N} be some permutation of numbers from 1 to N .You are given Bitwise-XOR of consecutive elements of S i.e X= (a_1 \oplus a_2) ,(a_2 \oplus a_3),.....(a_{N-1} \oplus a_N) .
Now you have to find original elements a_1,a_2...a_N using above series.
Note- N is given odd.

EXPLANATION:

Let’s denote XOR of series S by P= a_1 \oplus a_2 \oplus a_3\oplus....a_{N-1}\oplus a_N, since
S is permutation of numbers from 1 to N, P=1\oplus 2\oplus 3\oplus....\oplus N. So value of P can be calculated in linear time.
Let’s take XOR of odd elements of series X i.e. (a_1 \oplus a_2), (a_3 \oplus a_4),....(a_{N-2} \oplus a_{N-1}) if we xor this series its value will be a_1 \oplus a_2 \oplus....a_{N -1} (It will be missing last element of series P i.e. a_N).
Using these two series we can calculate value of a_N by XOR of these two series.

HOW?

P= a_1 \oplus a_2 \oplus a_3 \oplus.....\oplus a_{N-1}\oplus a_N
R=a_1 \oplus a_2 \oplus a_3 \oplus.....\oplus a_{N-1}
P \oplus R=(a_1 \oplus a_2 \oplus a_3 \oplus.....\oplus a_{N-1}\oplus a_N) \oplus (a_1 \oplus a_2 \oplus a_3 \oplus.....\oplus a_{N-1})
Using commutative property of XOR
P \oplus R=(a_1 \oplus a_1) \oplus (a_2\oplus a_2)\oplus.....\oplus(a_{N-1} \oplus a_{N-1}) \oplus a_N
Since, a\oplus a=0
P \oplus R= 0 \oplus 0 \oplus...0 \oplus a _N
Also, a \oplus 0=a
P \oplus R=a_N

From value of a_N we can find the value a_{N-1} from last element X i.e. a_{N-1} \oplus a_N. Similarly by reverse iteration on X we can find values of a_{N-1}, a_{N-2}, a_{N-3}....a_3, a_2, a_1 in the given order. Thus original permutation is restored.

TIME COMPLEXITY: O(N)

SOLUTION:

LINK

2 Likes

I request you to provide editorial for the last problem (https://www.codechef.com/ALRA2020/problems/ALR20F)

Don’t worry all editorials would be available soon.