Overview

Given the arrival times of \(N\) buses in ascending order, the task is to compute all differences between consecutive arrival times (arrival intervals) and find the minimum and maximum among them.

Analysis

The key to solving this problem is to focus on “differences between adjacent elements”.

Let the bus arrival times be \(T_1, T_2, \ldots, T_N\). The arrival intervals between consecutive pairs of buses are the following \(N-1\) values: - Interval between the \(1\)st and \(2\)nd bus: \(T_2 - T_1\) - Interval between the \(2\)nd and \(3\)rd bus: \(T_3 - T_2\) - \(\vdots\) - Interval between the \((N-1)\)th and \(N\)th bus: \(T_N - T_{N-1}\)

Since the problem guarantees that the arrival times are strictly increasing (\(T_1 < T_2 < \cdots < T_N\)), all these intervals are guaranteed to be positive integers.

The maximum value of \(N\) is \(2 \times 10^5\). Computing all intervals requires \(N-1\) operations, so the computational complexity is proportional to \(N\). This is sufficiently small compared to the number of operations a typical programming language can process in \(1\) second (approximately \(10^8\) operations), so a straightforward approach of computing all intervals will yield a correct answer within the time limit.

Algorithm

1. Read the number of buses \(N\) and each arrival time \(T_1, \ldots, T_N\) as a list (array).
2. For \(i = 1\) to \(N-1\), compute the difference between adjacent times \(T_{i+1} - T_i\) and store the results in a new list.
3. Find the minimum and maximum values from the created list of intervals.
4. Output the minimum and maximum values separated by a space.

Complexity

• Time complexity: \(O(N)\)
  • Reading input, computing intervals (\(N-1\) times), and finding the minimum and maximum all complete in time proportional to \(N\).
• Space complexity: \(O(N)\)
  • The list storing arrival times and the list storing intervals each hold at most \(N\) elements.

Implementation Tips

• Fast input in Python: Since \(N\) can be as large as \(2 \times 10^5\), reading all input at once using sys.stdin.read().split() is faster than repeatedly calling input(), reducing execution time.

• List comprehension: In Python, using a list comprehension like [t[i+1] - t[i] for i in range(n - 1)] allows you to create the list of intervals concisely and efficiently.

• Using built-in functions: For obtaining the minimum and maximum values, it is efficient to use Python’s built-in functions min() and max(). These internally operate in \(O(N)\).

  Source Code

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白文字で分割してリストにする
    # Nが最大2*10^5程度であれば、この方法がPythonでは高速です
    data = sys.stdin.read().split()
    if not data:
        return
    
    # 1番目の要素がバスの本数 N
    n = int(data[0])
    
    # 2番目以降の要素が到着時刻 T_1, T_2, ..., T_N
    # これらを整数のリストに変換する
    t = list(map(int, data[1:]))
    
    # 連続する2つのバスの到着間隔をすべて計算し、リストに格納する
    # T_i は狭義単調増加なので、間隔は必ず正の整数になる
    gaps = [t[i+1] - t[i] for i in range(n - 1)]
    
    # 最小の間隔と最大の間隔を求め、スペース区切りで出力する
    # min() と max() は Python の組み込み関数で、リストを1巡して値を求めるため効率的
    print(min(gaps), max(gaps))

if __name__ == '__main__':
    main()

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