Section 5: Advanced Dynamic Programming Solutions
CS 124 Spring 2021
1 Problem 1: Optimal Taxation
You are the king of a kingdom that’s set up like a tree, and you want to collect some taxes. You know that each city has a “tax potential” ti that you can collect. However, you don’t want to tax adjacent cities, because they might talk to each other and begin a revolt. Find the maximum tax you can collect in linear time.
Solution: Let dp[i][0] be the most revenue we can collect from the subtree at i when i is not used and let dp[i][1] be the most revenue we can collect from the subtree at i when i is used.
Then, note that we have
dp[i][0] = ∑ max (dp[j][0], dp[j][1]) j∈N(i),j̸=p
dp[i][1] = ti + ∑ dp[j][0] j∈N(i),j̸=p
and now we simply use the DFS algorithm as mentioned before.
2 Problem 2: Stack the Blocks
We have n blocks, each with weight wi and strength bi. We stack the blocks on top of each other in some order.
The power of a block is its strength minus the sum of the weights which lie on it.
The strength factor of a stack is the minimum power of any particular block.
Give a O(n · 2n) algorithm to find the maximum possible strength factor across all permuta-
tions containing all of the blocks (note: answer might be negative).
Solution: First, we write the dynamic programming solution in the language of sets. Note that
dp[S] = maxmin dp[S\{i}],bi − ∑ wk = maxmin dp[S\{i}],bi +wi − ∑wk i∈S k∈S\{i} i∈S k∈S
and dp[] = 0
which we can see by noticing that the strength factor of S \ {i} stacked on top of i is given by the
minimum of the strength factor of S \ {i} and the power of the bottom block. Implementing this in bitsets is not much more complicated, as one can simply iterate through each i ∈ [0, 1, . . . n − 1] to see if its in S, and then perform the calculation.
Note: A variant of this problem appeared as USACO 2014 December Gold Contest Problem 1. 1
3 Problem 3: Longest Paths in a Tree
Find the length of the longest path in a tree, where the edges are weighted (and possibly negative).
Solution: Each path on a tree has a unique “highest” point v. We will essentially calculate the longest path whose highest point is given by v. First, however, since paths whose highest points are at v consist of two disjoint “vertical paths”, we first compute the longest vertical paths that end at each vertex. dp[i] is the length of the longest “vertical path” whose highest point is i.
Then, note that we have
dp[i] = max 0, max (dp[j] + wij) j∈N(i),j̸=p
Now, for each vertex v, to find the longest path whose highest point is v, we simply compute
l[i] = max dp[i], max ((dp[j] + wij) + (dp[k] + wik)) . j,k∈N(i),j,k̸=p,j̸=k
which we can find by simply finding the two largest values of dp[j] + wij across all j. Both of these problems fit nicely into our framework, and we may conclude.
2