allthecode's blog

XOR
By allthecode, 12 years ago, In English

Hello,

I found this Div 2 — A problem quite interesting. The tutorial gives a quadratic solution; however, I was wondering if there was a linear solution. Any ideas? Just for the fun.

Thanks.

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

»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

O(N*log(maxAi)) is well known .. See this problem. I don't know whether there is a linear solution, but in general case O(N*log(maxAi)) will almost always enough.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    It is linear solution, as the size of input is itself, so the time complexity of this solution grows linearly with input length.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I think that CherryTree means O(N*log(maxAi)) integer operations, and this grows as log(max(Ai)) * input

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        It's a tricky question. We are often assuming O(1) operations with arbitrary-precision integers, but still consider them in time/space complexity. Which, I think, causes some strange situations. I'm not qualified in computational complexity theory, though I prefer notation in such cases. :) Anyway, we are already too far from the subject.

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

          Actually, this is a problem like that: given two arbitary integers in decimal, compute xor of them. Suddenly, you're to convert them into binary, so... Let us denote input is O(1), xor is O(1) and ignore "арифметическую поправку асимптотических обозначений" (I don't know how it is called in English) :)

          → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I think that there is a trick that allows you to have impractical, but better solution with following idea.

    First of all, compute prefix xors and split them into parts with max_bit set and not set. (This is O(N))

    This is the following problem now: given A and B, find i,j: a[i] ^ b[j] is maximal.

    Split each array by k maximal bits (i.e. O(2^k) groups). Solve this problem for numbers of groups in O(k*2^k). Each group from A will be optimal with not more than one group from B. Let T(N,b) will be complexity of the solution. We have T(N,b) = sum (T(n[i], b-k)) + k*2^k + N, where sum of all n[i] is N. We can denote k like min(b, log(N/log(N))), and, I think, got T(N,b) like N*b/min(b, log(N/log(N)) as a result (possible, with some additional tricks).

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

    So how to solve this problem in your link?

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

      There is a link to the editorial in the problem.

      → Reply