Editorial for Tall

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: Plasmatic

Subtask 1

For this subtask, we can just brute force all possible values of $c$ $c$ since any value of $c$ $c$ above $255$ $255$ would have bits above $2^7$ $2^{7}$ set. This would cause the answer to always be $0$ $0$ .

Time Complexity: $\mathcal O(N \max \{ a_i \})$ $O (N max {a_{i}})$ or similar

Subtask 2

This subtask is for any solutions that have the same observation as subtask 3 but are otherwise too slow.

Time Complexity: $\mathcal O(N^3)$ $O (N^{3})$ or similar

Subtask 3

Observe that after applying $a_i \oplus c$ $a_{i} \oplus c$ over all $a_i$ $a_{i}$ , at least one element must be zero so that our MEX is non-zero. Thus, $a_i = c$ $a_{i} = c$ for some $i$ $i$ so there are only $N$ $N$ possible values that $c$ $c$ can be. The MEX of a sequence can be computed in linear time, which is sufficient to pass this subtask.

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

Full Solution

First, remove any duplicates in the sequence so all elements are unique.

Consider some bit $2^k$ $2^{k}$ and the least significant $k+1$ $k + 1$ bits of the values in the sequence. Divide the sequence by whether each value has the bit corresponding to $2^k$ $2^{k}$ set, giving us two sets of values. Notice that depending on whether bit $2^k$ $2^{k}$ is set in $c$ $c$ or not, one of these will only contain values in the range $[0, 2^k-1]$ $[0, 2^{k} - 1]$ and the other will only contain values in the range $[2^k, 2^{k+1}-1]$ $[2^{k}, 2^{k + 1} - 1]$ . Call these the lower and upper sets respectively.

Observe that if the lower set has $2^k$ $2^{k}$ values, then the answer is at least $2^k$ $2^{k}$ no matter what the lower bits of $c$ $c$ are, so we can just compute the answer for the bit $2^{k-1}$ $2^{k - 1}$ using the upper set only, yielding us the lower bits of $c$ $c$ . On the other hand, if the lower set does not have $2^k$ $2^{k}$ values, then the MEX can be at most $2^k-1$ $2^{k} - 1$ so the values of the upper set do not matter since they are all at least $2^k$ $2^{k}$ . Then, we can do the same as the previous case, except using the lower set instead.

In the worst case, we just need to compute the answer for bit $2^{k-1}$ $2^{k - 1}$ using the two sets of numbers individually, and can then use those answers to compute the final answer in $\mathcal O(1)$ $O (1)$ time. Starting this search from the most significant bit yields us a divide and conquer solution.

Time Complexity: $\mathcal O(N \log \max \{ a_i \})$ $O (N \log max {a_{i}})$

Comments

There are no comments at the moment.