### daneshtoshniwal's blog

By daneshtoshniwal, history, 2 months ago,

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

• +16

 » 2 months ago, # |   0 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 childnode} + opt_without(child) {when childroot} Here we compare with root because we are not taking the so no need to satisfy heap property.
 » 2 months ago, # |   -26 Wtf man, go to the strip club, you ain't got no bitches
 » 2 months ago, # |   0 Auto comment: topic has been updated by daneshtoshniwal (previous revision, new revision, compare).
 » 2 months ago, # | ← Rev. 2 →   -9 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) vector adj[1000]; vector dp(1000); vector tree(1000,false); int dfs(int index, int num){ if(dp[index] != 0 and index>num){ return(dp[index]); } int nottake = 0; for(int i=0;i= num){ for(int i=0;i
 » 2 months ago, # | ← Rev. 3 →   0 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.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 2 months ago, # ^ |   0 Try lines of length $> 10$, and compare your answer with the length of the LIS.
•  » » » » 2 months ago, # ^ |   0 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
•  » » » » » 2 months ago, # ^ |   0 Isn't the correct answer $7$?
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » » 2 months ago, # ^ |   0 Ok sorry, I thought the input was in the opposite direction.Can you send the complete code? (I will try to test)
•  » » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 #include using namespace std; vector adj[1000]; vector dp(1000); vector tree(1000); int dfs(int index, int num){ // dp to store previous values if(dp[index] != 0 and index>num){ return(dp[index]); } int nottake = 0; for(int i=0;i= num){ for(int i=0;i0){ tree[index]=index; } else{ tree[index]=-1; } // cout<>x; int n; cin>>n; for(int j=0;j>c; adj[x].push_back(c); } } // run with root nodes value twice cout<
•  » » » » » » » » » 2 months ago, # ^ | ← Rev. 4 →   0 5 1 1 5 5 1 6 6 1 2 2 1 3 3 1 4 If my understanding of the input format is correct, this should print $4$, but it prints $5$.
•  » » » » » » » » » 2 months ago, # ^ |   0 can you please get the right algo for this question?
•  » » » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 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) ?
•  » » » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 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)$.
•  » » » » » » » » » 2 months ago, # ^ |   0 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 ?
•  » » » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 If you have written the 2D DP correctly, it's correct :DIn my first comment, I have posted a $O(n \log n)$ solution.
•  » » » » » » » » » 2 months ago, # ^ |   0 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.
•  » » » » » » » » » 2 months ago, # ^ |   0 Read this blog. It should work in any DP without memory optimizations.
•  » » » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Sorry for repetitive questions but you have been very helpful and appreciate it. void maketree(int index, int num){ if(dp[index][num][1] > dp[index][num][0]){ for(auto x: adj[index]){ maketree(x,index); } if(index!=num) newadj[num].push_back(index); } else{ for(auto x: adj[index]){ maketree(x,num); } } } 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 nodeOnce again, thanks a lot for your help.
•  » » » » » » » » » 2 months ago, # ^ |   0 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.
•  » » 2 months ago, # ^ |   0 thanks