Internet Problem Solving Contest

• Correct output – L1
• Correct output – L2
• C program to solve both data sets

Consider a generalized problem: What is the maximum average height of tower if the current tower top has radius r (and thus only blocks with base radius at most r can be played) and t minutes are remaining? Answer to this question will be refferred to as E(t,r). Solution to original problem is then value E(T,R)

Clearly E(0,r)=0 (there is no time to build anything). To find values of E(t,r) where t > 0 we analyze what happens in the first minute. First, Peter draws a building block from his bag. Let its base radius be a and ist height be b. Then he decides what to do with this block.

• Not use this block: For the rest of his tower all blocks with base radius at most r would be allowed and t-1 minutes would remain to finish the tower. So the average height of complete tower in this case would be E(t-1,r).
• Use this block: (this option is available only if a ≤ r) For the rest of his tower only blocks with base radius at most a would be allowed and t-1 minutes would remain to finish the tower. The average height of rest of tower would be E(t-1,a), so the average height of complete tower in this case would be b+E(t-1,a).

By the problem statment Peter chooses the better among this options. So the average height of the complete tower (if he draws block with dimensions a and b) is max(E(t-1,r),b+E(t-1,a)).

To find value of E(t,r) we simply take average over all possibilities for a and b. Or more formally:

E(t,r) = (1/RH)*∑_a=1..R∑_b=1..Hmax( E(t-1,r) , [a≤r](b+E(t-1,a)) ).

Direct implementation of this recursion using memoization or dynamic programmimg leads to a solution with time complexity O(T*R²*H) and was sufficient to solve the easy data set.

To be able to solve the hard data set we have to rewrite the right side of that recursion so that its computation is more efficient. One observation that might help is that for any r, t and a there is a height boundary such that we use a cylinder with radius a iff its height exceeds the boundary. A formal derivation of the optimized equation follows.

First we get rid of [a≤r] factor by splitting the outer sum into two sums, so we have E(t,r)=(A(t,r)+B(t,r))/RH where A(t,r) = ∑_a=r+1..R∑_b=1..HE(t-1,r) = (R-r)*H*E(t-1,r) and B(t,r) = ∑_a=1..r∑_b=1..Hmax( E(t-1,r) , b+E(t-1,a) ).

Next observe that E(t-1,r) < b+E(t-1,a) if and only if b > ⌊E(t-1,r) - E(t-1,a)⌋ because b is integer. So we can rewrite the inner sum of B(t,r) in the following way: ∑_b=1..Hmax( E(t-1,r) , b+E(t-1,a) ) = ∑_{b=1..d(t,r,a)}E(t-1,r) + ∑_{b=d(t,r,a)+1..H}(b+E(t-1,a)) = d(t,r,a)*E(t-1,r) + (d(t,r,a)+1+H)*(H-d(t,r,a))/2 + (H-d(t,r,a))*E(t-1,a) where d(t,r,a)=⌊E(t-1,r) - E(t-1,a)⌋.

The final result is thus: E(t,r) = (1/RH)*(R-r)*H*E(t-1,r) + (1/RH)*∑_a=1..r( d(t,r,a)*E(t-1,r) + (d(t,r,a)+1+H)*(H-d(t,r,a))/2 + (H-d(t,r,a))*E(t-1,a) ) where d(t,r,a)=⌊E(t-1,r) - E(t-1,a)⌋. We eliminated one level of summation.

Direct implementation of this recursion using memoization or dynamic programmimg leads to a solution with time complexity O(T*R²) and was sufficient to solve both data sets.