Indian Computing Olympiad

Training Material


Dynamic programming on trees→Rivers (IOI 2005)

Nearly all of the Kingdom of Byteland is covered by forests and rivers. Small rivers meet to form bigger rivers, which also meet and, in the end, all the rivers flow together into one big river. The big river meets the sea near Bytetown.

There are N lumberjacks' villages in Byteland, each placed near a river. Currently, there is a big sawmill in Bytetown that processes all trees cut in the Kingdom. The trees float from the villages down the rivers to the sawmill in Bytetown.

The king of Byteland decided to build K additional sawmills in villages to reduce the cost of transporting the trees downriver.

After building the sawmills, the trees need not float to Bytetown, but can be processed in the first sawmill they encounter downriver. Obviously, the trees cut near a village with a sawmill need not be transported by river. It should be noted that the rivers in Byteland do not fork. Therefore, for each village, there is a unique way downriver from the village to Bytetown.

The king's accountants calculated how many trees are cut by each village per year. You must decide where to build the sawmills to minimize the total cost of transporting the trees per year. River transportation costs one cent per kilometre, per tree.

Example:

   Bytetown        1            1
      ---    1    ---    10    ---     5    ---
     | 0 |<------| 1 |<-------| 2 |<-------| 3 | 10
      ---         ---          --- <--      ---
                                      |
                                      |3
                                      |     ---
                                       ----| 4 | 1
                                            ---
                                            

The nodes {1,2,3,4} are villages and the edges are rivers. The number of trees to be cut is written by the side of each village. The length of each river is written by the edge. 2 sawmills are to be placed.

The solution in this case is to place the mills at villages 2 and 3, which incurs a cost of 4.

Input: The number of villages N (≤ 100), the number of additional sawmills to be built K (≤ 50), the number of trees cut near each village W_i (≤ 10000), and descriptions of the rivers,

Output: The minimal cost of river transportation after building additional sawmills.

Solution

Observe that the rivers form a tree. Use dynamic programming. What are the important parameters?

We need to consider every possible village as a candidate. If we place a sawmill at v, it "controls" a subtree of which it is the root. What is the cost of this subtree?

We need to know how many sawmills have already been placed in the subtree rooted at v, say r.

We also need to take care of the next sawmill downstream between v and Byteland, where the logs at v will land up if there is no sawmill at v. Instead of considering the identity of the village downstream, we will use as a parameter the distance L of that village from Byteland. This uniquely specifies the village.

As a simplifying assumption, assume we have at most two children at each node. We compute two quantities.

Thus, we want to compute two cost functions.

  • Cost1(v,r) : min cost in subtree rooted at v with r sawmills with one mill at v
  • Cost2(v,r,L) : min cost in subtree rooted at v with r sawmills without one mill at v, where L is the depth from Byteland of the nearest sawmill downstream from v

Let v have children w1 and w2.

Then

                         i sawmills below w1     i sawmills below w1
                          one sawmill at w1       no sawmill at w1
                                      \               /
Cost1(v,r) =     min         { min[ Cost1(w1,i),Cost2(w1,i,depth(v))],
             i,j s.t i+j=r-1   min[ Cost1(w2,j),Cost2(w2,j,depth(v))] }
                                      /               \
                         j sawmills below w2     j sawmills below w2
                          one sawmill at w2       no sawmill at w2
      

Thus

Cost2(v,r.L) =  Trees(v)*(depth(v) - L)  /*  Cost of trees at v travel upstream     */
                  +
                 min         { min[ Cost1(w1,i),Cost2(w1,i,L)],
             i,j s.t i+j=r     min[ Cost1(w2,j),Cost2(w2,j,L)] }
      

Now, what happens when we have more than 2 children? We have to analyze all ways of splitting r among the children.

How do we efficiently deal with the problem of considering all partitions of K as KU?

Restructure the children of a node as a skew tree:

     -- v--                         v
    /  / \  \        ===>          / \
   u1 u2 u3 u4                   u1   x1
                                     /  \
                                    u2   x2
                                        /  \
                                       u3   x3
                                           /
                                         u4
      

We have reduced the degree of each node. We set the number of trees cut at {x1,x2,x3} to be 0. We copy the costs of (u2,v), (u3,v), (u4,v) to the edges (u2,x1), (u3,x2), (u4,x3), respectively and set cost of the new edges (x3,x2), (x2,x1), (x1,v) to be 0. This ensures that the modified tree has the same costs as the original one.

In this way, we can transform the original tree into a new one with the same cost function for which the cost is easier to compute.

This process adds one node per child, so this at most doubles the number of villages.

What happens if we put a sawmill at a fictitious village xi? We can argue that we can shift this sawmill upto v and not change the complexity.