Problem Link
Difficulty
Easy
Pre-requisites
Dynamic programming
Problem
Count the number of ways to construct a sequence of nested spheres
How to get 40 points
First of all, let’s note that the number of ways construct a sphere of the radii of R is equal to the product of the number of lower hemispheres of the radii of R multiplied by the number of upper hemispheres of the radii of R. Let’s call this number S[R].
Now, let’s denote the number of ways to construct a sequence of K nested spheres with the largest sphere having the radii of R by F[K][R]. Let’s take F[0][0] equal to one.
The rules for the recalculation of f[K][R] are straightfowrward: we need to pick a sequence of (K-1) spheres, where the largest sphere has the radii less than R. The number of such sequences (let’s denote it by W[K][R]) is equal to the sum of F[K-1][J] for all J < R. Now we need to add a sphere of the radii R to the end of each of these sequences. Considering that there are S[R] ways to create a sphere of the radii of R, we obtain that F[K][R] = W[K][R]*S[R].
The number of sequences of K nested spheres will clearly be equal to the sum of F[K][J] for all J between 1 and C.
In total, we need to calculate O(C2) states of F[][], and it takes O(C) to calculate each of them. So, the total complexity will be O(C3).
This solution is capable of solving the first two subtasks, but is too slow to solve the last one.
How to get 100 points
The solution’s idea remains the same.
Let’s find a way to calculate the values of F[][] in O(1) time. For achieving this, let’s note that the value of W[K][R] equals to the W[K][R-1] + F[K-1][R-1]. So now, using the old values of W[][], we can calculate the new one in O(1).
Now, since the calculation of every state runs in O(1), we get the total complexity of O(C2), which fits for our problem.
Setter’s Solution
Can be found here
Tester’s Solution
Can be found here