Insolvable Disks

Let disk $i$ project onto the $x$-axis as

$$[x_i-r_i,\ x_i+r_i].$$

Because all centers are on one line, two disks overlap exactly when these intervals overlap with positive length. Tangency between $i<j$ means

$$x_i+r_i=x_j-r_j.$$

Only Adjacent Pairs Matter

Here is the first trap: you might think far-apart disks can also be tangent. Nope.

Let $L_i=x_i-r_i$ and $R_i=x_i+r_i$. Since the centers are sorted and disks do not overlap, adjacent intervals satisfy

$$R_i\le L_{i+1}.$$

Also every radius is positive, so

$$L_{i+1}<R_{i+1}.$$

For $j\ge i+2$, we get a chain like

$$R_i\le L_{i+1}<R_{i+1}\le \cdots \le L_j,$$

so actually $R_i<L_j$. Therefore disk $i$ and disk $j$ cannot be tangent. The middle positive-radius disk blocks exact contact. Geometry did not come here to negotiate.

So we only care about adjacent pairs. Define

$$d_i=x_{i+1}-x_i.$$

The constraints become

$$r_i+r_{i+1}\le d_i,$$

and pair $i,i+1$ is tangent iff

$$r_i+r_{i+1}=d_i.$$

So the problem is now purely one-dimensional: maximize the number of tight adjacent inequalities.

Possible Radii After A Prefix

After processing gaps $1..i$, we are standing at disk $i+1$. For each $k$, define $S_k$ as the set of possible values of $r_{i+1}$ if we can already achieve at least $k$ tangencies in the processed prefix.

These sets are open intervals. Suppose one such interval is

$$(A,B).$$

Now process the next gap $d$.

If we make the next edge tangent, then

$$y=d-r,$$

where $r$ is the old radius and $y$ is the next radius. We need $r<d$, so the image interval is

$$(\max(0,d-B),\ d-A).$$

If we do not force this edge to be tangent, we only need

$$r+y<d.$$

Since $r$ can approach $A$, the possible next radii are

$$(0,\ d-A).$$

The open endpoints matter. If $A=d$, then no positive next radius fits. This is why the code uses strict $L<d$, not $L\le d$.

The Greedy Invariant

The huge simplification is this invariant:

After each processed gap, let $K$ be the maximum achievable number of tangencies. Then:

• for every $k<K$, $S_k=(0,p)$, where $p$ is the previous gap;
• for $k=K$, $S_K=(L,U)$ for some interval we store.

In plain English: every non-best count is fully flexible. Only the current best count has a weird restricted interval.

Why is that true? If you are not chasing the absolute best count, you have at least one missed tangency available somewhere, and that missed edge lets you reset the next radius to basically anything positive below the current gap. The interval transition above makes this formal.

Now process a new gap $d$.

Case 1: $L<d$

Some best-count configuration has current radius small enough to fit through this gap. So we make this edge tangent and increase the answer:

$$K\leftarrow K+1.$$

The new best interval is the tangent image of $(L,U)$:

$$L'=\max(0,d-U), \qquad U'=d-L.$$

Case 2: $L\ge d$

Every best-count configuration has current radius too large. It cannot even satisfy

$$r_i+r_{i+1}\le d$$

with $r_{i+1}>0$. So the best state dies here. Brutal, but useful.

We fall back to the second-best state. By the invariant, its possible current radii are exactly

$$(0,p),$$

where $p$ is the previous gap. We make the new edge tangent, so the answer stays $K$, and the new best interval is

$$L'=\max(0,d-p), \qquad U'=d.$$

That is the whole algorithm.

Why This Is Correct

The geometry lemma proves that every tangent pair must be adjacent, so maximizing tangent disk pairs is exactly maximizing tight constraints $r_i+r_{i+1}=d_i$.

The interval transition is exact: from an old radius interval, either we make the next edge tight and reflect the interval through $d$, or we leave slack and can choose any smaller positive next radius.

The invariant says we never need to store all $S_k$. All counts below the best remain completely flexible over the latest gap, while the best count is summarized by one interval $(L,U)$. The two update cases cover everything:

• if $L<d$, a best configuration can take the next tangency, so no solution can beat $K+1$ and we achieve it;
• if $L\ge d$, no best configuration can even pass the next constraint, so $K+1$ is impossible, and rebuilding $K$ from the second-best flexible interval is optimal.

Thus the greedy update always preserves the true maximum after each prefix.

Complexity

Each gap is processed once. Total complexity is

$$O(n)$$

per test case, with $O(1)$ extra memory besides the input. Across all tests, this is $O(\sum n)$, which is exactly what we need for $2\cdot 10^6$ points.