Overview

Sort the positions of street lights and minimize the maximum distance between adjacent street lights.
Binary search on the answer, checking “Can we make the maximum dark interval at most \(D\)?”

Analysis

Let the street light positions sorted in ascending order be \(A_0, A_1, \ldots, A_{M-1}\).
What matters here is only the difference between adjacent street lights:

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

If we naively enumerate “which street light to move” and “where to move it,” there are up to \(O(MN)\) candidates, and computing the maximum each time would be too slow.

Therefore, we binary search on the answer.

We consider “Can we make the maximum dark interval at most \(D\)?”

When removing one street light

When we consider moving street light \(A_k\), we first remove \(A_k\).

The original gaps affected are at most two:

• The gap between \(A_{k-1}\) and \(A_k\)
• The gap between \(A_k\) and \(A_{k+1}\)

Also, if \(A_k\) is not at an endpoint, a new gap

\(A_{k+1} - A_{k-1}\)

is created.

All other gaps remain unchanged.

When placing a street light at the destination

Adding one street light can only split at most one gap.

In other words, if after removing a street light there are 2 or more gaps exceeding \(D\), we cannot fix all of them with a single addition.

Therefore, for each \(k\), we can determine as follows:

• If there are 2 or more gaps exceeding \(D\) after removal
  → Impossible
• If there is exactly 1 gap exceeding \(D\) after removal
  → Check whether we can place a street light in that gap such that both left and right distances are at most \(D\)
• If there are 0 gaps exceeding \(D\) after removal
  → We just need to place it somewhere without creating a new gap exceeding \(D\)

The destination must be an originally empty position

We cannot place the street light back at its original position.
Therefore, the only available destinations are positions that were originally empty.

To quickly check whether there is an empty position within an interval, we prepare a prefix sum of empty position counts.

Algorithm

First, sort the street light positions and store adjacent differences as gap.

Also, manage whether each position is empty, and create a prefix sum prefEmpty of empty position counts.
This allows us to determine in \(O(1)\) whether there is an empty position in an interval \([l, r]\).

Decision function feasible(D)

Determines “Can we make the maximum dark interval at most \(D\)?”

First, count the gaps that exceed \(D\) among the current gaps.
Call this totalBad.

Next, enumerate all street lights \(A_k\) to move.

1. Compute the number of bad gaps after removing \(A_k\)

When \(A_k\) is removed, the original gaps that disappear are:

• gap[k-1]
• gap[k]

Also, if \(A_k\) is not at an endpoint, a new gap

\(A_{k+1} - A_{k-1}\)

is created.

Using this, compute the number of gaps exceeding \(D\) after removal.

2. If there are 2 or more bad gaps, it’s impossible

Since adding one street light can fix at most 1 gap, this \(k\) is impossible.

3. If there is exactly 1 bad gap

Let this gap be \([l, r]\).

We need to place a street light inside this gap.
If we place it at position \(x\), the necessary conditions are:

\( x - l \leq D \)

and

\( r - x \leq D \)

That is,

\( r - D \leq x \leq l + D \)

Furthermore, \(x\) must be inside the gap, so:

\( l + 1 \leq x \leq r - 1 \)

Therefore, the valid range for placement is:

\( \max(l+1, r-D) \leq x \leq \min(r-1, l+D) \)

If there is an empty position in this range, we can make the maximum dark interval at most \(D\).

4. If there are 0 bad gaps

Let mn be the minimum position and mx be the maximum position of the remaining street lights after removal.

At this point, all gaps are at most \(D\).

Safe destinations are any of the following:

• Place to the left of mn
  
  • The new gap created is mn - x
  • So \(x \in [mn-D, mn-1]\)
• Place between mn and mx
  
  • This only splits an existing gap, so it necessarily remains at most \(D\)
  • So \(x \in [mn+1, mx-1]\)
• Place to the right of mx
  
  • The new gap created is x - mx
  • So \(x \in [mx+1, mx+D]\)

If there is an empty position in any of these intervals, it is possible.

Binary Search

feasible(D) has monotonicity.

That is, if it is possible for some \(D\), it is always possible for any larger \(D\).

Therefore, we can binary search on the answer.

Complexity

• Time complexity: \(O(M \log M + M \log N)\)
  • \(O(M \log M)\) for sorting
  • \(O(\log N)\) iterations of binary search
  • \(O(M)\) for each decision
• Space complexity: \(O(N + M)\)

Implementation Notes

• By managing the count of empty positions with a prefix sum, we can determine in \(O(1)\) whether there is an empty position within an interval.

• Only originally empty positions count as valid destinations. The original position of the moved street light cannot be used as a destination.

• When removing an endpoint street light, note that no new merged gap is created.

• When \(M=2\), removing one street light leaves only one, but the same logic handles this case.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<int> A(M);
    vector<int> occ(N + 1, 0);
    for (int i = 0; i < M; i++) {
        cin >> A[i];
        occ[A[i]] = 1;
    }

    sort(A.begin(), A.end());

    vector<int> gap(M - 1);
    for (int i = 0; i < M - 1; i++) {
        gap[i] = A[i + 1] - A[i];
    }

    vector<int> prefEmpty(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        prefEmpty[i] = prefEmpty[i - 1] + (occ[i] == 0);
    }

    auto countEmpty = [&](int l, int r) -> int {
        l = max(l, 1);
        r = min(r, N);
        if (l > r) return 0;
        return prefEmpty[r] - prefEmpty[l - 1];
    };

    auto feasible = [&](int D) -> bool {
        int totalBad = 0;
        vector<int> badIdx;
        badIdx.reserve(4);

        for (int i = 0; i < M - 1; i++) {
            if (gap[i] > D) {
                totalBad++;
                if ((int)badIdx.size() < 4) badIdx.push_back(i);
            }
        }

        for (int k = 0; k < M; k++) {
            int badUnaffected = totalBad;

            if (k > 0 && gap[k - 1] > D) badUnaffected--;
            if (k + 1 < M && gap[k] > D) badUnaffected--;

            bool mergedBad = false;
            if (k > 0 && k + 1 < M) {
                mergedBad = (A[k + 1] - A[k - 1] > D);
            }

            int badCount = badUnaffected + (mergedBad ? 1 : 0);
            if (badCount > 1) continue;

            if (badCount == 1) {
                int l, r;

                if (mergedBad) {
                    l = A[k - 1];
                    r = A[k + 1];
                } else {
                    if (totalBad > 3) continue;

                    int idx = -1;
                    for (int id : badIdx) {
                        if (id != k - 1 && id != k) {
                            idx = id;
                            break;
                        }
                    }
                    if (idx == -1) continue;

                    l = A[idx];
                    r = A[idx + 1];
                }

                int L = max(l + 1, r - D);
                int R = min(r - 1, l + D);

                if (countEmpty(L, R) > 0) return true;
            } else {
                int mn = (k == 0 ? A[1] : A[0]);
                int mx = (k == M - 1 ? A[M - 2] : A[M - 1]);

                if (countEmpty(mn - D, mn - 1) > 0) return true;
                if (countEmpty(mn + 1, mx - 1) > 0) return true;
                if (countEmpty(mx + 1, mx + D) > 0) return true;
            }
        }

        return false;
    };

    int ok = N, ng = 0;
    while (ok - ng > 1) {
        int mid = (ok + ng) / 2;
        if (feasible(mid)) ok = mid;
        else ng = mid;
    }

    cout << ok << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.