INTXOR - Editorial

PROBLEM LINK:

Div 1
Div 2
Practice

Author: Full name
Tester: Full name
Editorialist: Oleksandr Kulkov

DIFFICULTY:

SIMPLE

PREREQUISITES:

Basic xor properties

PROBLEM:

You need to guess sequence of number a_1,\dots,a_N (8 \leq N\leq 5 \cdot 10^4). You’re allowed to ask N queries of kind calculate a_i \oplus a_j \oplus a_k for three distinct indices i,j,k where \oplus is bitwise xor operation. Additionally each index may appear in queries at most 3 times.

QUICK EXPLANATION:

Solve N=3k+1 and N=3k+2, then due to constraints N=3k may be decomposed into N=4 and N=3(k-2)+2.

EXPLANATION:

Consider quadruple a_1,a_2,a_3,a_4. We may only ask four queries for it, we’ll see that it’s enough:

\begin{cases} a_1 \oplus a_2 \oplus a_3 = b_1 \\ a_1 \oplus a_2 \oplus a_4 = b_2 \\ a_1 \oplus a_3 \oplus a_4 = b_3 \\ a_2 \oplus a_3 \oplus a_4 = b_4 \end{cases}

Given that x \oplus x \oplus x = x we may obtain that a_1 \oplus a_2 \oplus a_3 \oplus a_4 = b_1 \oplus b_2 \oplus b_3 \oplus b_4. Thus solution to the system is:

\begin{cases} a_1 = b_1 \oplus b_2 \oplus b_3 \\ a_2 = b_1 \oplus b_2 \oplus b_4 \\ a_3 = b_1 \oplus b_3 \oplus b_4 \\ a_4 = b_2 \oplus b_3 \oplus b_4 \end{cases}

in this way we may resolve any quadruple. But we also may see that there is another interpretation of equations we get for quadruple. From one point of view we consider every way to leave one variable out. This approach is not feasible for higher N. But we also may see it as we consider every possible way to take 3 consecutive variables in the xor. And this approach is feasible!

Let’s consider N xor triples b_i = a_{i-1} \oplus a_{i} \oplus a_{i+1} with a_{N+1} \equiv a_1 and a_{-1} \equiv a_N. Let s = b_1 \oplus \dots \oplus b_N. One can see that for this value holds s=a_1 \oplus \dots \oplus a_{N} since all a_i occur in s exactly thrice. Now we should consider cases:

  1. N=3k+1. In this case you have an easy way to subtract from s anything but a_i:
a_i = s \oplus b_{i+2} \oplus b_{i+5} \dots \oplus b_{i-2} = s \oplus (a_{i+1} \oplus a_{i+2} \oplus a_{i+3}) \oplus (a_{i+4} \oplus a_{i+5} \oplus a_{i+6}) \oplus \dots \oplus (a_{i-3} \oplus a_{i-2} \oplus a_{i-1})
  1. N=3k+2. Now you may subtract everything but a_{i+1} and a_{i+2}:
a_{i+1} \oplus a_{i+2} = s \oplus b_{i-1} \oplus b_{i-4} \oplus \dots \oplus b_{i+4} = s \oplus (b_{i} \oplus b_{i-1} \oplus b_{i-2}) \oplus(b_{i-3} \oplus b_{i-4} \oplus b_{i-5}) \oplus \dots \oplus (b_{i+5} \oplus b_{i+4} \oplus b_{i+3})

Xoring this value with b_{i+1} will give you a_i.

Combining this approaches as mentioned in quick explanation will finish off the problem. Note that due to N \leq 5 \cdot 10^4 you’ll have to use some kind of prefix and suffix sums grouped by remainder of index modulo 3 to quickly calculate final values of a_i.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

RELATED PROBLEMS:

1 Like

Hello sir,there is one condition a(i+1)=a(i)+1
Subtask #2 (25 points): a(i+1)=(ai)+1 for each valid i
With this if i know a1,i will get complete series

if i=1,j=2,k=3
then the XOR of values at these indexes is R(17) given by the system
10001=17
now take 4 LSB keep the remaing bits in the R as it is,and try to get the consicutive values by chaning the 4 LSB and their XOR should be 17
this goves the value of the Index 1,from the Subtask#2 we can obtain remaing series
Regards
Samuel