Overview

Given the positions and elevations of villages, find the minimum number of radio towers to install to cover all villages under specified conditions.

Analysis

In this problem, we must determine whether each village can receive signals from a radio tower, and then find the minimum number of radio towers that satisfies these conditions.

First, an important observation is that processing becomes easier when villages are considered in order of position. Also, since radio towers can only be installed at villages with elevation \(K\) or higher, it is efficient to separately manage only the candidate villages where installation is possible.

Next, we need to verify that every village can be covered by at least one radio tower. That is, we check whether, for each village, there exists a village with elevation \(K\) or higher within \(D\) meters in either direction. If no such village exists, the conditions cannot be satisfied, so we output -1.

Finally, when actually installing radio towers, we use a greedy algorithm. The strategy is: “To cover the village currently being considered, install a radio tower at the position that covers as far as possible.” In other words, among the villages within the coverable range of the current village of interest, we install a radio tower at the rightmost village with elevation \(K\) or higher, thereby simultaneously covering as many subsequent villages as possible.

The correctness of this greedy algorithm comes from the fact that “the further right we install, the more villages we can cover.” Additionally, by using binary search, we can efficiently find candidates within the range.

Algorithm

1. Read the input and sort villages by position
2. Store the indices of villages with elevation \(K\) or higher in cand_indices
3. For each village, use binary search to check whether a village with elevation \(K\) or higher exists within distance \(D\)
   • If none exists, output -1 and terminate
4. Find the minimum number of radio towers using a greedy algorithm
   • Starting from the leftmost village, install a radio tower at the rightmost village with elevation \(K\) or higher within the coverable range
   • Skip villages that are covered by the installed radio tower
5. Output the number of installed radio towers

Complexity

• Time complexity: \(O(N \log N)\)
• Space complexity: \(O(N)\)

The time complexity is dominated primarily by sorting and binary search operations. The operation of searching for candidates using binary search for each village is \(O(\log N)\), and since this is repeated \(N\) times, the overall complexity is \(O(N \log N)\).

Implementation Notes

• When sorting villages by position, elevation information must also be managed together

• Having an index list cand_indices of tower-installable villages (elevation \(K\) or higher) makes binary search straightforward

• When searching for the “rightmost installable village” in the greedy algorithm, logic is needed for binary search on the position array and then searching backward from there to find the first candidate

• Be careful about out-of-bounds access and handle boundary conditions with care

  Source Code

import sys
from bisect import bisect_left, bisect_right

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    D = int(data[idx])
    idx += 1
    
    X = []
    P = []
    for _ in range(N):
        x = int(data[idx])
        idx += 1
        p = int(data[idx])
        idx += 1
        X.append(x)
        P.append(p)
    
    # 村を位置順にソート
    villages = sorted(zip(X, P))
    X_sorted = [v[0] for v in villages]
    P_sorted = [v[1] for v in villages]
    
    # 電波塔を設置可能な村のインデックスをリストアップ
    cand_indices = []
    for i in range(N):
        if P_sorted[i] >= K:
            cand_indices.append(i)
    
    # 各村が被覆可能かチェック
    for i in range(N):
        # 二分探索で距離D以内に標高K以上の村があるか確認
        x = X_sorted[i]
        left = bisect_left(X_sorted, x - D)
        right = bisect_right(X_sorted, x + D) - 1
        # [left, right] の範囲内に標高K以上の村があるか
        # cand_indices は昇順なので、これも二分探索可能
        l_idx = bisect_left(cand_indices, left)
        r_idx = bisect_right(cand_indices, right)
        if l_idx >= r_idx:
            print(-1)
            return
    
    # 被覆可能な場合、貪欲法で最小タワー数を求める
    # 左端から見て、カバーできる最も右の候補地にタワーを設置
    count = 0
    i = 0
    while i < N:
        # 村iをカバーするには、[X_sorted[i] - D, X_sorted[i] + D] 内にタワーが必要
        # タワーはこの範囲内で最も右（X_sortedが大きい）かつ標高K以上である村に設置するのが最適
        # 最も右の候補を探す
        right_limit = X_sorted[i] + D
        # X_sortedの中でright_limit以下の最大の要素のインデックスを求める
        pos = bisect_right(X_sorted, right_limit) - 1
        
        # このposから左方向にさかのぼって、最初に見つかる標高K以上の村が最適な設置場所
        tower_pos = -1
        j = pos
        while j >= 0:
            if P_sorted[j] >= K:
                tower_pos = j
                break
            j -= 1
        
        if tower_pos == -1:
            print(-1)
            return
        
        # このタワーでカバーできる最も右の村を見つける
        coverage_end = X_sorted[tower_pos] + D
        while i < N and X_sorted[i] <= coverage_end:
            i += 1
        
        count += 1
    
    print(count)

if __name__ == "__main__":
    main()

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