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: