Overview

A problem where \(N\) settlements are divided into \(K\) contiguous groups, and the goal is to minimize the maximum “width” (maximum coordinate - minimum coordinate) among all groups. We perform binary search on twice the answer and use a greedy method for the feasibility check.

Analysis

Key Observation 1: Settlement assignments form contiguous groups

The settlements are sorted on a number line. In an optimal arrangement, the settlements assigned to each shelter form a contiguous interval in coordinate order.

This is because if settlements \(A < B < C\) exist and \(A\) and \(C\) are assigned to the same shelter, then \(B\), which is between them, should be closest (or equally close) to that shelter as well.

Key Observation 2: Optimal shelter position for each group

When placing one shelter for a contiguous group \(X_l, X_{l+1}, \ldots, X_r\), the position that minimizes the maximum distance is the midpoint \(\frac{X_l + X_r}{2}\), and the maximum distance at that point is \(\frac{X_r - X_l}{2}\).

Key Observation 3: Binary search on twice the answer

Instead of checking whether \(d\) is achievable, we binary search on \(D = 2d\) (a non-negative integer). The condition becomes “the width of each group satisfies \(X_r - X_l \leq D\).”

Key Observation 4: Determining if division into exactly \(K\) groups is possible

• Minimum number of groups: Greedily make each group as large as possible (extend to the right while width \(\leq D\))
• Maximum number of groups: Each settlement can be an independent group, giving \(N\) groups

If the minimum number of groups \(\leq K \leq N\), then division into exactly \(K\) groups is possible (we can split larger groups as needed).

Algorithm

1. If \(K \geq N\), we can place a shelter at each settlement, so the answer is \(0\)
2. Binary search on \(D = 2d\) (\(0 \leq D \leq 2(X_N - X_1)\))
3. For each \(D\), compute the minimum number of groups using a greedy method:
   • Scan from left to right; if the width from the start of the current group exceeds \(D\), start a new group
4. If the minimum number of groups \(\leq K\), then \(D\) is achievable

Concrete example: For \(N=5, K=2, X=[1, 3, 7, 8, 12]\), \(D=4\): - Group 1: \(\{1, 3\}\) (width \(2 \leq 4\)); adding \(7\) gives width \(6 > 4\), so we cut here - Group 2: \(\{7, 8, 12\}\) (width \(5 > 4\)); adding \(12\) makes it exceed, so we cut - Minimum number of groups = 3 > 2 → \(D=4\) is insufficient

Complexity

• Time complexity: \(O(N \log(\max(X_i)))\) — binary search runs \(O(\log(2 \cdot 10^9))\) times, each feasibility check is \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Since the binary search target is \(2d\) (a non-negative integer), it can be computed exactly using integer binary search

• Cases where the answer is a half-integer are naturally handled by treating \(2d\) as an integer

• In the greedy method, we record “the start of the current group” and start a new group whenever the difference with a new settlement exceeds \(D\)

  Source Code

import sys
from typing import List

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    X = [int(input_data[i + 2]) for i in range(N)]
    
    if K >= N:
        print(0)
        return
    
    # Binary search on 2d (let's call it D = 2d)
    # So d = D/2, and each shelter covers a range of length d on each side.
    # We need to check: can we partition N settlements into K contiguous groups,
    # where each group can be covered by one shelter with max distance <= d = D/2,
    # AND every shelter has at least one settlement assigned to it.
    
    # For a contiguous group of settlements X[l], X[l+1], ..., X[r],
    # the optimal shelter is at (X[l] + X[r]) / 2, and the max distance is (X[r] - X[l]) / 2.
    # So the condition is X[r] - X[l] <= D (since 2d = D means d = D/2, and we need (X[r]-X[l])/2 <= D/2).
    # Wait, (X[r] - X[l]) / 2 <= d = D/2, so X[r] - X[l] <= D.
    
    # But we also need ALL K shelters to have at least 1 settlement.
    # So we must partition into EXACTLY K groups (each non-empty, contiguous).
    
    # Greedy check: given D, can we partition N sorted settlements into exactly K contiguous groups
    # such that each group has span <= D?
    
    # Greedy: go left to right, extend current group as far as possible. Count min groups needed.
    # Also count max groups possible (each group is 1 settlement except when forced).
    # We need min_groups <= K <= max_groups.
    
    # min_groups: greedily make groups as large as possible
    # max_groups: greedily make groups as small as possible (each group = 1 settlement, 
    #             but we must ensure remaining can be covered... actually max_groups = N if D >= 0 always,
    #             since each settlement can be its own group with span 0 <= D for D >= 0)
    # Wait, but K <= N, so max_groups = N always works if D >= 0.
    # So we just need min_groups <= K.
    
    # Actually wait - we need exactly K groups, and each group must have span <= D.
    # min_groups is the minimum number of groups needed. If min_groups <= K, 
    # since we can always split a group into smaller groups (max_groups = N),
    # and K <= N, we can achieve exactly K groups.
    # But we need to be careful: can we always split groups freely?
    # Yes, because groups are contiguous and each single settlement forms a valid group (span 0 <= D).
    # So if min_groups <= K <= N, it's feasible.
    
    def min_groups(D):
        # Minimum number of contiguous groups where each group has X[r] - X[l] <= D
        count = 1
        left = 0
        for right in range(1, N):
            if X[right] - X[left] > D:
                count += 1
                left = right
        return count
    
    # Binary search on D (= 2d), which is a non-negative integer.
    # We need min_groups(D) <= K.
    
    lo, hi = 0, 2 * (X[-1] - X[0])
    
    while lo < hi:
        mid = (lo + hi) // 2
        if min_groups(mid) <= K:
            hi = mid
        else:
            lo = mid + 1
    
    print(lo)

solve()

---

This editorial was generated by claude4.6opus-thinking.