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.
fourth link in Google
You can find maximum xor of K numbers in O(NlogX) (where X is maximum number in array) using Gaussian elemination (as mentioned on Quora). The unsolved part of problem for me is to find these K numbers in array.
The Quora answer is just wrong. 3Sum is widely known to be O(n2), I have no idea what they're talking about. The linked article also solves the problem in
. Even if 3sum were 
, the XOR maximization algorithm given only works if you can use the whole array.
If C is small you can use the "xor transform" to find the smallest/greatest value in O(C * logC). Binary search to find the first value in any triple looks ok to find the triple.
Sorry for my lack of education, is "xor transform" the same as the "xor convolution"? And where to read about them? And still there is a question after this — what if the numbers in array are large (say, n is about 105 and C is about 109, and that's a real (contest) problem; or that's a theoretical problem, then how to solve it in O(n logk (Cn)))?
Yes, you can learn it from here https://csacademy.com/blog/fast-fourier-transform-and-variations-of-it . The problem for higher values of C is likely an open problem as pointed out below.
The problem is known as 3XOR in the literature, by the way.
As far as I know, 3XOR is to find a, b, c such that a xor b = c.
"a ^ b = c" is the same as "a ^ b ^ c = 0", which is the same as "(a ^ X) ^ (b ^ X) ^ (c ^ X) = X". That is, by xoring everything with X, you can ask the same 3XOR oracle, whether there is a triple that xors to a given number X.
Now, thanks to bitwise independency of XOR, you can find the maximal xor bit by bit:
And so on.
So, what you want to say is that I'm right and you are wrong, however, you can reduce the problem described in this post to the 3XOR problem, right?
I guess so. My point is that since the reduction is simple, you can safely regard the problems as the same.
No, you can't. Because it is simple to reduce 3-SAT to 3-COL, but 3-SAT and 3-COL are two different problems.
“Regarding as the same” and claiming equality are different things. As long as I’m fine with logarithmic slowdown (the OP seems to be fine too), I would read everything about 3XOR as if it were written about the original problem, instead of thinking that there was no such research.
Your first affirmation was The problem is known as 3XOR, and you were wrong here. That's it, just as simple. And now, you're saying "Regarding as the same" and claiming equality are different things... just stop contradict yourself.
Yes, you can reduce the problem from this post to 3XOR, but even so, these two problems are not the same (the reason is similar to 3SAT and 3COL).
Yes, you are technically right. Seems like you really really wanted to hear those words. Now that we've established that, let's acknowledge that Urbanowicz's comment was helpful and relevant to the question and stop arguing for silly details. The author of the blog doesn't seem to be writing an academic paper for any of this to matter.
"Is there a triple that xors to 11 (or 01, depending on previous answer)?"
How fast you find it?
I don’t, 3XOR oracle does that for us. We only strip the numbers to their first most significant bits before asking.