Editorial for WC '15 Contest 1 S4 - Chocolate Milk
Submitting an official solution before solving the problem yourself is a bannable offence.
Once again, we can see the system as a graph with nodes (cisterns). Due to the fact that there are
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
is the root of the tree, and that cistern
is the parent of node
. In addition, the problem conveniently guarantees that node
is the parent of node
if and only if
. 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 represent the maximum amount of chocolate milk which can flow into cistern
(from all sources, direct or indirect), after
of the pipes in
'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
after
pipes have been upgraded) will then be
.
For each cistern from
down to
, we'll compute
all at once based on the DP values of its children. For each of its child
, we can choose to distribute some number
of pipe upgrades to its subtree, and we can choose to either upgrade to pipe from
to
(in which case the amount of flow into
will be
), or not (in which case it'll be
). If
, an additional flow of
will also always be added. We can explore all possible decisions regarding how to distribute pipe upgrades amongst
's children using secondary DP, letting
be the maximum flow from the first
children with
pipe upgrades. Letting
be the number of children that cistern
has, we can then copy over the results into the primary DP, with
(for
).
The secondary DP takes time to compute for each cistern
. Note that the sum of all
for all
is equal to
, 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
time.
Comments