Overview

A problem to find the minimum communication range \(K\) required so that all base stations arranged on a straight line can communicate with each other.

Analysis

In this problem, we need to build a network where all base stations can communicate “directly or via relay.” In other words, the goal is to create what is known in graph theory as a “connected graph.”

A straightforward approach would be a binary search method: assume some \(K\), then determine whether all base stations are connected with that \(K\). However, there is a more efficient way to solve this.

The key observation is that “the base stations are arranged on a straight line” and “whether communication is possible depends on whether the distance is within \(K\).” In other words, if adjacent base stations can communicate with each other, the entire network is likely to be connected.

In fact, after sorting the base stations by coordinate, the maximum distance between consecutive base stations is the minimum \(K\). This is because if we can cover that maximum distance, all shorter distances are automatically covered, and thus all base stations become connected.

For example, if the coordinates are [1, 4, 7], the adjacent distances are \(3\) each, so the minimum \(K\) is \(3\). If \(K\) were smaller, say \(K=2\), station 1 and station 2 could communicate, and station 2 and station 3 could also communicate, but station 1 and station 3 could neither communicate directly nor via relay, so the network would be disconnected.

Conversely, if we set \(K\) to the maximum distance between adjacent base stations, every base station can “communicate with the stations before and after it,” so it is guaranteed that all base stations will ultimately be connected.

Algorithm

1. Sort the coordinate list \(X\) of the base stations.
2. In the sorted list, compute the differences between adjacent elements \(|X[i] - X[i-1]|\) and find the maximum value.
3. That maximum value is the desired minimum communication range \(K\).

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(1)\) (constant memory excluding input)

Implementation Notes

• Don’t forget to read the input and sort the coordinates.
• Be careful with indices when computing differences (the first element has no predecessor to compare with).
• Integer arithmetic provides sufficient precision, so floating-point numbers are not needed.

## Source Code

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    X = list(map(int, data[1:]))
    
    # 座標をソート
    X.sort()
    
    # 隣接する基地局間の距離の最大値が求める最小のK
    max_diff = 0
    for i in range(1, N):
        diff = X[i] - X[i-1]
        if diff > max_diff:
            max_diff = diff
    
    print(max_diff)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.