How to solve this problem in time O(n log^k Cn) for some constant k? (or maybe it is impossible?)
Consider an array of size n with natural numbers not greater than C. I want to find three different elements in it (possibly their numbers will be equal) with maximal xor among all such triples.
For two elements the problem can be easily solved in time O(n log C), so I was thinking about this version. I haven't seen it before, neither on a contest nor on a training.