Contest Duration: - (local time) (120 minutes) Back to Home

## D - XOR Game Editorial by evima

Consider whether the score gets $$v$$ or smaller.

If it is possible to divide $$A$$ into $$N$$ pairs so that the XOR of each pair is $$v$$ or smaller, Bob can play according to such division to ensure that the score gets $$v$$ or smaller.

On the other hand, if there is no such division, the score will be at least $$v+1$$, since assuming otherwise leads to contradiction immediately.

Thus, the problem becomes a matching problem where we should minimize the XORs of the pairs.

Let $$L=30$$. First, consider whether the $$L$$-th lowest bit of the answer is $$1$$. If we have an even number of integers whose $$L$$-th lowest bits are $$0$$ and an even number of integers whose $$L$$-th lowest bits are $$1$$, we can classify the integers according to that bit, and solve the same problem for each category where $$L:=L-1$$. Otherwise, we should make at least one pair of an integer whose $$L$$-th lowest bit is $$0$$ and an integer whose $$L$$-th lowest bit is $$1$$. On the other hand, if we make just one such pair, we can match $$0$$ to $$0$$ and $$1$$ to $$1$$ for the remaining pairs.

Therefore, the problem is reduced to the one where we have two sets of integers $$X$$ and $$Y$$, and we have to choose one element from each of the sets to minimize their XOR. We can solve it by building a trie.

The total complexity of our solution is $$O(NL)$$.

posted:
last update: