Jellyfish and Miku
Contest: Codeforces Round 901 (Div. 1)
Difficulty rating: 2800
Tags: divide and conquer, dp, math, probabilities

There are $$$n + 1$$$ cities with numbers from $$$0$$$ to $$$n$$$, connected by $$$n$$$ roads. The $$$i$$$-th $$$(1 \leq i \leq n)$$$ road connects city $$$i-1$$$ and city $$$i$$$ bi-directionally. After Jellyfish flew back to city $$$0$$$, she found out that she had left her Miku fufu in city $$$n$$$.

Each road has a positive integer level of beauty. Denote the beauty of the $$$i$$$-th road as $$$a_i$$$.

Jellyfish is trying to find her fufu. Because of her poor sense of direction, she doesn't know which way to go. Every day, she randomly chooses a road connected to the city she currently is in and traverses it. Let $$$s$$$ be the sum of the beauty of the roads connected to the current city. For each road connected to the current city, Jellyfish will traverse the road with a probability of $$$\frac x s$$$, where $$$x$$$ is the beauty of the road, reaching the city on the other side of the road.

Jellyfish will start at city $$$0$$$, and she will get only her fufu back when she reaches city $$$n$$$.

You want to choose the beauty of the roads such that the expected number of days Jellyfish takes to find her fufu will be the minimum possible. However, due to limited funding, the sum of beauties of all roads must be less than or equal to $$$m$$$.

Find the minimum expected number of days Jellyfish needs to get her fufu back if the beauty of the roads is chosen optimally.

Input format:
The first and only line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq m \leq 3000$$$) — the number of the roads and the maximum sum of beauty of the roads.

Output format:
Output the minimum expected number of days Jellyfish needs to get her fufu back if the beauty of the roads is chosen optimally.

Your answer will be accepted if the absolute or relative error does not exceed $$$10^{-9}$$$. Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is considered correct if $$$\frac{|a-b|}{\max(1,|b|)} \leq 10^{-9}$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first example, the optimal assignment of beauty is $$$a=[1, 2, 5]$$$. The expected number of days Jellyfish needs to get her fufu back is $$$5.2$$$.

Example input:
3 8

Example output:
5.200000000000

Example input:
10 98

Example output:
37.721155173329

Editorial:
Let's assume that $$$a$$$ is given. We can use dynamic programming to solve the problem.
Let's define $$$f_i$$$ means the expected number of days Jellyfish needs to reach city $$$i$$$ from city $$$0$$$.
We will have:
$$$f_0=0, f_1=1$$$
$$$\forall i > 1, f_i=f_{i-1}+1+\frac {a_{i-1}} {a_{i-1}+a_i} \times (f_i - f_{i-2})$$$
Let's make it better:
$$$f_i = f_{i-1} + 1 + \frac {a_{i-1}} {a_i} \times (f_{i-1}-f_{i-2}+1)$$$
What does this inspire us to do? Let's define $$$g_i=f_i-f_{i-1}$$$, then we will get:
$$$g_1=1$$$
$$$\forall i > 1, g_i = 1 + \frac {a_{i-1}} {a_i} \times (g_{i-1}+1)$$$
By induction, we will find $$$g_i = 1 + 2 \times \sum_{j=1}^{i-1} \frac {a_j} {a_i}$$$. According to the definition, $$$f_n = \sum_{i=1}^n g_n = n + 2 \times \sum_{i=1}^n\sum_{j=1}^{i-1} \frac{a_j}{a_i}$$$.
Then we can use dynamic programming to solve the problem itself.
Let's define $$$s_i = \sum_{j=1}^i a_j$$$, then $$$f_n = n + 2 \times \sum_{i=1}^n \frac{s_{i-1}}{a_i}$$$
Let's define $$$dp_{i, x}$$$ means when $$$s_i = x$$$, the minimum value of $$$\sum_{i=1}^n \frac{s_{j-1}}{a_i}$$$.
We transfer by enumerating the values of $$$a_{i+1}$$$, The transition is: $$$dp_{i+1, x+y} \leftarrow dp_{i, x} + \frac x y$$$.
But the time complexity is $$$O(n m^2)$$$, how can it becomes faster?
Let's take a closer look at $$$\sum_{i=1}^n\sum_{j=1}^{i-1} \frac{a_j}{a_i}$$$. If there exists $$$i < n$$$ satisfying $$$a_i > a_{i+1}$$$. We can swap $$$a_i$$$ and $$$a_{i+1}$$$, the answer will be better! so $$$a$$$ is a non-decreasing array, which means $$$a_i \leq \frac m {n - i + 1}$$$.
Because $$$\sum_{i=1}^n \frac n i$$$ is $$$O(n \log n)$$$, so if we only enumerate the possible values of $$$a_i$$$ the time complexity will be $$$O(m^2 \log m)$$$.