PrevNext
Rare
 0/6

DP on Trees - Combining Subtrees

Author: Benjamin Qi

?

Focus Problem – read through this problem before continuing!


This was the first problem I saw that involved this trick.

Solution

For two vectors aa and bb, define the vector c=abc=a\oplus b to have entries ci=mink=0i(ak+bik)c_i=\min_{k=0}^i\left(a_k+b_{i-k}\right) for each 0i<size(a)+size(b)10\le i < \text{size}(a)+\text{size}(b)-1.

Similar to the editorial, define dp[x][0][g]\texttt{dp[x][0][g]} to be the minimum cost to buy exactly gg goods out of the subtree of xx if we don't use the coupon for xx, and define dp[x][1][g]\texttt{dp[x][1][g]} to be the minimum cost to buy exactly gg goods out of the subtree of xx if we are allowed to use the coupon for xx. We update dp[x][0]\texttt{dp[x][0]} with one of the child subtrees tt of xx by setting dp[x][0]=dp[x][0]dp[t][0]\texttt{dp[x][0]}=\texttt{dp[x][0]}\oplus \texttt{dp[t][0]}, and similarly for dp[x][1]\texttt{dp[x][1]}.

Code

The editorial naively computes a bound of O(N3)\mathcal{O}(N^3) on the running time of this solution. However, this actually runs in O(N2)\mathcal{O}(N^2)!

Time Complexity of Merging Subtrees

The complexity can be demonstrated with the following problem:

You have an list of NN ones and a counter initially set to 00. While the list has greater than one element, remove any two elements aa and bb from the list, add aba\cdot b to the counter, and add a+ba+b to the list. In terms of NN, what is the maximum possible value of the counter at the end of this process?

Solution

Problems

StatusSourceProblem NameDifficultyTags
COCINormal
CFNormal
IOINormal
CFNormal
Show TagsDP
DMOJHard
Show TagsNT

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext