Given a list of numbers, you have to choose 3 of them so that xor of the chosen numbers is maximal
The most obvious way to solve this problem would be to find xor of all triplets of elements in the list and report the maximum. Complexity of such a solution is O(N^3). This solution will be able to solve subtask 1 with N ≤ 100. However, for larger N, it will take too much time, and should time out.
Lets try to find if the problem can be solved in smaller time. Lets look at each nmber as a bitstring of length 30. Lets say we fix two numbers X and Y, and we want to find the third number Z ≠ X, Y such that X xor Y xor Z is largest. Let W = X xor Y. W is also a bitstring of length 30. We want to choose a Z so that XOR of W and Z is maximum.
Lets consider the possibilities of Z. If the first bit of W is w1, we want the first bit of Z to be 1 ^ w1, so that the first digit of XOR be 1. If there exist any such Z, then only those Zs need to be consider further, because for any other Z, the XOR will always be less than 229. Similarly, if w2 is the second bit of W, then we would prefer to have the second bit of our best Z to be 1 ^ w2. If such a Z exists among the list of Zs being currently considered then the second bit of optimal XOR is 1. Also, we will choose only those Zs for next step for which second bit is 1 ^ w2. If not, all the Z are equally bad and we will not remove any of the Zs. We can keep going like this, maintaining the list of possible Zs all the time till all 30 bits of the optimal XOR have ben decided.
The only hard part about this solution is to maintain the set of possible value of Z, as we examine every bit of W. This can be done easily by maintaining a Trie of all values of Z ≠ X, Y. We start with current node = root node of this trie. At any time, the set of values of Z we are considering are the descendants of current node. To test whether there exists any Z for which ith bit is b would be same as testing whether the current node has a non-null child along edge corresponding to b. To choose only those Zs for which ith bit is b would be same as going one step towards edge corresponding to b. The complexity of this solution is O(N2 log Amax), and can be used to solve all subtasks. See Tester’s / Setter’s solutions for implementation details.