Editorial for WC '15 Contest 1 S4 - Chocolate Milk

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Once again, we can see the system as a graph with $N$ ~N~ nodes (cisterns). Due to the fact that there are $N-1$ ~N-1~ edges and no cycles, we can also see that the graph is a tree. You can read more about properties of trees from this article. In this case, we can see that cistern $1$ ~1~ is the root of the tree, and that cistern $C_i$ ~C_i~ is the parent of node $i$ ~i~. In addition, the problem conveniently guarantees that node $i$ ~i~ is the parent of node $j$ ~j~ if and only if $i < j$ ~i < j~. Everything about it points towards a solution using the classic dynamic programming (DP) on a tree approach. Many articles for DP on a tree can be found with a quick search online.

Let our dynamic programming state $DP[i][j]$ ~DP[i][j]~ represent the maximum amount of chocolate milk which can flow into cistern $i$ ~i~ (from all sources, direct or indirect), after $j$ ~j~ of the pipes in $i$ ~i~'s subtree (not including the pipe leading down from it, if any) have been upgraded. The final answer (the maximum amount of chocolate milk which can flow into cistern $1$ ~1~ after $K$ ~K~ pipes have been upgraded) will then be $DP[1][K]$ ~DP[1][K]~.

For each cistern $i$ ~i~ from $N$ ~N~ down to $1$ ~1~, we'll compute $DP[i][0 \dots K]$ ~DP[i][0 \dots K]~ all at once based on the DP values of its children. For each of its child $c$ ~c~, we can choose to distribute some number $u$ ~u~ of pipe upgrades to its subtree, and we can choose to either upgrade to pipe from $u$ ~u~ to $i$ ~i~ (in which case the amount of flow into $i$ ~i~ will be $DP[c][u]$ ~DP[c][u]~), or not (in which case it'll be $\max\{DP[c][u], F_u\}$ ~\max\{DP[c][u], F_u\}~). If $i \ge 2$ ~i \ge 2~, an additional flow of $P_i$ ~P_i~ will also always be added. We can explore all possible decisions regarding how to distribute pipe upgrades amongst $i$ ~i~'s children using secondary DP, letting $DP2[j][k]$ ~DP2[j][k]~ be the maximum flow from the first $j$ ~j~ children with $k$ ~k~ pipe upgrades. Letting $M_i$ ~M_i~ be the number of children that cistern $i$ ~i~ has, we can then copy over the results into the primary DP, with $DP[i][k] = DP2[M_i][k]+P_i$ ~DP[i][k] = DP2[M_i][k]+P_i~ (for $0 \le k \le K$ ~0 \le k \le K~).

The secondary DP takes $\mathcal O(M_i \times K^2)$ ~\mathcal O(M_i \times K^2)~ time to compute for each cistern $i$ ~i~. Note that the sum of all $M_i$ ~M_i~ for all $i = 1 \dots N$ ~i = 1 \dots N~ is equal to $N-1$ ~N-1~, since every cistern (except the root) is the child of one other cistern, so this DP (and the whole solution) will take a total of $\mathcal O(N \times K^2)$ ~\mathcal O(N \times K^2)~ time.

Comments

There are no comments at the moment.