×

How to solve GothamPD from MAY17?

 4 4 Can someone please explain how to solve GothamPD ? asked 18 May '17, 15:37 1.1k●1●10 accept rate: 10%

Before diving into the persistent part, you must understand how to solve it in brute force.

Brute Force - O(QN)

Update

1. Set parent of u to be v

Query

1. Climb all ancestors and get all their keys
2. 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.

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)

1. Copy the parent's trie then persistently insert the key
2. One line: trie[u] = insert(trie[v], k)
3. This lets trie[u] have all the keys from the root to u!

Query

1. 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 :)

5★hikarico
1.8k515
accept rate: 28%

Up you go! Brilliant explanation!

(19 May '17, 11:01)

I love how you explained it here in detail ^^

(22 Jun '17, 19:59)
 12 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 6★praran26 137●2 accept rate: 0% This was really cool! (19 May '17, 10:06) ankesh185★
 10 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 http://www.geeksforgeeks.org/persistent-data-structures/ https://blog.anudeep2011.com/persistent-segment-trees-explained-with-spoj-problems/ http://www.geeksforgeeks.org/persistent-segment-tree-set-1-introduction/ 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 127●5 accept rate: 12% 3 Here's my solution using this method if you need some code to relate to: link :) (18 May '17, 22:36) meooow ♦6★
 4 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 5★sdssudhu 844●2●10 accept rate: 13%
 3 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. answered 18 May '17, 15:45 226●1●3 accept rate: 7% 1 since it was a dynamic tree and online soln reqd. how do u do heavy light decomposition on dynamic trees ? (18 May '17, 17:09) 1 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. (18 May '17, 18:10)
 3 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: Gotham Police Department Cheers! answered 24 May '17, 21:09 4★gkcs 2.5k●1●10●26 accept rate: 9%
 1 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: https://www.codechef.com/viewsolution/13450801 answered 19 May '17, 07:45 4★vasja 515●1●6 accept rate: 7%
 1 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 51●3 accept rate: 0%
 0 @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 4★ps_1234 49●3 accept rate: 0% 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)
 0 Can anyone suggest some test cases for this problem ?? My code is showing wrong answer https://www.codechef.com/viewsolution/13566224 answered 23 May '17, 00:05 1 accept rate: 0%
 0 I used offline solution using trie and dfs. Here is my solution. https://www.codechef.com/viewsolution/13512384 answered 23 May '17, 12:35 -1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×165
×138
×5

question asked: 18 May '17, 15:37

question was seen: 2,282 times

last updated: 22 Jun '17, 19:59