Indian Computing Olympiad

Dynamic Programming→Yertle the Turtle

Yertle, the turtle king, has 5607 turtles. He wants to stack up these turtles to form a throne. Each turtle i has weight W[i] and capacity C[i]. A turtle can carry on its back a stack of turtles whose total weight is within C[i]. This should include W[i], the weight of the current turtle, so assume that C[i]≥W[i] always.

Find the height of the tallest turtle throne that Yertle can build.

Define the residual capacity of turtle i as C[i] - W[i].

It not enough to look at heuristics such as "place minimum weight turtle on top" or "put maximum residual capacity turtle on bottom".

For instance, if we have two turtles with (W,C) = (100,100) and (3,103), respectively, we have to stack the heavier turtle on top because the lighter turtle has a higher carrying capacity.

On the other hand, if (W,C) = (1000000,1001000) and (1,10000), we would put the turtle with maximum residual capacity on top.

The problem numbers suggest that we can at most use N² time.

Claim: If there is a stack of height k, there is a stack of height k in which carrying capacities are sorted in descending order from bottom to top.

Proof: Suppose, t1 is below t2 and t1 has smaller carrying capacity than t2. Then, we can swap t1 and t2 and the stack will still be stable.

Define RC(i,k) to be the maximum of the following:

• Calculate each arrangement of height k using turtles 1..i
• Calculate the minimum residual capacity in this arrangement

Now

• RC(i+1,k) =
               max {
                   RC(i,k),
                   min{ (C[i+1]-W[i+1], (RC(i,k-1) - wt(i+1)) }
               }

The answer we want is the largest k for which RC[5607,k] is positive. This can be done in time N², which is feasible for N = 5607.

How much memory do we need? Naively, we need an 5607×5607 array. This is too large. However, row RC[i+1,...] depends only on RC[i,...] so we need to maintain only two rows of the matrix at a time.