Overview

Given \(N\) pillars arranged on a circular ring, the problem asks to choose one pillar to install a streetlight such that the maximum distance (angular deviation) to \(M\) pillars that have benches is minimized. The minimum cost should be output as a reduced fraction.

---

Analysis

1. Naive Approach and Its Limitations

If we naively compute the maximum distance to all benches \(S_k\) for every pillar \(i\) (\(1 \leq i \le N\)), the time complexity becomes \(O(N \times M)\). Given the constraints \(N \le 10^9\) and \(M \le 2 \times 10^5\), this approach will not meet the time limit (TLE). Since \(N\) is very large, we need to narrow down the candidate positions for the streetlight and compute the minimum cost efficiently.

2. Key Observation: Focus on the “Largest Gap Without Benches”

On the circular ring, we call the distance (difference in pillar indices) between adjacent benches a gap. When the pillars with benches are listed in clockwise order, let the intervals between adjacent benches be \(L_1, L_2, \ldots, L_M\). Their total sum equals the circumference \(N\).

Here, we focus on the “largest gap without benches”. Let the length of the largest gap be \(L_{\max}\).

We choose the streetlight position at the center of the side directly opposite to this largest gap \(L_{\max}\). Why is this optimal?

As a concrete example, consider \(N = 10\) with benches at \([2, 5, 9]\). * The gaps between benches are: * Between \(2\) and \(5\): length \(3\) * Between \(5\) and \(9\): length \(4\) (this is the largest gap \(L_{\max} = 4\)) * Between \(9\) and \(2\): length \(3\) * The benches at both ends of the largest gap (length \(4\)) are \(5\) and \(9\). We place the streetlight at pillar \(2\), which is near the center on the opposite side of this gap. * In this case, the distance from the streetlight to bench \(5\) is \(3\), and to bench \(9\) is \(3\), while the distance to the other bench (\(2\) itself) is \(0\). Therefore, the maximum distance is kept at \(3\).

In general, when the streetlight is placed at the center opposite the largest gap \(L_{\max}\), the benches at both ends of that gap become the “farthest benches.” All other benches are concentrated in the semicircle on the streetlight’s side, so they are closer to the streetlight. Therefore, the maximum distance \(D\) to all benches coincides with the distance to the endpoints of the largest gap, and can be formulated as follows.

3. Formulation of Maximum Distance \(D\)

The distance calculation differs slightly depending on whether the circumference \(N\) is even or odd (due to integer division truncation).

• When \(N\) is even For each gap \(L\), let max_val be the maximum of the half-lengths (rounded down). $\(\text{max\_val} = \max \left( \lfloor L / 2 \rfloor \right)\)\( The minimum possible maximum distance \)D\( from the streetlight to the farthest bench is: \)\(D = \frac{N}{2} - \text{max\_val}\)$

• When \(N\) is odd Similarly, for each gap \(L\), define max_val as follows: $\(\text{max\_val} = \max \left( \lfloor (L - 1) / 2 \rfloor \right)\)\( The minimum distance \)D\( is: \)\(D = \frac{N - 1}{2} - \text{max\_val}\)$

4. Conversion to Angle and Reduction to Irreducible Fraction

For the computed minimum distance \(D\), the actual cost (angle) is \(D \times \frac{360}{N}\) degrees. To output this as a reduced fraction \(\frac{P}{Q}\): * Numerator \(P = D \times 360\) * Denominator \(Q = N\)

Then divide both by the greatest common divisor \(\gcd(P, Q)\) to obtain the irreducible fraction.

---

Algorithm

1. Sort the array \(S\) representing bench positions in ascending order.
2. Compute all intervals between adjacent benches (including the one that wraps around the circular boundary) and store them in array \(L\).
   • \(L_i = S_{i+1} - S_i\) (\(0 \le i < M-1\))
   • \(L_{M-1} = N + S_0 - S_{M-1}\)
3. Compute max_val from each \(L_i\) depending on the parity of \(N\).
4. Using max_val, compute the minimum distance \(D\).
5. Set \(P = D \times 360\), \(Q = N\), divide by \(\gcd(P, Q)\), and output the reduced fraction P/Q.

---

Complexity

• Time Complexity: \(O(M \log M)\) Sorting the bench positions \(S\) takes \(O(M \log M)\). The subsequent interval computation and maximum value search can be done in \(O(M)\), so the overall time complexity is dominated by sorting at \(O(M \log M)\). Since \(M \le 2 \times 10^5\), this comfortably fits within the time limit.
• Space Complexity: \(O(M)\) Dynamic arrays (std::vector) storing bench positions and intervals use \(O(M)\) memory.

---

Implementation Notes

• Handling the circular boundary: The distance between the last bench \(S_{M-1}\) and the first bench \(S_0\) must be computed as \(N + S_0 - S_{M-1}\), taking into account the wraparound of the circular ring.

• Preventing overflow: Since \(N\) can be up to \(10^9\), computing the numerator \(P = D \times 360\) may overflow a standard 32-bit integer type (int). In C++, use the long long type for calculations.

• Reducing to irreducible fraction: Using std::gcd, available since C++17, allows computing the greatest common divisor concisely and efficiently.

  Source Code

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

using namespace std;

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

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

    vector<long long> S(M);
    for (int i = 0; i < M; ++i) {
        cin >> S[i];
    }

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

    vector<long long> L(M);
    for (int i = 0; i < M - 1; ++i) {
        L[i] = S[i+1] - S[i];
    }
    L[M-1] = N + S[0] - S[M-1];

    long long max_val = 0;
    if (N % 2 == 0) {
        for (long long len : L) {
            max_val = max(max_val, len / 2);
        }
    } else {
        for (long long len : L) {
            max_val = max(max_val, (len - 1) / 2);
        }
    }

    long long D;
    if (N % 2 == 0) {
        D = N / 2 - max_val;
    } else {
        D = (N - 1) / 2 - max_val;
    }

    long long P = D * 360;
    long long Q = N;
    long long g = std::gcd(P, Q);
    P /= g;
    Q /= g;

    cout << P << "/" << Q << "\n";

    return 0;
}

---

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