genesis's blog

DP on Tree with Prefix sum
By genesis, history, 35 hours ago, In English

Can anyone please explain how this problem can be solved?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
34 hours ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

First, you can construct a directed graph consisting of $$$n$$$ edges $$$i \rightarrow A_i$$$ (known as sunflower graph).

The sunflower would look like a cycle and some trees from other nodes.

Example image

Compress the cycle to be a single node and make it the root, so it will become a normal tree.

Now you can do $$$O(N^2)$$$ DP like this:

$$$dp(i, j) = $$$ How many ways to assign numbers to subtree $$$i$$$, such that the assigned number is $$$j$$$.

The formula: $$$dp(i, j) = \prod\limits_{c \in adj(i)}{ \sum\limits_{v = 1}^{v \le j} {dp(c, v)} }$$$

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

    wouldn't it be the multiplication of the valid children states, instead of summation?

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

      Thanks I was wrong, I'll update it

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

    Isn't this $$$O(N \cdot M^2)$$$? You can make it $$$O(N \cdot M)$$$ by using prefix sum, or changing the state: dp(i, j) = number of ways to choose numbers in subtree of $$$i$$$, where the number assigned to $$$i$$$ is $$$\le j$$$. Then: $$$dp(i, j) = dp(i, j-1) + \prod dp(c_k, j)$$$, where $$$c$$$ are the children of $$$i$$$.

    → Reply
»
34 hours ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Let's construct a directed graph where each node correcponds to an element of x and an edge from u to v means that $$$x[u]\leq x[v]$$$ (i.e. $$$v=a[u]$$$).

The first thing we botice is that since there are n nodes and n edges, it's a functional graph, which means each component will have exactly one cycle, with all other nodes being in a path that leads to the cycle. The elements whose nodes are part of the cycle need to be equal, since they all need to be smaller or equal than the others.

After we find the cycle of each component, we can use all the nodes in the cycle as a single node, so we now have a rooted tree with that node as the root.

Now we use DP to find the number of ways to fill the tree with values. Let $$$dp[i][k]$$$ be the number of ways to fill the subtree of i with values if $$$x[i]\leq k$$$.

For the leaves, $$$dp[i][k]=k$$$, since we can assign any value from 1 to k. For all other nodes, we'll try every value from 1 to k and see in how many ways we can fill the node's childern's subtrees if we choose that value: $$$dp[i][k] = \sum\limits_{x=1}^{k} \prod\limits_{c\in childen} dp[c][x]$$$.

Its complexity is $$$O(nm^2)$$$ which is too much, but we can speed it up by using the previous values of k to calculate the current ones:
$$$dp[i][1] = \prod\limits_{c\in childen} dp[c][1]$$$
$$$dp[i][k] = dp[i][k-1] + \prod\limits_{c\in childen} dp[c][k-1]$$$
Now the complexity is $$$O(nm)$$$.

The number of ways to fill each tree entirely is dp[r][m], where r is the root. The final step is to multiply these values for all trees in the forest / components in the graph.

→ Reply
  • »
    »
    33 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
     dp[i][k] = sum(product(dp[c][x] for each child c) for each value x).

    can you please elaborate this part?

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

      okay, got it, thank you!!

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

      $$$\sum\limits_{x=1}^{k} \prod\limits_{c\in childen} dp[c][x]$$$
      (Yeah, I just figured out how to add equations)

      If the value of the current node is $$$x$$$, we have $$$dp[c][x]$$$ ways for the subtree of each child $$$c$$$, so we multiply these values. We then add the products for each possible x.

      → Reply