Problems (May 29, 2008)

The order given is not necessarily the best order to solve the problems. Most of the problems can be solved using some graph theory and/or dynamic programming.
A)

Bachet's Game
Hint: Dynamic programming. Compute for each number of stones which player wins (the one who takes the first move or the other).

B)

Stacking Boxes
Hint: This can be modelled as finding a longest path in a DAG. To determine whether a box nests in another one can use sorting.

C)

Mailbox Manufacturers Problem
Hint: Dynamic programming, but quite tricky. Try a 3D state space as follows. What is the minimum number of crackers needed to determine how many crackers i boxes can withstand given we know that it can withstand between j..k crackers?.

D)

Periodic Strings
Hint: You don't anything fancy like a border array. Just implement the naive O(n^2) algorithm.

E)
Internet Bandwidth
Hint: Max-flow, if you have a working implementation this should be very easy.

F)

Crimewave
Hint: Max-flow (see CLRS Problem 26.1). You need to figure out how to represent vertex capacities.

G)

Nested Dolls
Hint: Greedy (or using Dilworth's theorem you could solve it using longest increasing subsequence). Try to build the set of boxes. By going through the boxes in sorted order on one of the dimensions, there is always an optimal place to put the next box.