Editorial for CPC '21 Contest 1 P2 - AQT and Multiset - Olympiads Online Judge

Editorial for CPC '21 Contest 1 P2 - AQT and Multiset

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Tzak

For the first subtask, it suffices to try possible values of $c$ $c$ less than $2^{15}$ $2^{15}$ . The resulting multisets can be compared with sorting in $\mathcal O(N \log N)$ $O (N \log N)$ .

Time complexity: $\mathcal O(\max A \cdot N \log N)$ $O (max A \cdot N \log N)$

For the second subtask, we observe that if a value for $c$ $c$ exists, there is some $A_i$ $A_{i}$ such that $A_i \oplus c = B_1$ $A_{i} \oplus c = B_{1}$ , meaning $c = A_i \oplus B_1$ $c = A_{i} \oplus B_{1}$ . With this, we have $2N+1$ $2 N + 1$ possible candidates for $c$ $c$ : $A_1 \oplus B_1, A_2 \oplus B_1, \dots, A_{2N+1} \oplus B_1$ $A_{1} \oplus B_{1}, A_{2} \oplus B_{1}, \dots, A_{2 N + 1} \oplus B_{1}$ .

Time complexity: $\mathcal O(N^2 \log N)$ $O (N^{2} \log N)$

For the final subtask, we will use the fact that $2N+1$ $2 N + 1$ is odd. Let's begin by assuming that we have found a value of $c$ $c$ which makes the multisets equal. This implies that:

$\displaystyle A_1 \oplus c \oplus A_2 \oplus c \oplus \dots \oplus A_{2N+1} \oplus c = B_1 \oplus B_2 \oplus \dots \oplus B_{2N+1}$ $A_{1} \oplus c \oplus A_{2} \oplus c \oplus \dots \oplus A_{2 N + 1} \oplus c = B_{1} \oplus B_{2} \oplus \dots \oplus B_{2 N + 1}$

Let's XOR both sides by $A_1 \oplus A_2 \oplus \dots \oplus A_{2N+1}$ $A_{1} \oplus A_{2} \oplus \dots \oplus A_{2 N + 1}$ :

$\displaystyle c \oplus c \oplus \dots \oplus c = B_1 \oplus B_2 \oplus \dots \oplus B_{2N+1} \oplus A_1 \oplus A_2 \oplus \dots \oplus A_{2N+1}$ $c \oplus c \oplus \dots \oplus c = B_{1} \oplus B_{2} \oplus \dots \oplus B_{2 N + 1} \oplus A_{1} \oplus A_{2} \oplus \dots \oplus A_{2 N + 1}$

The left hand side has an odd number of copies of $c$ $c$ , so we have:

$\displaystyle c = B_1 \oplus B_2 \oplus \dots \oplus B_{2N+1} \oplus A_1 \oplus A_2 \oplus \dots \oplus A_{2N+1}$ $c = B_{1} \oplus B_{2} \oplus \dots \oplus B_{2 N + 1} \oplus A_{1} \oplus A_{2} \oplus \dots \oplus A_{2 N + 1}$

We have proven if a solution exists, then it is unique and given by the expression above. All that remains is to check if this value of $c$ $c$ works.

Time complexity: $\mathcal O(N \log N)$ $O (N \log N)$

Comments

There are no comments at the moment.