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)$ ~\mathcal O(N \log N)~.

Time complexity: $\mathcal O(\max A \cdot N \log N)$ ~\mathcal 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$ ~2N+1~ possible candidates for $c$ ~c~: $A_1 \oplus B_1, A_2 \oplus B_1, \dots, A_{2N+1} \oplus B_1$ .

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

For the final subtask, we will use the fact that $2N+1$ ~2N+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}$

Let's XOR both sides by $A_1 \oplus A_2 \oplus \dots \oplus A_{2N+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}$

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}$

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)$ ~\mathcal O(N \log N)~

Comments

There are no comments at the moment.