PROBLEM LINK:
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:
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:
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:
- N=3k+1. In this case you have an easy way to subtract from s anything but a_i:
- N=3k+2. Now you may subtract everything but a_{i+1} and a_{i+2}:
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.