radoslav11's blog

RMI 2014 — Minxor
By radoslav11, history, 8 years ago, In English

Hello!

I was solving problem Minxor from second day of RMI 2014. In short the problem is:

You have 3 types of queries.

1 x -> inserts x into the set
2 x -> deletes x from the set
3 -> asks for the smallest xor of any two numbers in the set

I solved the problem offline using a trie + divide and conquer. My solution is similar to link. Again in short: compressing all updates as "number x appears from time I to time J". Here is the code. The complexity is O(M * log(M) * 32);

So my question is:

Is there a solution which runs faster than that or/is online. Thanks in advance :)

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

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

Yes, there's a simpler, online, O(log M) per query solution. Notice that if a < b < c, the minimum xor pair is never (a, c).

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

    Can you explain a little bit more the idea? How we get that (log M) per query ?

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

      Using the observation above, you can prove that members of the minimum xor pair must be adjacent in sorted order. So you only need to keep a simple BST (such as a STL set<>) to keep track of successors and predecessors of inserted/deleted elements and another min-heap-like structure in which you actually store the adjacent xor values in increasing order.

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

    Thats a nice trick! Thanks

    BTW is there a similar trick but for maximum xor?

    → Reply