Official
B - 円形公園の街灯 / Street Lights in a Circular Park Editorial by admin
Claude 4.6 Opus (Thinking)Overview
Among \(N\) pillars arranged in a circle, \(M\) of them have benches. The problem is to optimally choose the facing direction of a streetlight installed at the center of the circle to minimize the maximum deviation angle across all benches. This reduces to a 1-center problem on a discrete circle.
Analysis
Rephrasing the Problem
The deviation angle is calculated as \(d(i, S_k) \times \frac{360}{N}\), and since \(\frac{360}{N}\) is a constant, we essentially need to minimize the following:
\[\min_{i} \max_{1 \leq k \leq M} d(i, S_k)\]
Here, \(d(i, j) = \min(|i-j|, N - |i-j|)\) is the circular distance.
Focusing on the Maximum Gap
When the bench positions are sorted on the circle, “gaps” (intervals without benches) appear between adjacent benches.
Key observation: For the arc on the opposite side of the maximum gap \(G_{\max}\) (the side where benches are densely packed), with length \(\text{span} = N - G_{\max}\), pointing the streetlight toward the center of this arc minimizes the distance to the farthest bench.
Concrete example: \(N=8\), benches at positions \(0, 1, 3\) (0-indexed). - Gaps: \(1, 2, 5\). Maximum gap \(G_{\max} = 5\). - \(\text{span} = 8 - 5 = 3\). Placing at the center gives \(D = \lceil 3/2 \rceil = 2\). - Setting to pillar 1: \(d(1,0)=1, d(1,1)=0, d(1,3)=2\). Maximum \(= 2\). ✓
Why Use the Maximum Gap
The bench farthest from the streetlight is the one on the “opposite side” of the streetlight. By making the maximum gap side the “back,” all benches fit within the shortest arc, minimizing the maximum distance.
Discrete Considerations
If \(\text{span}\) is even, we can place exactly at the center with \(D = \text{span}/2\). If odd, there is no pillar exactly at the center, so \(D = \lceil \text{span}/2 \rceil = (\text{span}+1)/2\).
Algorithm
- Convert bench positions to 0-indexed and sort
- Calculate gaps between adjacent benches (cyclically, including last → first)
- Find the maximum gap \(G_{\max}\)
- \(\text{span} = N - G_{\max}\), \(D = \lceil \text{span} / 2 \rceil\)
- Output the answer \(= D \times \frac{360}{N} = \frac{360D}{N}\) as an irreducible fraction
Complexity
- Time complexity: \(O(M \log M)\) (sorting is the bottleneck)
- Space complexity: \(O(M)\)
Implementation Notes
Don’t forget to calculate the cyclic gap (distance from the last bench to the first bench \(= N - p_{M-1} + p_0\))
To reduce \(\frac{360D}{N}\) to an irreducible fraction, divide by \(\gcd(360D, N)\)
When \(D = 0\) (the case where \(M=1\) and the streetlight faces the pillar with that bench), output
0/1Although \(N\) can be as large as \(10^9\), the computation itself completes in \(O(M)\), so there is no issue
Source Code
import sys
from math import gcd
def solve():
input_data = sys.stdin.buffer.read().split()
N = int(input_data[0])
M = int(input_data[1])
S = [int(input_data[i + 2]) for i in range(M)]
# Convert to 0-indexed positions on the circle
# Position of bench k is S_k - 1 (0-indexed), on a circle of size N
# d(i, j) = min(|i-j| mod N, N - |i-j| mod N) but with 0-indexed:
# d(i, j) = min((i-j) % N, (j-i) % N)
# We want to find i (0..N-1) that minimizes max over all benches of d(i, bench)
# where d(i, bench) = min((i - bench) % N, (bench - i) % N)
#
# The cost is d_max * 360 / N, so we need to minimize d_max.
# d_max = max_k min((i - s_k) % N, (s_k - i) % N) = max_k (N/2 - |((s_k - i) % N) - N/2|)
# Actually, d(i, s_k) = min((s_k - i) % N, N - (s_k - i) % N)
# which equals min(x, N-x) where x = (s_k - i) % N, and this is at most N//2.
# Sort bench positions (0-indexed)
positions = sorted([(s - 1) % N for s in S])
# For a given candidate direction i, d(i, s) = min((s-i)%N, (i-s)%N)
# We want to minimize over i: max over all s of d(i,s).
# Binary search on d_max. For a given threshold D, we need:
# For all benches s_k: d(i, s_k) <= D
# i.e., min((s_k - i) % N, (i - s_k) % N) <= D
# This means i is within distance D of s_k on the circle.
# Each bench covers an arc of positions [s_k - D, s_k + D] (mod N).
# We need the intersection of all M arcs to be non-empty.
# The intersection of arcs on a circle:
# Sort positions. Each arc is [s_k - D, s_k + D].
# The intersection is non-empty iff:
# For the sorted positions, the "spread" when looking at contiguous coverage:
# Actually, the intersection of all arcs [s_k - D, s_k + D] is non-empty iff
# there exists a point covered by all arcs.
# Equivalently, for sorted positions p_0 <= p_1 <= ... <= p_{M-1},
# we need: for some i, all positions are within distance D of i.
# This means max_k d(i, p_k) <= D.
# The optimal i minimizes max_k d(i, p_k).
# On a circle, the optimal i is the "midpoint" of the largest gap's complement.
#
# Think of it differently: sorted positions on circle.
# For each consecutive pair in sorted order (including wrap-around),
# consider the arc that does NOT contain the gap. The "radius" needed
# is ceil(arc_length / 2) where arc_length = N - gap.
#
# Actually: the minimum d_max = min over all "starting points" of
# the maximum distance. With sorted positions, consider the M arcs
# between consecutive benches. For each gap g between consecutive benches,
# the complementary arc has length N - g. The optimal point placed in
# the middle of that complementary arc needs radius ceil((N-g)/2) if integer,
# or (N-g)/2 exactly.
#
# Wait - we want the minimum of max d. The answer is:
# min over gaps of ceil_half(N - gap_size), but we can pick any i, not just integer.
# But i must be an integer (a pillar position).
#
# For sorted positions, gaps between consecutive (circular),
# the span = N - gap. The needed D = ceil((span - 1) / 2) if span > 0...
# Hmm let me think more carefully with the discrete circle.
# span of benches when gap g is the "back gap" = N - g
# We need D such that all benches fit within distance D of some integer point.
# Min D = ceil((span) / 2) where span = max circular distance among benches when optimally centered.
# Actually: for a set of points on circle, min max_d = min over all arcs containing all points of ceil(arc_length/2).
# Arc containing all points: N - max_gap. So min D_integer = ceil((N - max_gap) / 2) ... but with floor.
# The minimum of max d(i, s_k) over integer i = floor of (N - max_gap) / 2...
# Hmm, let me just think: if the max gap is G, the points span N-G around the circle.
# Place i at the midpoint: D = ceil((N-G-1)/2) if N-G >= 1...
# Actually it should be floor((N-G)/2).
# Let me reconsider. Positions sorted: p0 < p1 < ... < p_{M-1}.
# Gaps: p1-p0, p2-p1, ..., N - p_{M-1} + p_0.
# If we remove the largest gap G, the remaining arc has length N - G.
# Place i at midpoint. The farthest bench is at distance floor((N-G)/2) if we choose optimally.
# Answer D = floor((N-G)/2). But need to be careful.
# span = (last - first) on the arc = N - G - (M-1)... no.
# If gap G is between p_a and p_{a+1}, the benches on the other side span from p_{a+1} to p_a (going the other way).
# Arc length = N - G. Benches at relative positions 0, d1, d1+d2, ..., sum = N - G.
# Farthest from center of this arc: center is at relative position (N-G)/2.
# Actually no: farthest bench from any integer point i.
# The endpoints of the bench set are at relative positions 0 and N-G (on the arc).
# Wait the arc is from p_{a+1} to p_a going the short way (not through the gap).
# Leftmost bench: p_{a+1}, rightmost: p_a + N (or equivalently p_a on the other side).
# Distance from leftmost to rightmost along this arc: N - G.
# But N - G counts edges, not the benches. The "span" in terms of circle distance = N - G.
# Wait no. If gap from p_a to p_{a+1} (clockwise) is G, then going the other way from p_{a+1} to p_a is N - G.
# The first bench clockwise after the gap is p_{a+1}, the last bench before the gap is p_a.
# Clockwise distance from p_{a+1} to p_a (not through gap) = N - G.
#
# If we place i optimally, the max distance to these endpoints should be minimized.
# The two extreme benches are at clockwise distance 0 and N-G from p_{a+1}.
# Best i: at clockwise distance (N-G)/2 from p_{a+1}.
# If N-G is even, D = (N-G)/2 exactly (integer point exists).
# If N-G is odd, D = (N-G+1)/2 = ceil((N-G)/2) since we must pick integer.
# Wait: d(i, p_{a+1}) = (N-G)/2 and d(i, p_a) = (N-G)/2. But also other benches
# in between might be further? No, they're between the extremes so they're closer.
#
# But we also need i to be at distance <= D from ALL benches. The farthest ones
# from the midpoint are the two endpoints. Others are between. So D = ceil((N-G)/2)...
# Actually floor: if N-G even, D=(N-G)/2. If odd, we need (N-G+1)/2.
# Hmm: positions 0 and 5 on circle of N=10. Midpoint at 2 or 3. d(2,0)=2, d(2,5)=3. d(3,0)=3, d(3,5)=2. So D=3 = ceil(5/2).
# With (N-G)=5: ceil(5/2)=3. Yes.
# So D_min = ceil((N - G_max) / 2) where G_max is the largest gap.
# But wait, we want min over all gaps? No: we pick the largest gap to remove,
# because that minimizes N - G, hence minimizes D.
# D_min = ceil((N - G_max) / 2)
# But actually: what if there are multiple large gaps? We still remove only one (the largest).
# But couldn't we choose i to be in a position that's not the midpoint of the complement of the largest gap?
# No - the optimal is always to remove the largest gap and center.
# Hmm wait, that's actually not always true on discrete circles with M > 2. Let me reconsider...
# Actually it is: the set of benches lies in some arc. The smallest such arc is obtained
# by choosing the largest gap as the "outside". Then centering in that arc gives the minimum max distance.
# So: find the maximum gap G_max among consecutive bench pairs (circular).
# Answer D = ceil((N - G_max) / 2).
# But we could also have ties or the ceil might not give the best if there's a
# perfect centering with a smaller gap removed... Actually no, largest gap is always best.
# Wait, I realize there could be subtlety: ceil((N-G)/2) might equal the same
# for different gaps if they're close. But we want the minimum D, so we want G as large as possible.
# Let me verify with a simple example:
# N=8, M=2, benches at 1,5 (0-indexed: 0,4)
# Gaps: 4, 4. G_max = 4. N-G=4. ceil(4/2)=2. D=2.
# Cost = 2 * 360/8 = 90. That makes sense: place light at pillar 2 or 6, max dist = 2.
# N=6, M=3, benches at 1,2,4 (0-indexed: 0,1,3)
# Sorted: 0,1,3. Gaps: 1, 2, 3. G_max=3. N-G=3. ceil(3/2)=2. D=2.
# Cost = 2*360/6 = 120.
# Check: place at 1 (0-indexed). d(1,0)=1, d(1,1)=0, d(1,3)=2. Max=2. ✓
# Place at 2 (0-indexed). d(2,0)=2, d(2,1)=1, d(2,3)=1. Max=2. ✓
# So the answer cost = D_min * 360 / N where D_min = ceil((N - G_max) / 2).
#
# Let span = N - G_max.
# D_min = (span + 1) // 2 if span is odd, span // 2 if span is even.
# = (span + 1) // 2 ... wait no. ceil(span/2) = (span + 1) // 2.
#
# Hmm wait, for span=4: ceil(4/2)=2=(4+1)//2=2. For span=5: ceil(5/2)=3=(5+1)//2=3. OK.
# But actually I need to double-check: is it ceil(span/2) or floor(span/2)?
# span = N - G_max = distance from first to last bench going the short way.
# But it's the number of "edges" not "vertices" between the extreme benches.
#
# Example: benches at 0 and 4 on circle of 8. span = 8 - 4 = 4.
# Midpoint at 2. d(2, 0) = 2, d(2, 4) = 2. D = 2 = span/2. ✓
#
# Example: benches at 0 and 3 on circle of 8. Gaps: 3, 5. G_max=5. span=3.
# Midpoint: 0 + 1.5 → choose 1 or 2.
# d(1, 0)=1, d(1, 3)=2. D=2.
# d(2, 0)=2, d(2, 3)=1. D=2.
# ceil(3/2) = 2. ✓
# So answer = ceil((N - G_max) / 2) * 360 / N.
#
# But wait! I also need to consider that multiple gaps could yield the same or
# better result depending on parity. No, G_max is the unique best choice.
# Actually wait, I want to reconsider the problem more carefully.
#
# We have M bench positions. We want to choose integer i to minimize max_k d(i, S_k).
# This is equivalent to: find a point on the discrete circle that minimizes the
# maximum distance to any bench.
# This is the 1-center problem on a discrete circle.
#
# The answer is: find the largest "gap" (empty arc) between consecutive benches,
# remove it, and center in the remaining arc. The max distance is ceil(span/2)
# where span = N - gap.
# Actually, I realize I should also check: what if the optimal i coincides with one
# of the positions adjacent to the midpoint? There might be multiple gaps and
# the answer might be better with a different configuration. But no, for the
# 1-center problem on a circle, the answer is always determined by the largest gap.
# Let me also handle edge case M=1: only one bench. Then we can place i = S_1,
# and D = 0. G_max = N (the gap wrapping all the way around).
# span = N - N = 0. ceil(0/2) = 0. ✓
# And M=N: all pillars have benches. D = floor(N/2). G_max = 1 (each gap is 1).
# span = N - 1. ceil((N-1)/2). For N=4: ceil(3/2)=2. d max = 2.
# Check: N=4, benches at 0,1,2,3. Place at 0: d(0,2)=2. Yes. ✓
# OK so the algorithm is:
# 1. Sort bench positions (0-indexed).
# 2. Find the maximum gap between consecutive benches (including wrap-around).
# 3. span = N - max_gap.
# 4. D_min = ceil(span / 2) = (span + 1) // 2.
# Wait: when span is 0, D_min = 0. (span+1)//2 = 0 for span=0? No, (0+1)//2 = 0. ✓
# When span is 1 (two adjacent benches, largest gap = N-1), D_min should be...
# Wait M=2 benches adjacent: positions 0 and 1. Gaps: 1 and N-1. G_max = N-1. span = 1.
# D_min = ceil(1/2) = 1. Place at 0: d(0,0)=0, d(0,1)=1. Max=1.
# Place at 1: d(1,0)=1, d(1,1)=0. Max=1. So D=1 is correct. (1+1)//2 = 1. ✓
# Hmm wait, I realize there may be an issue. Let me reconsider.
#
# Actually, I think I might be wrong about ceil vs floor. Let me think again.
#
# benches at positions a and b on the circle (0-indexed), with a < b.
# gaps: b - a and N - (b - a). Suppose gap = N - (b - a) is larger, so G_max = N - (b-a).
# span = N - G_max = b - a.
# The benches span from a to b (clockwise).
# Optimal i: a + span/2 = a + (b-a)/2.
# If span even: i = a + span/2. d(i, a) = span/2, d(i, b) = span/2. D = span/2.
# If span odd: i = a + (span-1)/2 or a + (span+1)/2.
# For i = a + (span-1)/2: d(i,a) = (span-1)/2, d(i,b) = (span+1)/2. D = (span+1)/2.
# For i = a + (span+1)/2: d(i,a) = (span+1)/2, d(i,b) = (span-1)/2. D = (span+1)/2.
# So D = ceil(span/2). ✓
#
# But with more than 2 benches, intermediate benches are all within the span,
# so they're all within distance ceil(span/2) of the center. ✓
# Great. So answer = ceil(span / 2) * 360 / N.
# where span = N - G_max.
# Now I need to output as reduced fraction P/Q.
# answer = ceil(span/2) * 360 / N
# ceil(span/2) = (span + 1) // 2 when span is odd, span // 2 when span is even.
#
# Let D = ceil(span/2). Actually, D is an integer.
# answer = D * 360 / N = 360 * D / N.
# Reduce: g = gcd(360 * D, N). P = 360*D/g, Q = N/g.
# But simpler: g = gcd(360*D, N). Or just P = 360*D, Q = N, then reduce.
positions.sort()
# Compute gaps
max_gap = 0
for idx in range(M):
if idx + 1 < M:
gap = positions[idx + 1] - positions[idx]
else:
gap = N - positions[idx] + positions[0]
if gap > max_gap:
max_gap = gap
span = N - max_gap
D = (span + 1) // 2 # ceil(span / 2)
# Answer = 360 * D / N as a reduced fraction
P = 360 * D
Q = N
if P == 0:
print("0/1")
else:
g = gcd(P, Q)
print(f"{P // g}/{Q // g}")
solve()
This editorial was generated by claude4.6opus-thinking.
posted:
last update: