slizkov's blog

By slizkov, history, 6 years ago, In English

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.

  • Vote: I like it
  • +51
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    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.

»
6 years ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

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.

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)))?

»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

The problem is known as 3XOR in the literature, by the way.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As far as I know, 3XOR is to find a, b, c such that a xor b = c.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      "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:

      1. Consider only the most significant bits (MSB). Is there a triple so that it xors to 1? If yes, then the MSB of the maximal xor has to be 1. Otherwise it is 0.
      2. Now add next bits. Is there a triple that xors to 11 (or 01, depending on previous answer)?

      And so on.

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 2   Vote: I like it -32 Vote: I do not like it

        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?

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +31 Vote: I do not like it

          I guess so. My point is that since the reduction is simple, you can safely regard the problems as the same.

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it -19 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it +10 Vote: I do not like it

              “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.

              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, # ^ |
                  Vote: I like it -19 Vote: I do not like it

                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).

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                    Vote: I like it +21 Vote: I do not like it

                  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.

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        "Is there a triple that xors to 11 (or 01, depending on previous answer)?"

        How fast you find it?

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I don’t, 3XOR oracle does that for us. We only strip the numbers to their first most significant bits before asking.