Can someone please explain how to solve GothamPD ? asked 18 May '17, 15:37

Before diving into the persistent part, you must understand how to solve it in brute force. Brute Force  O(QN)Update
Query
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:
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:
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
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).
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 Adding PersistenceNow 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 PERSISTENCEEvery 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
Why do we need persistence, you ask? Well, this is useful for pathtoroot 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 Update (set
Query
There are answered 19 May '17, 09:45
Up you go! Brilliant explanation!
(19 May '17, 11:01)
I love how you explained it here in detail ^^
(22 Jun '17, 19:59)

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 answered 18 May '17, 16:50

This involves persistent data structures.I hope you are aware about xor minimsation/maximisation using tries.If not check out this first https://threadsiiith.quora.com/TutorialonTrieandexampleproblems 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 http://www.geeksforgeeks.org/persistentdatastructures/ https://blog.anudeep2011.com/persistentsegmenttreesexplainedwithspojproblems/ http://www.geeksforgeeks.org/persistentsegmenttreeset1introduction/ 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 :) answered 18 May '17, 15:54
3
Here's my solution using this method if you need some code to relate to: link :)
(18 May '17, 22:36)

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 answered 18 May '17, 19:09

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! answered 24 May '17, 21:09

Enter my custom randomized MOlike 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. On the first try i got TLE, but on the second all passed :) Link to solution: answered 19 May '17, 07:45

Check out https://www.codechef.com/viewplaintext/13447819 (solution by @tapasjain01) for a very clean implementation for persistent data structure. answered 20 May '17, 00:13

@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 answered 18 May '17, 16:37
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
(18 May '17, 16:48)

Can anyone suggest some test cases for this problem ?? My code is showing wrong answer answered 23 May '17, 00:05

I used offline solution using trie and dfs. Here is my solution. https://www.codechef.com/viewsolution/13512384 answered 23 May '17, 12:35
