Overview

Sort the positions of the streetlights and consider only the differences between adjacent streetlights.
Create a function that determines “whether the maximum dark interval can be made \(D\) or less,” and find the answer using binary search.

Analysis

Let the streetlight positions sorted in ascending order be

\(A_0, A_1, \ldots, A_{M-1}\)

Define the differences between adjacent streetlights as

\(G_i = A_{i+1} - A_i\)

Then the current maximum dark interval is the maximum value of \(G_i\).

Why a naive approach is difficult

There are \(M\) choices for “which streetlight to move” and up to \(N\) choices for “where to move it.”
If we compute the maximum dark interval after each move, it takes at least \(O(MN)\) in the worst case, which is too slow for \(N,M \leq 3 \times 10^5\).

Determining whether we can achieve \(D\) or less

Instead of directly computing the answer, we determine:

Can we move exactly \(1\) streetlight so that all adjacent differences become \(D\) or less?

If we can achieve \(D\) or less, then we can certainly achieve \(D+1\) or more as well.
Therefore, this determination has monotonicity, so binary search can be used.

Bad gaps

For a fixed \(D\), we call a gap with \(G_i > D\) a “bad gap.”

When moving one streetlight, the operation can be thought of in two stages:

1. Remove a streetlight
2. Place that streetlight at a different unoccupied position

When a streetlight is removed, only the gaps to its left and right are affected.

For example, if we remove an interior streetlight \(A_i\):

• The two gaps \(A_i - A_{i-1}\) and \(A_{i+1} - A_i\) disappear
• Instead, a new gap \(A_{i+1} - A_{i-1}\) is created

On the other hand, the placement operation can fix at most \(1\) gap.
Therefore, if \(2\) or more bad gaps remain after removal, that \(D\) is impossible.

Also, if there are \(3\) or more bad gaps from the start, it is impossible.
This is because removing \(1\) streetlight cannot reduce the bad gaps sufficiently.

Condition for splitting a bad gap

Suppose a bad gap is \((u, v)\), meaning the left streetlight is at \(u\) and the right streetlight is at \(v\).

To split this gap with a new streetlight \(x\) so that both resulting differences are \(D\) or less:

\(u < x < v\)

and

\(x - u \leq D\)

\(v - x \leq D\)

must hold.

Therefore, the range where \(x\) can be placed is

\(L = \max(u+1, v-D)\)

\(R = \min(v-1, u+D)\)

If there exists an originally unoccupied position within the interval \([L, R]\), then that bad gap can be fixed.

Algorithm

First, perform preprocessing:

1. Sort the streetlight positions into array \(A\)
2. Compute adjacent differences \(G_i = A_{i+1} - A_i\)
3. Create an array indicating whether each position is occupied
4. Create a prefix sum pref so that we can determine in \(O(1)\) whether there is a free position in any interval \([l,r]\)

Whether there is a free position in interval \([l,r]\) can be determined by:

Whether the length of the interval \(r-l+1\) is greater than the number of streetlights in that interval.

That is,

\((r-l+1) > \text{occupied count in } [l,r]\)

means there is a free position.

Feasibility function feasible(D)

Fix \(D\) and check whether it is achievable.

1. Enumerate bad gaps

Collect gaps where \(G_i > D\).

If there are \(3\) or more bad gaps, it is impossible, so immediately return False.

2. Try each streetlight as the “removed streetlight”

Assume streetlight \(A_i\) is removed.

Count the number of bad gaps remaining after removal.

• The left gap \(G_{i-1}\) disappears
• The right gap \(G_i\) disappears
• If it is an interior streetlight, a new gap \(A_{i+1}-A_{i-1}\) is created

Let \(c\) be the number of bad gaps after removal.

3. If \(c > 1\)

Since placing a streetlight can fix at most \(1\) bad gap, it is impossible.

4. If \(c = 1\)

Check whether the single remaining bad gap can be split by the newly placed streetlight.

If the bad gap is \((u,v)\), the placeable range is

\([\max(u+1, v-D), \min(v-1, u+D)]\)

If there is an originally unoccupied position in this interval, it is possible.

5. If \(c = 0\)

At the point of removal, all gaps are \(D\) or less.

In this case, we just need a place to put the streetlight where no new gap exceeds \(D\).

The candidates are as follows:

• To the left of the leftmost remaining streetlight
• To the right of the rightmost remaining streetlight
• Inside an originally existing gap that contains a free position
• Inside the new gap formed by connecting the left and right neighbors of the removed streetlight

For each candidate, use the prefix sum to check whether there is an originally unoccupied position satisfying the conditions.

Binary Search

Since feasible(D) is monotone, we binary search on \(D\).

• If feasible(D) == True, try a smaller \(D\)
• If feasible(D) == False, try a larger \(D\)

Ultimately, the minimum possible \(D\) is the answer.

Complexity

• Time complexity: \(O(N + M \log M + M \log N)\)
  • Sorting takes \(O(M \log M)\)
  • Each feasibility check takes \(O(M)\)
  • Binary search performs \(O(\log N)\) checks
• Space complexity: \(O(N + M)\)

Implementation Notes

• The relocation destination must be an “originally unoccupied position.” Since the removed streetlight cannot be placed back at its original position, we use the prefix sum to accurately determine the presence of free positions.

• Whether there is a free position in interval \([l,r]\) can be determined by (r-l+1) > pref[r] - pref[l-1].

• The maximum dark interval only considers adjacent differences between streetlights, so distances to the road endpoints \(1,N\) are not considered. However, the relocation destination must be between \(1\) and \(N\) inclusive.

• If there are \(3\) or more bad gaps, we can immediately conclude it is impossible. This ensures that at most \(2\) bad gaps need to be handled within the feasibility check.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    A = sorted(data[2:])

    G = [A[i + 1] - A[i] for i in range(M - 1)]
    empty_gap_count = sum(1 for x in G if x >= 2)

    occ = bytearray(N + 1)
    for x in A:
        occ[x] = 1

    pref = [0] * (N + 1)
    s = 0
    for i in range(1, N + 1):
        s += occ[i]
        pref[i] = s

    def feasible(D):
        a = A
        g = G
        pref_local = pref
        m = M
        n = N
        m1 = m - 1
        egc = empty_gap_count

        bad_idxs = []
        for idx, val in enumerate(g):
            if val > D:
                if len(bad_idxs) == 2:
                    return False
                bad_idxs.append(idx)

        C = len(bad_idxs)

        bad_split = []
        for j in bad_idxs:
            u = a[j]
            v = a[j + 1]
            l = v - D
            t = u + 1
            if l < t:
                l = t
            r = u + D
            t = v - 1
            if r > t:
                r = t
            bad_split.append(l <= r and (r - l + 1) > (pref_local[r] - pref_local[l - 1]))

        for i in range(m):
            c = C

            if i > 0 and g[i - 1] > D:
                c -= 1
            if i < m1 and g[i] > D:
                c -= 1

            hbad = False
            if 0 < i < m1:
                if a[i + 1] - a[i - 1] > D:
                    c += 1
                    hbad = True

            if c > 1:
                continue

            if c == 0:
                if i == 0:
                    first = a[1]
                else:
                    first = a[0]

                l = first - D
                if l < 1:
                    l = 1
                r = first - 1
                if l <= r and (r - l + 1) > (pref_local[r] - pref_local[l - 1]):
                    return True

                if i == m1:
                    last = a[m - 2]
                else:
                    last = a[m1]

                l = last + 1
                r = last + D
                if r > n:
                    r = n
                if l <= r and (r - l + 1) > (pref_local[r] - pref_local[l - 1]):
                    return True

                cnt = egc
                if i > 0 and g[i - 1] >= 2:
                    cnt -= 1
                if i < m1 and g[i] >= 2:
                    cnt -= 1
                if cnt > 0:
                    return True

                if 0 < i < m1:
                    l = a[i - 1] + 1
                    r = a[i + 1] - 1
                    if l <= r and (r - l + 1) > (pref_local[r] - pref_local[l - 1]):
                        return True

            else:
                if hbad:
                    u = a[i - 1]
                    v = a[i + 1]
                    l = v - D
                    t = u + 1
                    if l < t:
                        l = t
                    r = u + D
                    t = v - 1
                    if r > t:
                        r = t
                    if l <= r and (r - l + 1) > (pref_local[r] - pref_local[l - 1]):
                        return True
                else:
                    left = i - 1
                    right = i
                    for k, j in enumerate(bad_idxs):
                        if j != left and j != right:
                            if bad_split[k]:
                                return True
                            break

        return False

    lo, hi = 0, N
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid

    print(hi)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.