Overview

This problem asks us to find the minimum communication range \(K\) required to connect all base stations arranged in a straight line. This reduces to finding the maximum distance between adjacent base stations.

Analysis

Key Insight

The key point is that the base stations are arranged in a straight line. To connect all base stations, it is sufficient for “adjacent base stations” (when sorted by coordinate) to be able to communicate with each other.

For example, suppose there are 3 base stations at coordinates \(1, 5, 8\). - Distance between base station 1 (coordinate 1) and base station 2 (coordinate 5): \(4\) - Distance between base station 2 (coordinate 5) and base station 3 (coordinate 8): \(3\)

In this case, if \(K = 4\), everyone can communicate by relaying through 1→2→3.

Why We Only Need to Look at Adjacent Pairs

After sorting the coordinates, if all adjacent base stations are connected, the entire network is connected like a chain. Conversely, if even one pair of adjacent stations is not connected, the network becomes disconnected.

Specifically, since there are no base stations between coordinates \(X_i\) and \(X_{i+1}\), there is no other way than to directly connect these two.

Problems with the Naive Approach

The method of calculating distances for all pairs \((i, j)\) and determining connectivity as a graph requires \(O(N^2)\) time complexity, which is too slow for \(N = 2 \times 10^5\).

Solution

Sort the coordinates and find the maximum distance (gap) between adjacent base stations — this will be the answer.

Algorithm

1. If there is only one base station, communication range \(0\) is sufficient (output and exit)
2. Sort the coordinates
3. Calculate the distances between all adjacent base stations and find the maximum
4. Output the maximum

Example: X = [8, 1, 5]
After sorting: X = [1, 5, 8]
Gaps: 5-1=4, 8-5=3
Maximum gap: 4
Answer: K = 4

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (array to store coordinates)

Implementation Notes

• Special case \(N = 1\): If there is only one base station, there is no need to communicate with others, so output \(K = 0\)

• Don’t forget to sort: The input is not necessarily given in coordinate order, so always sort

• Integer arithmetic is sufficient: Coordinates are given as integers and distances are also integers, so there is no need to use floating-point numbers

  Source Code

def solve():
    N = int(input())
    X = list(map(int, input().split()))
    
    if N == 1:
        print(0)
        return
    
    # Sort the coordinates
    X.sort()
    
    # Find the maximum gap between consecutive stations
    max_gap = 0
    for i in range(1, N):
        gap = X[i] - X[i-1]
        max_gap = max(max_gap, gap)
    
    print(max_gap)

solve()

---

This editorial was generated by claude4.5opus.