Show description

5) . In order to compute all values of Av,t,l (respectively Av,t ), for some i,s l ∈ {0, . . , depth(v)}, we compute Bi,s v,l (respectively Cv ) for each i = 0, . . , deg(v) and s = 0, . . , k. e. n − 1. After computing all values of Av,t,l the program returns A (r, k, 0) as the final answer. Rivers Too Much Dynamic Programming Using dynamic programming twice would not be required if all the vertices in the tree had small number of children. Fortunately, we can easily construct a binary tree of villages that has the same minimal cost of transportation as the original one.

1 6 . . . . . . . . * . . 1 7 . . . . * . . . . * . . 1 8 . . . . . . . . . * . 1 9 . . * . . * . . . . . * . 2 0 . . . . . . . . . . * Fig. 1: A chart depicting winning and losing situations. The latter ones are marked with stars. (a) Let us assume, that after the first cut we have a l × m rectangle, where 2n l < n. Since n = 2k (m + 1) − 1, we have 2k−1 (m + 1) − 1 < l < 2k (m + 1) − 1. Hence, the second player can reduce the rectangle to 2k−1 (m + 1) − 1 × m, which is a losing position for the first player.

From the above we obtain that n × m is a losing position. n+1 3. Let us assume that n and m do not fulfill the above condition. Then, log2 ( m+1 ) is not an integer. Without the loss of generality, we can assume that n m. Let us denote by l the following value: l=2 n+1 ) log2 ( m+1 (m + 1) − 1 n We have n+1 l < n. So, the first player can cut a rectangle reducing it 2 < l + 1 < n + 1, and from this we obtain 2 to l × m, which is a losing position for the second player. The model solution follows the proof of the lemma and for every winning position it finds the appropriate move in logarithmic time.