Hello everyone!

After one year, I am back to translating Looking for a Challenge 2. At this rate, I will finish in 2060 :)

Today, I am looking at "The Motorway" from 2013 (see page 79 for English task statement).

Abridged problem statement

There are $$$n$$$ entry points along a motorway. The $$$i$$$th entry point is located $$$a_i$$$ metres from the start of the motorway.

Byteasar would like to build $$$n+1$$$ tollbooths on the motorways so that:

• The tollbooths are evenly spread out so that the distance between consecutive tollbooths is the same
• Between every two consecutive entry points, there is a tollbooth (it is acceptable for a tollbooth to be positioned exactly at one of the entry points).
• There is a tollbooth before the first, and after the last entry point (or exactly at).

Formally, an arrangement of tollbooths can be described by the position of the leftmost booth $$$b_0$$$ and a distance $$$l$$$ between consecutive tollbooths. The tollbooths would be positioned at $$$b_0, b_0 + l, b_0 + 2l, \ldots, b_0 + nl$$$. The $$$j$$$th entry point must be positioned in the interval $$$[b_0 + (j-1)l, b_0 + jl]$$$.

Your job is to find the minimum and maximum possible $$$l$$$ where an arrangement exists. Give your answer within an epsilon of $$$10^{-8}$$$.

Bounds: $$$3 \leq n \leq 10^6$$$, $$$0 \leq a_i \leq 10^9$$$

Solution

Translation note: Initially, I was planning to faithfully translate the (very thorough and detailed!) solutions from Polish, but that turned out to be a lot of effort... so instead, I have decided to use the original solutions as more of a reference.

For conciseness, we will use $$$s$$$ instead of $$$b_0$$$. We will also focus on finding the minimum $$$l$$$ (maximum $$$l$$$ will be similar). Let's rewrite the condition. For $$$0 < i < n$$$, we need the $$$i$$$th tollbooth to lie between entry point $$$i-1$$$ and $$$i$$$. So,

Note that $$$\frac{a_{i-1}}{i}$$$ and $$$\frac{a_{i}}{i}$$$ are constants, so we'll denote them $$$L_i$$$ and $$$R_i$$$ respectively:

(This doesn't take into account the requirement that there should be a tollbooth before the first and after the last entry point, but one can introduce virtual entrypoints at -infinity and infinity to accommodate for this. Perhaps there is a more elegant way.)

Thus, we can interpret the condition on the $$$i$$$th tollbooth as constraining $$$l$$$ to an interval $$$[L_i, R_i]$$$. What about the $$$-\frac{s}{i}$$$? This represents a shift of the interval by $$$s$$$, scaled by $$$\frac{1}{i}$$$.

For a fixed choice of $$$s$$$, we can easily determine the intersection of all intervals in linear time, thus we can determine the range of possible $$$l$$$ in linear time. That's great, but there are too many possible choices of $$$s$$$.

To save us, we need to observe that we can binary search on $$$s$$$. One can imagine that as $$$s$$$ increases, the interval $$$[L_i, R_i]$$$ sliding to the left. Intervals with larger $$$i$$$ slide more slowly (as it is scaled by $$$\frac{1}{s}$$$).

Claim: The values of $$$s$$$ that admit a valid solution form an interval. Informal proof: If two intervals are "moving" in the same direction, then the interval that represents their overlap is also "moving" in that direction. Furthermore, the "time" that they overlap is contiguous. This extends to the intersection of multiple moving intervals by induction.

Claim: Maximising $$$s$$$ also minimises $$$l$$$. Informal proof: If two intervals are "moving" in the same direction, the endpoints of their overlap are also moving in the same direction. Thus, the largest value of $$$s$$$ will give the smallest left endpoint (remember that the shift is by $$$-\frac{s}{i}$$$).

These two facts allow us to binary search on $$$s$$$. If we calculate that the intervals do not overlap, we can pick any two non-overlapping intervals and check whether $$$s$$$ needs to be increased or decreased.

This gives a solution that runs in $$$O(n \log M)$$$, where $$$M$$$ is the required precision, which suffices to solve the problem.

Translation note: The polish solution described a few solutions, of which the one I provide above is one of them (I think). It also presents a linear time solution, but note that it is very difficult to implement.