missionary_69's blog

Coding round question — XOR, Tree, multiple queries
By missionary_69, history, 5 years ago, In English

You are given a tree with A nodes and A-1 edges which is rooted at 1.
There are C queries and for each query you are given two integers d (the node number) and e and you have to find the maximum value when e is xor'ed with any of the ancestors of d or d itself.
Formally, find the maximum value which can be obtained when e is XOR'ed with any node in the path from d to root. XOR is bitwise XOR operator.

2 <= A <= 100000
Tree given in the form of an array B (one indexed) with A-1 elements where B[i] denotes parent of i+1 th node.
1 <= C <= 300000
1 <= D[i] <= A — node number d
1 <= E[i] <= 300000 — the number to be XOR'ed e

Input
A = 8
B = [1, 1, 2, 2, 3, 3, 1]
C = 5
D = [2, 3, 5, 6, 8]
E = [1, 1, 5, 4, 10]

Output
[3, 2, 7, 7, 11]

  • Vote: I like it
  • -17
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

First lets look at how to calculate: out of some numbers ai, what is max of e xor ai? Consider the largest bit set in any ai or set in e. For that bit to be set in e xor ai, they must have opposite values for that bit. If such a pair exists we know that it must be greater than any pair that has equal values for that bit because all the remaining bits cannot add up to more than that most significant bit. Therefore we can restrict our search to only those numbers that have such a bit set and repeat the process for the next bit. If we stored all the numbers ai into a trie we could easily test this for each bit and come to our largest pair in #bits <= 25 time.

Now the question is how to get such a trie at each query location. If we store the count of how many values have their endpoint underneath this node at each node of our trie we can quickly insert and remove numbers even when there are duplicates. In such a trie, instead of just checking if the node exists, we must also check that is has a size > 0. If we do a dfs, insert each number into our trie as we enter it, and remove it when we leave, then at each location in our dfs we will have a trie consisting of exactly the numbers on the path from the root to this location and can answer all the queries for this location offline.

The total time complexity should be #bits * ((2 * tree size) + query count) or about 12.5m operations.

→ Reply
»
5 years ago, # |
  Vote: I like it -19 Vote: I do not like it

you can solve it with persistent trie

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

nice handle

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

You just need to maintain trie at every Node. At i'th node the trie will contain all the values of the Ancestors of the i'th node and i'th node itself. Just try it once by yourself or refer the below code.

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

    looks good, thanks!

    also i think it would be better if you implemented a delete function for trie, because here you're passing whole Trie in dfs function, instead of passing it by reference. It could give you TLE, if i'm thinking correctly.

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

There is another method, no segment tree or trie needed. But complexity will be O(N*logN*logN) (A bit higher, but should pass anyways). Instead of using trie, use a multiset to store all the numbers. Do a DFS and when you enter a node insert the value of the node in multiset. When all the children of node has been processed, erase the value of that node. You will have only the ancestors of that node in the multiset now. Now iterate through the bits of the value of current node starting from MSB. Suppose the value of node is 10110.

Now u need to answer. Is there any number in form 0XXXX in my multiset? In others words, any number between 00000 and 01111? find the std::lower_bound of 00000 in multset and check if its <= 01111 and you're done!

Similarly maintain the prefix of the current number and using lower_bound keep on filtering out!

→ Reply