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 \})$ ~\mathcal 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)$ ~\mathcal 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)$ ~\mathcal O(N^2)~ or $\mathcal O(N^2 \log N)$ ~\mathcal 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)$ ~\mathcal 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 \})$ ~\mathcal O(N \log \max \{ a_i \})~

Comments

There are no comments at the moment.