Hint for Problem 8 on the final exam.

Pick a large number N.  (Say, N = 1000.)

Draw the opt-graph.  (It will have 2N+1 nodes, one for each reachable
offset function.)

Draw the red-black graph.  (It will have 4n+2 nodes, one for each pair
(omega,s) where omega is a reachable offset function and s is either A or B.)
There will be no red arrows, but each arrow will have a black cost and 
a red cost.

From each node, there draw the arrow showing what happens if A is requested
and what happens if B is requested.  In some cases, where WFA allows two
choices, there will be an extra arrow.

For each node in the red-black graph, define the "lazy potential" of
that node to be the maximum red cost of any path whose black cost is zero
and which starts from that node.

For each arrow where the black cost is positive, prove that the inequality
holds, where C = 2.

Make sure your logic works regardless of the value of N.

Then, you're done.

As N gets larger, the formulas look more complicated.  But as N goes to
infinity, the formulas converge to simple formulas.

Write it down.
