Politicians and Competitive Programmers#12861

Politicians and Competitive Programmers (Editorial)

Let's assign a value of to competitive programmers and to politicians. Then it's easy to see, that the query simply returns bitwise of the values of , , .

So, we have the following problem: n\ge 5 binary values x_1, x_2, \ldots, x_n are hidden. We can choose distinct indices (i, j, k), where can't be selected as more than once, and get x_i\oplus x_j \oplus x_k. We need to find all the values.

Let's start with first four values, and ask y_1 = x_1\oplus x_2 \oplus x_3, y_2 = x_2 \oplus x_3 \oplus x_4, y_3 = x_3\oplus x_4 \oplus x_1, y_4 = x_4\oplus x_1 \oplus x_2.

From here, we can deduce y_1\oplus y_2 \oplus y_3 = x_3, y_2\oplus y_3 \oplus y_4 = x_4, y_3\oplus y_4 \oplus y_1 = x_1, y_4\oplus y_1 \oplus y_2 = x_2.

After we determined the first values, we can determine the next ones one by one by asking for x_{i+1}\oplus x_i \oplus x_{i-1}.