×

Setter- Alei Reyes
Tester- Pranjal Jain
Editorialist- Abhishek Pandey

Medium-Hard

Dp on Tries

# PROBLEM:

Given a function $W$ and a set of non-negative integers $S_x$, you have to find the value $W$ takes if we remove $i'th$ element from the set. You need to do this for all $i=1$ to $N$. Please read rules to calculate $W$ from problem statement itself.

# QUICK-EXPLANATION:

Key to AC- Realizing that we can build trie from Least Significant Bit (LSB) to Most Significant Bit (MSB). This allows us to see that at any time, the two leaves with deepest LCA (Least Common Ancestor) are the numbers to be removed from the set in this operation. Rest is application of dynamic programming on it.

The first thing to handle is finding which $2$ elements to remove from the set. Realize that, if we build trie from LSB to MSB, then automatically the leaf nodes with deepest LCA (LCA farthest from root) are the numbers to remove first. Hence, by doing a simple DFS on trie, we can find solution to the problem in a bottom-up manner.

Define a pair of two things $< W(u), R(u) >$. $W(u)$ represents the answer for $u$ and sub-tree for $u$, and $R(u)$ represent any of the remaining unpaired element. Say we need to calculate answer for parent of $u$, say $v$. We will this as follows-

$W(v)=W(u_1) \oplus W(u_2)$ where $u_1$ and $u_2$ are children of $v$. (If $v$ has only $1$ child, then take $W(u_2)=0$. If $v$ is a leaf, then $W(u_1)=0$ as well). Also, if both $u_1$ and $u_2$ both had an unpaired element, then we pair them both and additionally do $W(v)=W(v) \oplus [(R(u_1) \oplus R(u_2))-1]$.

$R(v)=$ Any unpaired element/leaf left in subtree. Note that, if $v$ is a leaf, then it is by default unpaired. Hence, if $v$ is a leaf, then $W(v)=0$ and $R(v)=val$ where $val$ is the value represented by the leaf.

Calculate $< W(u),R(u) >$ considering all elements in the trie.

Notice that when removing an element from the set, at most $\approx 60$ nodes will change their value. Values of rest of the tree will remain the same. Hence, we traverse back the required path to recalculate value if that particular element is absent, and get rest of the values by memoization

# EXPLANATION:

Ouch, that was surely some "Quick" Explanation? :). If you're looking for a concise editorial, quick explanation has it all. In case one or more points are/were not clear, hop on to the appropriate section.

The quick explanation deals with all the important topics. We will elaborate the points on quick explanation, and proceed to conclude the editorial.

1. Handling the congruency thing.

At first sight, its not very trivial how we are supposed to get the two elements to pick from set.

Notice the effect of modulo $2^i$ operation. You will see that all bits after $i$ become $0$, and all bits from $[0,i)$ remain the same. An example to illustrate the point is in the tab below.

View Content

With this in mind, and lets see how to utilize this fact for our question. Usually, when we have to do such bit-wise operations, (eg- Find subarray with maximum XOR). The point is, that tries are something which we can think of when our problem involves a lot of bit manipulation (especially XOR).

Notice that, if we build the trie from LSB to MSB, we can solve this part efficiently. Think on what would a LCA of $2$ leaves mean in this regard. LCA of $2$ leaves will mean that, except for part from leaf to LCA, every other bit is same in both these numbers. Since we started from LSB to MSB, it will mean that every bit from LSB to the bit represented by LCA are same in those numbers. The farther this LCA from the root, the more bits in common we get.

Hence, the farthest leafs with farthest LCA from root will be removed first, and so on. Hence, this allows us to traverse the trie using DFS to calculate our dp values in a bottom up fashion.

2. How to use DFS with above observation to calculate Dps-

(Optional -If you are not sure on how bottom up DP is calculated, you can read the box below.)

View Content

One important thing to realize is that, we only care about which element to pair with whom, and not the order in which they are paired. In other words, say we know that $(a,b)$ are paired, then we dont care if we calculate $W(u) \setminus (a,b)$ first of $W(\{a,b\})$ first. $(\because A \oplus B \equiv B \oplus A)$.

To prove above, lets do a dry run. Say our current set to calculate $W$ of is $S_x= \{a,b,c,d,e\}$, and that we know that we have to pair $a$ with $b$ and $c$ with $d$. Hence, our $W$ is calculated as-

$W= W(a,b,c,d,e)= W(a,b) \oplus W(c,d,e) = (a \oplus b -1 \oplus [W(c,d) \oplus W(e)] = (a \oplus b -1) \oplus (c \oplus d -1) \oplus e$

If our pairing is correct, i.e. still pair elements as before, then we can as well remove pair $(c,d)$ first, as shown below-

$W= W(a,b,c,d,e)= W(c,d) \oplus W(a,b,e) = (c \oplus d -1) \oplus [W(a,b) \oplus W(e)] = (c \oplus d -1) \oplus (a \oplus b -1) \oplus e$

Hence, what we should realize is that, the condition of "has remainders congruent with highest power of $2$" is more to make us pair elements correctly, than to tell in which order we have to remove. You can find further discussion on it in next paragraph $-$ its not a very trivial observation to make, so take your time going through the proof and discussion.

For above point, lets take an example. Say, we are at node $u$, and there exists some leaves with deeper LCA, which are not in subtree of $u$ and are in, say, subtree of some other node $v$. Ask yourself, does calculating answer for subtree of $u$ first affect answer? Think a while. The answer will be in the box below.

View Content

The above two are important to realize the proof of correctness of DFS.

3. DP recurrences-

Notice that all the operations in calculation of $W$ (except the one where $W$ has two elements only) are $XORS$. As clear from above, we can compute answer for each sub-tree independently, as except the remaining unpaired leaves, all leaves in a subtree will be paired with each other. (When I say leaf, remember that leaves are storing the value of that element. So pair of leaves is another way of saying pairing of elements).

Realizing this, and it becomes easy to compute $W$. We first calculate $W$ for complete set. We will discuss removals soon. By expansion of $W$, and our subtree argument, lets reason out on the recurrence-

• $W(v)=W(u_1) \oplus W(u_2)$ where $u_1$ and $u_2$ are children of $v$ - This part comes from the fact that, $W(u_1)$ and $W(u_2)$ are holding answers for elements/leaves which are paired in their subtree. The final answer, obviously depends on this. Also, we saw in expansion that final answer is XORSUM of different $W$ values, hence XOR of values of its subtree is done to find $W$. Obviously, if either or both of $u_1$ and $u_2$ do not exist, then their corresponding $W$ value is $0$.
• If both $u_1$ and $u_2$ both had an unpaired element, then we pair them both and additionally do $W(v)=W(v) \oplus [(R(u_1) \oplus R(u_2))-1]$. - This part comes from the fact that, if a subtree has odd number of leaves, it means we will have one leaf left unpaired. Since we want to obey the condition of remainders being congruent to highest power of $2$, we wish to pair it as soon as possible with another unpaired leaf as we traverse the tree in a bottom-up fashion. Once we find another unpaired leaf to pair it with, we pair it and add the correspondign value to answer.
• $R(v)=$ Any unpaired element/leaf left in subtree. Note that, if $v$ is a leaf, then it is by default unpaired. Hence, $R(u)$ just holds value of unpaired leaf/element and is easy to compute. If we have traversed the entire tree and still have an odd leaf (due to odd number of elements in the set), we use the definition of $W$ for a single element and XOR $W(R(u))$ with calculated answer.

Lets reason out on our base case for a leaf-

• Leaf is a single element. Hence, no pairing is possible. $W(L)=0 \oplus 0=0$ as discussed in recurrence.
• A single leaf is, by default, unpaired. Hence $R(L)=val$ where $val$ is value of element represented at leaf.

Now we will proceed to the last part of calculating the answer if an element from the set is removed. As a hint to people who want to try it themselves, its based on recalculating the value of $W$ by traversing the tree - using memoized values of $W$ for unchanged parts of tree, and hence calculating values for only leftover $log S_i \approx 60$ nodes of the tree.

An implementation of the function is to calculate recurrence is given below-

View Content

4. Dealing with removals.

One of the elegant ways of doing this, is calculate $W$ ignoring the leaf corresponding to element we have to remove. Most of the tree remains the same, only the $60$ nodes in trie corresponding to path to that leaf are to be handled.

Hence, what we do is, we start from root of the tree, and with initial value of answer as $0$. Now, we proceed with DFS as before. If the current node in DFS does not lie on path to removed leaf, we simply use back the memoized value. Else, if it lies on path to removed leaf, we recurse down the path to calculate answer with this leaf removed. This is equivalent to, returning a value of $< W(Leaf)=0,R(Leaf)=N/A>$ on reaching this leaf. Note that we are NOT traversing the entire trie again and again, we are just traversing the path to the removed leaf, and using the old memoized values we calculated earlier for parts where no change has occured.

A brief implementation of same can be found in tab below-

View Content

# SOLUTION

View Content
View Content

$Time$ $Complexity=O(NLog S_i)$ where $S_i$ denotes the maximum value of an element in the set.
$Space$ $Complexity=O(N_logSi)$ where $S_i$ denotes the maximum value of an element in the set.

# CHEF VIJJU'S CORNER :D

1. Setter's Notes-

View Content

2. Tester's Notes-

View Content

3. Related Problems-

This question is marked "community wiki".

15.4k12066
accept rate: 18%

19.8k350498541

 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:

×2,169
×1,343
×726
×47