Fill the segment with circles

Question

There is a line. On this line, we have $N \le 100$ points $(x_1, x_2, ..., x_n)$, $0 \le x_i \le 10^8$ which are centers of circles. We want to choose such radii for those circles, but in such way that they can't intersect (but they can be tangent). There is one more condition. We want those circles to have the highest possible sum of circumferences. We can write this sum as $2\pi r_1 + 2\pi r_2 + \cdots + 2\pi r_n$, where $r_i$ is radius of circle with center $x_i$. Taking $2\pi$, the task boils down to maximize $r_1 + r_2 + \cdots + r_n$, but with condition that those circles can't intersect. Also, any circle can't be inside any other. You can assume that centers are integers, but radii don't have to be integers. Also, every radius has to be positive (can't be equal to 0).

What is the fastest way to solve this? I would like to design an algorithm which could solve this.

Answer 1

Hint. Assume without loss of generality that $x_1<x_2<\cdots<x_n$, and define the functions $f_i$ as $$ f_i(d) = \text{the largest value of }\sum_{j\le i}r_j\text{ under the additional restriction that }r_i\le d $$ Then each $f_i$ will be a piecewise linear function of a particularly simple shape, and it is easy enough to derive $f_{i+1}$ given $f_{i}$ and the distance $x_{i+1}-x_j$.

Compute them all in sequence, and your answer will be the maximum of $f_n$.

---

(Actually, a bit of additional thought about the shape of the $f_i$s will reveal that the straightforward greedy algorithm is in fact optimal).

Answer 2

Here is a clever way to do the problem: First suppose there are only two circles. It is not hard to show the sum of the circumferences is independent of how we choose the radii, provided they are tangent.

Thus $C_1+C_2$ is independent of the arrangement. Likewise for $C_2 + C_3$ and $C_3 + C_4$ and so on. We conclude that $C_1 + 2C_2 + +2C_3 + \ldots + 2C_{98} + 2C_{99} + C_{100}$ is independent.

Now maximizing $C_1 + C_2 + \ldots + C_{99} + C_{100}$ is the same as maximizing $2C_1 + 2C_2 + \ldots + 2C_{99} + 2C_{100}$. By the above logic this is equivalent to maximising $C_1 + C_{100}$.

Edit: This only works if the maximum can be achieved by all circles being tangent. It may not help when there are an even number of points. In that case maximizing the first and last radius will prevent some circle in the middle having nonzero radius.