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.
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..H}max( 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^{2}*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..H}E(t-1,r) = (R-r)*H*E(t-1,r) and B(t,r) = ∑_{a=1..r}∑_{b=1..H}max( 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..H}max( 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^{2}) and was sufficient to solve both data sets.