I came across a good problem in an algorithms textbook and I am not sure if my algorithm is correct or not.The problem goes like this:

Given a tree T where every vertex is assigned a label which is a positive integer, describe an algorithm to find the largest rooted minor that is a minimum heap. Over here A rooted minor of a rooted tree T is any tree obtained by contracting one or more edges. When we contract an edge (u, v), where u is the parent of v, the children of v become new children of u and then v is deleted. From this we can see that the root of the tree should always be part of any rooted minor.

What would be an optimized algorithm, could anyone please explain the recurrence relation for the DP solution. Any help would be appreciated!.

UPDATE: I have attached 2 possible solutions as comments, can someone verify the correctness please

My approach was to consider 2 subproblems opt_with and opt_without where we consider the node or not to calculate opt(root)

opt(root) = 1 + max(opt_with(child),opt_without(child)) {when child>root} + opt_without(child) {when child<root}

For every vertex v, we consider opt_with and opt_without: - opt_with(node) = 1 + max(opt_with(child),opt_without(child)) {when child>node} + opt_without(child) {when child<node}

But here we need to compare with node instead of root to satisfy heap property - opt_without(node) = opt_without(child) {child<root} + max(opt_with,opt_without) {child>root} Here we compare with root because we are not taking the so no need to satisfy heap property.

Wtf man, go to the strip club, you ain't got no bitches

Auto comment: topic has been updated by daneshtoshniwal (previous revision, new revision, compare).Here is another approach that uses dfs and then builds the solution in bottom up manner using take and not take. Here index is current value and num is the value of root for which we are checking:- (We have assumed its value to be its index, and so, all the node values to be distinct)

Required answer = dfs(index of root, value of root); And as we have assumed the both to be same, answer = dfs(value of root, value of root);

It's 1193B - Волшебное дерево with $$$w_j = 1$$$. It's not easy. Your solutions don't seem to work because, when you don't take a node, you lose information about what's the maximum value chosen in the subtree.

Note: the solution in the editorial is overkill. A solution that gets 100 points is the same as the one with $$$w_j = 1$$$, but also storing the frequencies of days in the multiset (so, without a segment tree).

Another note: the problem is harder than LIS (it's exactly the LIS if the tree is a line). So, if your solutions can't solve the LIS (in particular, if they are $$$O(n)$$$), they are wrong.

Could you please give an edge case for the Code that I have posted in the comments. It works for all cases I tried but I feel there might be some edge case.

Try lines of length $$$> 10$$$, and compare your answer with the length of the LIS.

I run the above code for the tree 10 -> 1 -> 11 -> 2 -> 3 -> 12 -> 13 -> 5 -> 7 -> 14 -> 8 -> 9 and got the correct answer which is 5.

Is this the correct case ? Also, could you please analyse the complexity of the code in the comments. I think it should be O(n) because we are considering every node a constant number of times. But I don't know how to explain it properly. Can you/anyone write it a bit formally. Thanks

Isn't the correct answer $$$7$$$?

According to the question, root should always be part of the rooted minor. This is because we can never delete the root of the Tree by contracting an edge since it does not have a parent. So our answer should always contain the node with value 10.

Ok sorry, I thought the input was in the opposite direction.

Can you send the complete code? (I will try to test)

Sample input would be to replace nodes with 2, and pass the input as 8 1 11 11 2 9 10

Here 8 has 1 child which is 11 and 11 has 2 children which are 9 and 10. The answer should be 3 (heap consists of 8,9,10). Call dfs(8,8) since 8 is root.

Appreciate your help :)

If my understanding of the input format is correct, this should print $$$4$$$, but it prints $$$5$$$.

can you please get the right algo for this question?

Yeah thanks, I tried to resolve the same using 2D DP where I store both index,num in dp and it worked. Also can you please let me know the running time of the above algo, is it O(n) ?

Your first algorithm is $$$O(n)$$$, but it's wrong (because a correct algorithm should run at least in $$$O(n \log n)$$$), so it doesn't matter.

The 2D DP should be $$$O(n^2)$$$.

Ok thanks. So the 2D DP one is correct and runs in $$$O(n^2)$$$ right ? It won't fail for any case right ?

Also, do you have any idea for nlogn solution that works. Is it similar to the first comment I posted on this blog ?

If you have written the 2D DP correctly, it's correct :D

In my first comment, I have posted a $$$O(n \log n)$$$ solution.

Could you please explain how do we backtrack to get the final rooted minor which is a heap in our solution. Will it be like the following -

We start doing DFS from the root node, if its nottake value > take value, we contract this edge and not add it in the final solution.

For this we need to store values of take, nottake separately.

Read this blog. It should work in any DP without memory optimizations.

Sorry for repetitive questions but you have been very helpful and appreciate it.

Is the above function for backtracking and getting the largest rooted minor which is a min heap correct ? Here dp[index][num][1] corresponds to take and dp[index][num][0] corresponds to nottake. If correct, time complexity is O(N) ?

Explanation if someone wants to understand:

Case 1 opt take > opt nottake: In this case, since we are taking the current node, we call the maketree() function for the children of this node and pass value(node) as the parameter to make sure heap property is satisfied. Since we are taking this node, we create an edge between the calling node and this node in a new tree which will finally becomes our largest min-heap rooted minor.

Case 2 opt take ≤ opt nottake: In this case, since we are not taking the current node, we will call the maketree() function for the children of this node but this time we pass the same val as parameter. This is because we don’t need to check for heap property for current node

Once again, thanks a lot for your help.

I think I don't understand something in your code.

`maketree`

is called only once for each node. Then, for each`index`

, you create at most one edge to other nodes.thanks