Overview

Given base stations on a straight line where stations can directly communicate if their distance is at most \(K\), find the minimum \(K\) such that the entire network is connected. The answer is the maximum distance between adjacent base stations when the coordinates are sorted in ascending order.

Analysis

Consider a graph where base stations are vertices and edges connect pairs with distance at most \(K\). The condition “any two stations can communicate via relays” is equivalent to the graph being connected.

The key observation here is that the base stations lie on a straight line. Sort the coordinates in ascending order: \(X_{(1)} < X_{(2)} < \dots < X_{(N)}\).

• If there exists some adjacent difference \(X_{(i+1)} - X_{(i)} > K\), that “gap” cannot be directly crossed.
  Furthermore, since the stations are on a straight line, going from a point on the left side to a point on the right side necessarily requires crossing this interval, so the graph is inevitably disconnected (it cannot be connected).
• Conversely, if all adjacent differences satisfy \(X_{(i+1)} - X_{(i)} \le K\), then all neighboring base stations can directly communicate.
  This forms a chain (path) \(X_{(1)} \leftrightarrow X_{(2)} \leftrightarrow \dots \leftrightarrow X_{(N)}\), making the entire network connected.

Therefore, the condition for connectivity is
$\(\max_{i}(X_{(i+1)} - X_{(i)}) \le K\)\( and the minimum \)K\( is \)\(K_{\min} = \max_{i}(X_{(i+1)} - X_{(i)})\)$

Why a naive approach is disadvantageous

One might consider an approach such as “binary search on \(K\), and for each value build the graph and check connectivity via BFS/DFS.” However, the number of edges can be up to \(O(N^2)\), which is heavy. In this problem, the one-dimensional property means the answer is determined solely by the maximum adjacent difference, making such approaches excessive.

Concrete example

For coordinates \([1, 3, 8, 10]\), the adjacent differences are \(2, 5, 2\), so the maximum is \(5\).
With \(K=4\), stations \(3\) and \(8\) cannot connect, causing a disconnection. With \(K=5\), all stations connect in a chain and the network becomes connected.

Algorithm

1. If \(N \le 1\), there is at most one base station, so no communication range is needed — output \(0\).
2. Sort the coordinate array \(X\) in ascending order.
3. Examine all adjacent differences \(X[i+1]-X[i]\) and output their maximum value as the answer.

Complexity

• Time complexity: Dominated by sorting, \(O(N \log N)\)
• Space complexity: \(O(N)\) for the input array, etc.

Implementation Notes

• Since coordinates are given in arbitrary order, you must sort them before computing adjacent differences.

• When \(N=1\), no differences are defined, so output \(0\) as a special case.

• Differences can be up to around \(10^9\), which can be safely handled by Python’s int.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    X = list(map(int, input().split()))
    if N <= 1:
        print(0)
        return
    X.sort()
    ans = 0
    for i in range(N - 1):
        d = X[i + 1] - X[i]
        if d > ans:
            ans = d
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.