# 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(C ^{2})** states of

**F[][]**, and it takes

**O©**to calculate each of them. So, the total complexity will be

**O(C**.

^{3})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(C ^{2})**, which fits for our problem.

# Setter’s Solution

Can be found here

# Tester’s Solution

Can be found here