Overview

This problem involves dividing \(N\) settlements on a number line into at most \(K\) groups, and minimizing the half-difference between the maximum and minimum coordinates within each group. Since this has the classic structure of “minimizing the maximum,” it can be efficiently solved using the binary search on the answer technique (also known as “fix-and-check binary search”).

Analysis

1. Rephrasing the Problem

We call the set of settlements covered by each shelter a “group.” Let \(X_L\) be the minimum coordinate and \(X_R\) be the maximum coordinate of settlements covered by a shelter. To minimize the maximum distance from any settlement in this group to the shelter, it is optimal to place the shelter at the midpoint \(P = \frac{X_L + X_R}{2}\) between \(X_L\) and \(X_R\).

In this case, the distance from any settlement in the group to the shelter is at most \(\frac{X_R - X_L}{2}\). Therefore, the condition “the maximum distance from each settlement to its shelter is at most \(d\)” can be rephrased as “the difference (maximum coordinate \(-\) minimum coordinate) of each group is at most \(2d\).”

2. Regarding the “Capacity at Least 1” and “Exactly \(K\) Shelters” Conditions

The problem states that “exactly \(K\) shelters must be placed, and every shelter must have a capacity of at least 1.” While this may seem complex at first glance, it can be simplified as follows.

Suppose that after grouping the settlements to satisfy the maximum distance constraint, the number of groups is less than \(K\) (say \(M\) groups, where \(M < K\)). In this case, the remaining \(K - M\) shelters can be placed “immediately next to” (since we use real coordinates, at an extremely close position to) settlements already assigned to a group. This allows us to increase the number of shelters to \(K\) and ensure all capacities are at least 1, without affecting the existing assignments or the maximum distance.

Therefore, this condition is effectively simplified to “can the settlements be divided into at most \(K\) groups?”

3. Why Binary Search?

Let \(W\) denote the value of \(2d\) we want to find. * If \(W\) is too small (e.g., \(W = 0\)), each group can contain only one settlement, requiring \(N\) shelters, which exceeds \(K\). * If \(W\) is sufficiently large (e.g., \(W = X_N - X_1\)), all settlements can be combined into a single group, so only 1 shelter is needed.

Thus, there is monotonicity in the feasibility check “a valid grouping is possible if the value is at least \(W\)” (there exists a threshold value such that it is always possible for larger values and always impossible for smaller values). Therefore, we can use binary search to find the optimal \(W\) (i.e., the minimum value of \(2d\)).

Algorithm

At each step of the binary search, we solve the decision problem “can the settlements be divided into at most \(K\) groups such that twice the maximum distance is at most \(W\)?” using a greedy approach.

Decision Algorithm (Greedy)

We determine groups sequentially from the leftmost settlement. 1. Let \(X_L\) be the leftmost settlement of the current group. 2. The rightmost settlement \(X_R\) that can be included in this group must satisfy \(X_R \le X_L + W\) due to the distance constraint. Since it is advantageous to include as many settlements as possible in the same group, we choose the maximum \(R\) that satisfies this condition. 3. Set the leftmost settlement of the next group to \(X_{R+1}\) and repeat the same operation. 4. If the total number of groups after covering all settlements is at most \(K\), the check “succeeds”; if it exceeds \(K\), the check “fails.”

The process of finding the maximum \(R\) satisfying the condition can be performed efficiently using binary search (in Python, bisect_right) on the sorted array \(X\).

Complexity

• Time Complexity: \(O(N \log N \log(\max X))\)

  • The binary search range is from \(0\) to \(X_N - X_1\) (at most approximately \(10^9\)). The number of iterations is \(\log_2(10^9) \approx 30\).
  • In each decision step, we search for the right endpoint \(R\) using bisect_right starting from the left endpoint \(L\). In the worst case, \(N\) binary searches are performed, so the time for one decision step is \(O(N \log N)\).
  • Therefore, the overall complexity is \(O(N \log N \log(\max X))\), which comfortably fits within the time limit.

• Space Complexity: \(O(N)\)

  • Only the memory for the array \(X\) storing the settlement coordinates is used.

Implementation Notes

• When calling bisect_right, specifying lo=L as an argument restricts the search starting position to the current left endpoint $L`. This eliminates unnecessary searches and further reduces execution time.

• As guaranteed by the problem statement, \(2d\) is always an integer, so the binary search range (low, high, mid) can all be handled entirely with integer types.

  Source Code

import sys
import bisect

def solve():
    # 入力を一括取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    
    X = [int(x) for x in input_data[2:]]
    
    # 二分探索の範囲
    low = 0
    high = X[-1] - X[0]
    ans = high
    
    while low <= high:
        mid = (low + high) // 2
        
        # 判定
        count = 0
        L = 0
        possible = True
        while L < N:
            count += 1
            if count > K:
                possible = False
                break
            target = X[L] + mid
            # X[L] + mid 以下の最大の要素のインデックス R を探す
            R = bisect.bisect_right(X, target, lo=L) - 1
            L = R + 1
            
        if possible:
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
            
    print(ans)

if __name__ == '__main__':
    solve()

---

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