Teleporters
Contest: Educational Codeforces Round 126 (Rated for Div. 2)
Difficulty rating: 2600
Tags: binary search, greedy

There are $$$n+1$$$ teleporters on a straight line, located in points $$$0$$$, $$$a_1$$$, $$$a_2$$$, $$$a_3$$$, ..., $$$a_n$$$. It's possible to teleport from point $$$x$$$ to point $$$y$$$ if there are teleporters in both of those points, and it costs $$$(x-y)^2$$$ energy.

You want to install some additional teleporters so that it is possible to get from the point $$$0$$$ to the point $$$a_n$$$ (possibly through some other teleporters) spending no more than $$$m$$$ energy in total. Each teleporter you install must be located in an integer point.

What is the minimum number of teleporters you have to install?

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 < a_2 < a_3 < \dots < a_n \le 10^9$$$).

The third line contains one integer $$$m$$$ ($$$a_n \le m \le 10^{18}$$$).

Output format:
Print one integer — the minimum number of teleporters you have to install so that it is possible to get from $$$0$$$ to $$$a_n$$$ spending at most $$$m$$$ energy. It can be shown that it's always possible under the constraints from the input format.

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

Example input:
2
1 5
7

Example output:
2

Example input:
2
1 5
6

Example output:
3

Editorial:
Initial $$$n+1$$$ portals divide the path from $$$0$$$ to $$$a_n$$$ into $$$n$$$ separate sections. If we place a new portal between two given ones, it only affects the section between these two portals.
Let's suppose we want to place $$$k$$$ new portals into a section of length $$$x$$$. This will divide it into $$$(k+1)$$$ sections, and it's quite easy to prove that these sections should be roughly equal in size (to prove it, we can show that if the sizes of two sections differ by more than $$$1$$$, the longer one can be shortened and the shorter one can be elongated so the sum of squares of their lengths decreases). So, a section of length $$$x$$$ should be divided into $$$x \bmod (k+1)$$$ sections of length $$$\lceil \frac{x}{k+1} \rceil$$$ and $$$(k+1) - x \bmod (k+1)$$$ sections of length $$$\lfloor \frac{x}{k+1} \rfloor$$$. Let's denote the total energy cost of a section of length $$$x$$$ divided by $$$k$$$ new portals as $$$f(x, k)$$$; since we divide it in roughly equal parts, it's easy to see that
$$$$$$f(x, k) = (x \bmod (k+1)) \cdot (\lceil \frac{x}{k+1} \rceil)^2 + ((k+1) - x \bmod (k+1)) \cdot (\lfloor \frac{x}{k+1} \rfloor)^2$$$$$$
The key observation that we need to make now is that $$$f(x, k) - f(x, k+1) \ge f(x, k+1) - f(x, k+2)$$$; i. e. if we add more portals to the same section, the energy cost change from adding a new portal doesn't go up. Unfortunately, we can't give a simple, strict proof of this fact, but we have faith and stress (this would be easy to prove if it was possible to place portals in non-integer points, we could just analyze the derivative, but in integer case, it's way more difficult).
Okay, what should we do with the fact that $$$f(x, k) - f(x, k+1) \ge f(x, k+1) - f(x, k+2)$$$ for a section of length $$$x$$$? The main idea of the solution is binary search over the value of $$$f(x, k) - f(x, k+1)$$$; i. e., we use binary search to find the minimum possible change that a new portal would give us. Let's say that we want to check that using the portals that give the cost change $$$\ge c$$$ is enough; then, for each section, we want to find the number of new portals $$$k$$$ such that $$$f(x, k-1) - f(x, k) \ge c$$$, but $$$f(x, k) - f(x, k+1) < c$$$; we can use another binary search to do that. For a fixed integer $$$c$$$, we can calculate not only the number of new portals that we can add if the cost change for each portal should be at least $$$c$$$, but also the total cost of the path after these changes; let's denote $$$g(c)$$$ as the total cost of the path if we place new portals until the cost change is less than $$$c$$$, and $$$h(c)$$$ is the number of portals we will place in that case.
We have to find the minimum value of $$$c$$$ such that $$$g(c) \le m$$$. Now, it looks like $$$h(c)$$$ is the answer, but this solution gives WA on one of the sample tests. The key observation we are missing is that, for the value $$$c$$$, we don't have to add all of the portals that change the answer by $$$c$$$; we might need only some of them. To calculate the answer, let's compute four values:
• $$$g(c+1)$$$;
• $$$h(c+1)$$$;
• $$$g(c)$$$;
• $$$h(c)$$$.
If we place $$$h(c+1)$$$ portals and add new portals one by one, until the total cost becomes not greater than $$$m$$$, the cost change from each new portal will be equal to $$$\frac{g(c+1) - g(c)}{h(c) - h(c+1)}$$$ (or just $$$c$$$ if we consider the fact that we start using the portals which change the cost by $$$c$$$). So, we can easily calculate how many more additional portals we need to add if we start from $$$h(c+1)$$$ portals and cost $$$g(c+1)$$$.
The total complexity of our solution is $$$O(n \log^2 A)$$$: we have a binary search over the cost change for each new portal; and for a fixed cost change, to determine the number of portals we place in each section, we run another binary search in every section separately.