negativez2's blog

Optimization for dp on tree needed.
By negativez2, history, 5 years ago, In English

Statement:

Given a tree of N nodes, every node i have a value A[i].

You have to find the maximum value you can get by picking a subtree (a subgraph of the tree which is also a tree) of exactly K nodes.

Constrain : 1 <= K,N <= 1000

This can be solve in O(n^3) by a simple dp, but after spending time thinking, I couldnt find a better solution. Can anyone solve this in O(n^2) ?

Help is appreciated.

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Perhaps I don't understand something about this problem, but why can't you just do two rounds of DFS?

1st round cumulates the size of each node's subtree. 2nd round cumulates the total value of a subtree.

Then do an O(n) for loop passing through each node, checking if its first round result = K, and then taking the maximum of those second round results.

I don't think DP is needed. Are you sure you understood the problem correctly? ;}

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Tree is not rooted, so connected component do not have root is DFS tree too.

    I think this is standard knapsack dp in $$$O(n^2)$$$: $$$dp_{i,j}$$$ — maximum result for node $$$i$$$, where $$$i$$$ is included in result and $$$j$$$ its children.

    Now it is standard knapsack over direct sons of node $$$i$$$, just iterate until size of each node, not $$$n$$$ and it will be good complexity.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      Yup, it's $$$O(n^2)$$$. The code below will always print a number that doesn't exceed $$$n^2$$$ because every pair of vertices contributes to the number of operations at most once (when $$$v$$$ is their LCA).

      int operations = 0;
for(int v : vertices)
  for(int child1 : children[v])
    for(int child2 : children[v])
      operations += size_of_subtree[child1] * size_of_subtree[child2];
cout << operations;
      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I am not sure how this is relevant to the time complexity analysis, can you elaborate?

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          To compute dp of a parent, we iterate over the number of vertices taken in child1 and child2.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            I thought that we can take more than 2 children, right?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              Merge them one by one

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Oh hm, this makes sense. Thanks a lot!

                → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it -8 Vote: I do not like it

                Can you please share your code Errichto

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Share your code first ;p You have thousands of problems with code in the Internet. Why do you need me to implement this one too?

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it -8 Vote: I do not like it

                  Actually when I read the problem i thought it could be implemented with in-out dp but now the solution says O(n^2). I just wanted to know the right answer to this. Btw its 3 AM and you want me to code !!

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it +9 Vote: I do not like it

                  Oh, I'm sorry I wanted you to code xd

                  I don't know what in-out dp is, but you can implement n^3 solution and if will be n^2 if you iterate up to child subtree size only.

                  → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think it's still O(n^3) because you have to iterate the number of i's children also.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Why would you do that? You only care about the number of taken vertices and its value is up to size_of_subtree[child]

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Do you mean dp[i][j] where j is the number of direct children of i or total number of vertices in subtree of i that we take?

      EDIT: got it, j should be the total number of vertices we take. Then it makes sense.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Can you please share your code allllekssssa

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      If so, you can modify my solution to loop over the n possible roots. That would be O(n) * O(n) = $$$O(n^2)$$$.

      → Reply