Overview

This problem involves \(N\) points arranged from east to west, with streetlights installed at \(M\) of them. You must choose exactly one streetlight and move it to a different vacant point, minimizing the maximum distance between adjacent streetlights (the maximum dark interval).

By solving the decision problem “Can we make the maximum dark interval at most \(X\)?”, we can use binary search on the answer to find the optimal minimum value.

---

Analysis

1. Binary Search on the Answer

The condition “Can we make the maximum dark interval at most \(X\)?” has monotonicity. If we can make the maximum dark interval at most \(X\), then for any \(Y > X\), we can obviously also make it at most \(Y\). Therefore, we can find the desired minimum value using Binary Search. The search range is from a minimum of \(1\) to a maximum of \(N\).

2. Decision Problem: Can we make the maximum dark interval at most \(X\)?

Sort the streetlight coordinates in ascending order as \(A_1 < A_2 < \dots < A_M\), and define the gaps between adjacent streetlights as \(D_i = A_{i+1} - A_i\) (\(1 \le i \le M-1\)).

We enumerate which streetlight to move. Fix the streetlight to move as \(A_k\) (\(1 \le k \le M\)). When streetlight \(A_k\) is removed, let \(G\) be the number of gaps exceeding \(X\) among the remaining \(M-1\) streetlights’ gaps.

After removing streetlight \(A_k\), the gaps change from the original gaps \(D\) as follows: - When \(k=1\): \(D_1\) disappears. - When \(k=M\): \(D_{M-1}\) disappears. - When \(1 < k < M\): \(D_{k-1}\) and \(D_k\) disappear, and a new gap \(D_{k-1} + D_k\) is created instead.

All other gaps remain unchanged. If we pre-list the set of indices where \(D_i > X\), we can compute the value of \(G\) for each \(k\) in \(O(1)\). (Note: If there are 4 or more positions where \(D_i > X\), then \(G \ge 2\) regardless of which streetlight is moved, so we can immediately determine “impossible” and prune.)

Based on the value of \(G\), we determine whether a vacant point exists where streetlight \(A_k\) can be placed.

Case 1: \(G \ge 2\)

Since 2 or more intervals exceeding \(X\) remain, no matter where we place the single streetlight \(A_k\), we cannot make all intervals at most \(X\). Therefore, this \(k\) is impossible.

Case 2: \(G = 1\)

Exactly one interval exceeding \(X\) exists. Let \(L_{val}\) be the left endpoint and \(R_{val}\) be the right endpoint of this interval. We must place \(A_k\) within this interval to split it into two parts, both of length at most \(X\). That is, the placement coordinate \(P\) must satisfy the following conditions: - \(L_{val} < P < R_{val}\) (inside the interval) - \(P - L_{val} \le X \iff P \le L_{val} + X\) - \(R_{val} - P \le X \iff P \ge R_{val} - X\)

Combining these: $\(\max(L_{val} + 1, R_{val} - X) \le P \le \min(R_{val} - 1, L_{val} + X)\)\( If a vacant point \)P\( satisfying this exists, then this \)k$ is feasible.

Case 3: \(G = 0\)

All gaps between the remaining streetlights are already at most \(X\). In this case, we just need to place streetlight \(A_k\) somewhere such that no new gap exceeds \(X\). Let \(B_1\) be the minimum and \(B_{M-1}\) be the maximum of the remaining streetlights. The possible placement locations \(P\) are:

1. Outside the left end: To the left of \(B_1\). For the gap to be at most \(X\): \(B_1 - X \le P \le B_1 - 1\).
2. Outside the right end: To the right of \(B_{M-1}\). For the gap to be at most \(X\): \(B_{M-1} + 1 \le P \le B_{M-1} + X\).
3. Inside: Between \(B_1\) and \(B_{M-1}\). Since all gaps between streetlights in this range are already at most \(X\), placing it anywhere in between only further subdivides the gaps, so they always remain at most \(X\). That is, \(B_1 + 1 \le P \le B_{M-1} - 1\).

If a vacant point \(P\) exists in any of these ranges, then this \(k\) is feasible.

3. Checking Existence of Vacant Points

Whether a vacant point (a point without a streetlight) exists in a range \([L, R]\) can be determined in \(O(1)\) using prefix sums. Create an array IsU where each point \(i\) has value \(1\) if it’s vacant and \(0\) if it has a streetlight, then compute its prefix sum SumU. A vacant point existing in the interval \([L, R]\) is equivalent to SumU[R] - SumU[L-1] > 0.

---

Algorithm

1. Input and Preprocessing:
   • Sort the streetlight coordinates \(S\) to form array \(A\).
   • Create array IsU indicating whether each point is vacant, and compute its prefix sum SumU.
   • Compute the array \(D\) of distances between adjacent streetlights.
2. Binary Search:
   • Set the search range as \(low = 1, high = N\), and call the decision function check(mid) for the midpoint \(mid\).
3. Decision Function check(X):
   • Collect indices where \(D_i > X\). If there are 4 or more, return false.
   • For each streetlight \(k = 1 \dots M\), do the following:
     • Compute \(G\), the “number of gaps exceeding \(X\)” when \(A_k\) is removed.
     • If \(G = 1\), use prefix sums to check whether a vacant point exists that fits within the exceeding interval.
     • If \(G = 0\), use prefix sums to check whether a vacant point exists outside the ends or inside.
     • If a vacant point satisfying the conditions is found, return true.
   • If impossible for all \(k\), return false.

---

Complexity

• Time Complexity: \(O(M \log M + N + M \log N)\)

  • Sorting streetlights takes \(O(M \log M)\).
  • Building prefix sums takes \(O(N)\).
  • The number of binary search steps is \(O(\log N)\).
  • The decision function check(X) scans \(M\) streetlights per step, with each check in \(O(1)\), so \(O(M)\) overall per step.
  • Therefore, the total time complexity comfortably fits within the time limit.

• Space Complexity: \(O(N + M)\)

  • \(O(N)\) memory is used to store the coordinate array and prefix sum array.

---

Implementation Notes

• Excluding placement at the original position:

  • According to the problem statement, “exactly one streetlight must be relocated to a different vacant point.”
  • The original position of the moved streetlight \(A_k\) has IsU[A[k]] = 0 (not vacant) in the prefix sum SumU, so it is naturally excluded from the choices. This cleanly prevents the invalid transition of “not relocating.”

• Index boundaries:

  • The range \([L, R]\) for searching vacant points must be properly clipped with max(1, L) and min(N, R) to ensure it does not exceed the road range \([1, N]\).

    Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
vector<int> A;
vector<int> D;
vector<int> SumU;

bool has_U(int L, int R) {
    if (L > R) return false;
    L = max(1, L);
    R = min(N, R);
    if (L > R) return false;
    return (SumU[R] - SumU[L-1]) > 0;
}

bool check(int X) {
    vector<int> bad_indices;
    for (int i = 1; i <= M - 1; ++i) {
        if (D[i] > X) {
            bad_indices.push_back(i);
            if (bad_indices.size() > 3) return false;
        }
    }
    int cnt = bad_indices.size();

    for (int k = 1; k <= M; ++k) {
        int G = cnt;
        if (k == 1) {
            if (D[1] > X) G--;
        } else if (k == M) {
            if (D[M-1] > X) G--;
        } else {
            if (D[k-1] > X) G--;
            if (D[k] > X) G--;
            if (D[k-1] + D[k] > X) G++;
        }

        if (G >= 2) continue;

        if (G == 1) {
            int L_val = -1, R_val = -1;
            if (1 < k && k < M && D[k-1] + D[k] > X) {
                L_val = A[k-1];
                R_val = A[k+1];
            } else {
                int idx = -1;
                for (int i : bad_indices) {
                    if (k == 1 && i == 1) continue;
                    if (k == M && i == M - 1) continue;
                    if (1 < k && k < M && (i == k - 1 || i == k)) continue;
                    idx = i;
                    break;
                }
                if (idx != -1) {
                    L_val = A[idx];
                    R_val = A[idx+1];
                }
            }
            if (L_val != -1 && R_val != -1) {
                int L_range = max(L_val + 1, R_val - X);
                int R_range = min(R_val - 1, L_val + X);
                if (has_U(L_range, R_range)) return true;
            }
        } else { // G == 0
            int B1, BM_minus_1;
            if (k == 1) {
                B1 = A[2];
                BM_minus_1 = A[M];
            } else if (k == M) {
                B1 = A[1];
                BM_minus_1 = A[M-1];
            } else {
                B1 = A[1];
                BM_minus_1 = A[M];
            }

            if (has_U(B1 - X, B1 - 1)) return true;
            if (has_U(BM_minus_1 + 1, BM_minus_1 + X)) return true;
            if (has_U(B1 + 1, BM_minus_1 - 1)) return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> N >> M)) return 0;

    A.resize(M + 1);
    for (int i = 1; i <= M; ++i) {
        cin >> A[i];
    }
    sort(A.begin() + 1, A.end());

    D.resize(M);
    for (int i = 1; i <= M - 1; ++i) {
        D[i] = A[i+1] - A[i];
    }

    vector<int> IsU(N + 1, 1);
    IsU[0] = 0;
    for (int i = 1; i <= M; ++i) {
        IsU[A[i]] = 0;
    }
    SumU.resize(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        SumU[i] = SumU[i-1] + IsU[i];
    }

    int low = 1, high = N, ans = N;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (check(mid)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.