Can someone please explain how to solve GothamPD
?
4 Likes
Use heavy-light decomposition to turn long path into a data structure. For these long paths you can use a special trie to quickly lookup the optimal values. Maximum and Minimum XOR is really the same thing, you just need to invert your search key and the result.
In addition to the regular trie elements, on each valid tree node also store the minimum level of a element behind that trie node. This way you can quickly ignore trie nodes that are not on your path to the root because you searching from somewhere in the middle.
3 Likes
This involves persistent data structures.I hope you are aware about xor minimsation/maximisation using tries.If not check out this first https://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems
Moving forward,the basic concept used here is that if we can build tries for every node such that it contains every value from the path along that root to that node,then we can easily solve our problem in O(Log n) complexity .But building such tries will cost O(n^2) space and time which is not optimal.One thing we can observe is that if we have the trie build for a parent node,then the trie for it’s children will differ by only one entry.How can we use this to our advantage?Well here comes the use of persistence.Using this approach we can incrementally build a trie for a node using it’s parent’s trie in log n time and space.Here are two links from where i learnt about persistent data structures
Although both resources talk about persistent segment trees but hopefully you will get a very good idea about it as i did.Implementation is easier than persistent segment trees.Hope it helps 
10 Likes
@aditya730 Could you elaborate why parent node and child node differ by one entry.There seems to be no relation between encryption keys of parent and child in the question
did u understand the threads.iith.quora link ?
In that problem a trie is created for a set of numbers and max xor(or min) is found !!
For our problem v have a dynamic tree !!
So consider a node u. We have trie for all nodes (keys ) from root to u. Now we have to add new node v as child of u. But v’s trie should contain all nodes from root to u AND v added to it. So persistent tries are used which just basically append new key to parent’s trie
I used offline solution. I took input line by line and decoded the queries. If the line has 4 integers, 1st one must be 0, thus xor with 1st integer. Otherwise, 1st one must be 1, so xor with (1st integer ^ 1). Now after decoding queries, run a dfs on complete tree (after adding nodes from queries) and maintain a trie. As you get in subtree rooted at x, add x to trie, query for node x. And as you get out of subtree rooted at x, remove x from trie. (trie has all numbers from root to x while querying for x)
Code: Link
13 Likes
since it was a dynamic tree and online soln reqd. how do u do heavy light decomposition on dynamic trees ?
1 Like
Well, it claimed to require an offline solution, but actually you could easily decode it. As the first number of each row contain the encryption key or the encryption key xor 1. You could just check if the row contained 3 or 4 numbers to tell if the command is 0 or 1. However, even a real online solution would have worked. You already start with smaller tree and only grows over time. You easily do an online addition of nodes to the paths encoded in a trie. And you can add new trie path online as well, e.g: dynamically when first encountering a long path of regular nodes during a query.
1 Like
I had a simple approach that didn’t involve any persistent data structures though persistent is very useful in these kind of situations.
First notice that N is 10^5 and Q is 2 * 10^5.So due to this limit what I did was in every 1000th(depth of node %1000=1) I stored all its ancestors. So in the worst case it would be 1000+2000+…10^5 which is 1000(1+2+3+…100)=5050 * 1000 which is approximately 5*10^6 (n=10^5). This easily fits into the memory limit.
Next what I do is I sort all these lists in ascending order. So now if I start at a node then I move atmost 999 nodes upwards and then in the stored node you can a perform a binary search sort of trick to find the minimum and maximum value. Thus complexity is O((1000+logn)Q) which is O(10^7) approximately.
For adding nodes also follow same procedure and create a list in every 1000th node.
Link to my solution ---- https://www.codechef.com/viewsolution/13485588
4 Likes
Enter my custom randomized MO-like algorithm
I had a similar idea as aditya730, except i was not aware of persistent tries, and obviously building a trie at every node is too costly.
Then i remembered MO’s algorithm and how it divides the problem into segments of size sqrt(N), so i tried to build a trie at every node that was at depth divisible by sqrt(N). At the nodes where there was no trie, i moved in linear time up to root or until i meet a trie trie and for each trie i remembered the previous trie on the path to root.
This was still slow so i experimented with other values instead of sqrt(N). In the end i found out that my solution ran fastest if i placed a trie at depth divisible by ~6000. This still gave TLE on 2 cases. Then i used random :). I placed a trie on a node at depth divisible by 6000 with a probability of 50%.
On the first try i got TLE, but on the second all passed
Link to solution:
1 Like
Before diving into the persistent part, you must understand how to solve it in brute force.
Brute Force - O(QN)
Update
- Set parent of u to be v
Query
- Climb all ancestors and get all their keys
- XOR everything and get the minimum/maximum
But above solution will not pass since Q and N are upto 10^5.
Fast XOR min/max using trie - O(log N)
How do we optimize? Let’s solve XOR min first. Suppose we already have the set of encryption keys from the start. Given a decryption key, consider binary representation of all numbers. Sort the set. Then the set will look something like this:
// EXAMPLE
01101 // decryption key = 13
----- // encryption set = {1, 5, 6, 11, 20, 22, 26}
00001
00101
00110
01011
10100
10110
11010
When a sorted set is represented in binary, the 0’s come before the 1’s (obviously). Consider splitting the encryption set into those that start with 0 and those that start with 1:
0 | 1101 // decryption key = 13
--+----- // encryption set = [{1, 5, 6, 11}, {20, 22, 26}]
0 | 0001
| 0101
| 0110
| 1011
--+-----
1 | 0100
| 0110
| 1010
Here comes the crucial observation. To minimize XOR, we choose the encryption set with the same first bit as the descryption key. This greedy strategy works since (0 XOR 0) == (1 XOR 1) == 0 is always the minimal choice, compared to (0 XOR 1) == (1 XOR 0) == 1. Setting the leftmost bit to 0 is preferred. For the other bits, we can recursively do the same thing.
- | 1101 // decryption key = 13
--+----- // encryption set = {1, 5, 6, 11}
- | 0001
| 0101
| 0110
| 1011
--+-----
- | ----
| ----
| ----
With a sorted set, we can perform a binary search to limit our range of answers. If you notice, this is pretty similar to radix sort method. But this runs in O(log^2 N). Can we do better?
Now the question is, how do we represent this? Ignore the graph structure first in the original problem. Since we are branching at every bit, we can simply make a BINARY TRIE of 0’s and 1’s. A trie is basically a tree of suffixes. Left represents 0 while Right represents 1 (see Topcoder - Trie).
01101 // decryption key = 13
----- // encryption set = {1, 5, 6, 11, 20, 22, 26}
bit 1: [00001, 00101, 00110, 01011, 10100, 10110]
/ \
bit 2: [0001, 0101, 0110, 1011] [0100, 0110]
/ \ | \
bit 3: [001, 101, 110] [011] [100, 110] []
/ \ / \ / \
bit 4: [01] [01, 10] [11] [] [] [00, 10]
| \ / \ | \ / \
bit 5: [1] [] [1] [] [] [1] [0] [0]
Now this becomes interesting! To minimize a decryption key, we just have to go down the tree edges as we iterate through the bits. Be careful, if the branch to traverse to is empty, we should use the other branch, since we want to find an existing candidate to XOR with.
Since there are log N bits in an integer, traversing the trie will only take O(log N) time. I’ll leave it up to you to simulate the answer as an exercise. By the way, the answer for the above is (13 XOR 11) == 6.
Adding Persistence
Now that we know how to minimize XOR given a key and a trie, we can solve the problem by introducing persistence. A persistent trie is basically an immutable trie.
GOLDEN RULE OF PERSISTENCE
Every change in the trie returns a new trie such that the old version is not destroyed.
Though that sounds complicated, it’s actually straightforward; just make the insert operation return a new node instead of mutating:
Node insert(Node trie, ...) {
if (shouldInsertAtLeftNode)
return new Node(insert(trie.left, ...), tree.right);
else
return new Node(trie.left, insert(trie.right, ...));
}
Why do we need persistence, you ask? Well, this is useful for path-to-root problems! Notice how we can save a version of the trie in EVERY node and copy them down to children without costs. With this strategy, each node will have a trie that has ALL values from the root to the node, which is literally the problem we want to solve.
Solution with persistent XOR trie - O(Q log n)
Everything good so far? Going back to the main problem, let every node u own a persistent binary trie, say trie[u]. Then we have the following operations:
Update (set u as the parent of v with key k)
- Copy the parent’s trie then persistently insert the key
- One line:
trie[u] = insert(trie[v], k) - This lets
trie[u]have all the keys from the root to u!
Query
- Just query from
trie[u], simulating the XOR min/max algorithm above
There are Q queries and each operation costs O(log n), so we have solved it in O(Q log n). Hope that was helpful
13 Likes
This was really cool!
Up you go! Brilliant explanation!
Check out https://www.codechef.com/viewplaintext/13447819 (solution by @tapasjain01) for a very clean implementation for persistent data structure.
1 Like
Can anyone suggest some test cases for this problem ??
My code is showing wrong answer
I used offline solution using trie and dfs. Here is my solution.
https://www.codechef.com/viewsolution/13512384
Hi everyone!
@jtnydv25 and I have made a video editorial on this problem. It uses the persistent trie approach mentioned by @aditya730 to get an O(N*B) solution. You can have a look at it here:
Cheers!
3 Likes
I love how you explained it here in detail ^^