daneshtoshniwal's blog

By daneshtoshniwal, history, 12 months ago, In English

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

  • Vote: I like it
  • +16
  • Vote: I do not like it

| Write comment?
»
12 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

It's 1193B - Magic Tree 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.

  • »
    »
    12 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            12 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              12 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

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

              • »
                »
                »
                »
                »
                »
                »
                »
                12 months ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it
                #include<bits/stdc++.h>
                using namespace std;
                
                vector<int> adj[1000];
                vector<int> dp(1000);
                vector<int> 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<adj[index].size();i++){
                		nottake += dfs(adj[index][i],num);
                	}  
                	int take = 0;
                	if(index >= num){
                		for(int i=0;i<adj[index].size();i++){
                			take += dfs(adj[index][i], index);
                		}
                		take++;
                	}
                	dp[index] = max(take,nottake);
                	if(dp[index]==take && take+nottake>0){
                		tree[index]=index;
                	}
                	else{
                		tree[index]=-1;
                	}
                	// cout<<take<<" "<<nottake<<" "<<index<<endl;
                	return(max(take,nottake));
                }
                
                
                int main(){
                	// HOW TO RUN -
                	// Replace n with the number of nodes that have children (hardcode)
                	int nodes;
                	// For input, put the value of the nodes that have children and its number of children. 
                	// Then enter the values of the children
                	for(int i=0;i<nodes;i++){
                		int x;
                		cin>>x;
                		int n;
                		cin>>n;
                		for(int j=0;j<n;j++){
                			int c;
                			cin>>c;
                			adj[x].push_back(c);
                		}
                	}
                	
                	// run with root nodes value twice
                	cout<<dfs(7,7)<<endl;
                	
                }
                

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 months ago, # ^ |
                  Rev. 4   Vote: I like it 0 Vote: I do not like it
                  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$$$.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 months ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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) ?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 months ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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)$$$.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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 ?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 months ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 months ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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 node

                  Once again, thanks a lot for your help.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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.