FattyLovesMangoes's blog

How to solve these type of problems?
By FattyLovesMangoes, 3 years ago, In English

Can someone explain how to solve this and if you know similar problems, can you please mention them here?

I know trie concept but not able to come up with a solution.

(Please don't down vote until some one posted the solution. I don't want it to disappear from recent actions without being answered.)

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

»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think something like the following could work (lmk about any issues):

Construct the bit trie on all elements, then for each element in the sequence, do the following:

Find the paths in the trie that produce the lowest and highest xor (of course, excluding the path of the current element). Denote these xors as $$$l$$$ and $$$r$$$ respectively. Now, we know that for the current element, we have $$$n - 1$$$ xors in the range $$$[l, r]$$$.

Now, sort all of these $$$[l, r]$$$ segments. We know that there are $$$n$$$ such segments, and that each segment has $$$n - 1$$$ xors in it. This is good for the following brute force:

Sort all the segments. Keep iterating through the segments as long as we can take the next segment without the total # of xors exceeding k. When this condition is broken, simply iterate through all xors of the current segment until we get to the k-th smallest xor overall.

EDIT: Small issue since this solution counts each pair twice. You can solve an equivalent problem where you consider the xor of all ORDERED pairs, and instead find the 2 * k -th smallest xor.

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

    Those segments are not disjoint which means we cannot determine to which segment the kth smallest belongs to.

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

This looks like binary search (search the answer) problem. Can you see how you can count number of xors <= lim in a bit trie or does it need clarification?

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

    looks like this should work. Thank you :)

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

      This is my solution.I think it will help you.Since the answer will increase when k is increasing.We just use binary search to find the answer.And then,we assume current answer is x.We use trie to caculate the number of pairs whose xor value is smaller than x in order to check if the current answer is right. Your text to link here...

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

      You can solve it even without using trie. Basically we find each bit from MSB to LSB, checking how many numbers can have this bit unset in the xor , if it is greater than k and then we know that even in the kth xor element too it will be unset, otherwise this bit will have to be set and so we substract the number of xors having this bit unsett from k and continue processing the bits ahead. My AC solution:

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

    Could you please elaborate?

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

      You can check here

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

      For the binary trie bit, maintain a binary trie with an auxiliary array, cnt, storing the number of array values, adding and removing a value from a binary trie now is just simply going down the trie whilst adding or subtracting one from the cnt array. Now, we need a function that finds the number of value that, when xored with $$$a_i$$$, is strictly smaller than a certain value (target). This is quite simple using the trie, so basically when we are going down the trie, we check whether the j-th largest bit is on or off for both the target and $$$a_i$$$, and there would be four cases: 1. Both are on 2. Both are off 3. $$$a_i$$$ is off and the target is on 4. $$$a_i$$$ is on and the target is off. For case 1, it is obvious that when we xor a number that has the j_th bit turned on, the resulting number would be strictly smaller than the target, so we can add all the numbers that have the j_th bit turned on to our answer. Using a similar analysis for all four cases, we can calculate the number of array values that when xored with $$$a_i$$$, result in a smaller than the target. We can then use this result to check if the target value is "good" or "bad". You can check the implementation detail in my code: pastebin

      → Reply