Overview

If we view the range where resident \(i\) can receive signals from a base station as the interval \([X_i-R_i,\ X_i+R_i]\), the problem reduces to: “Given \(K\) points, cover as many intervals as possible.”

We solve this using dynamic programming by restricting candidate locations to the right endpoints of intervals and placing base stations from left to right.

Analysis

1. Representing Residents as Intervals

Let \(L_i=X_i-R_i,\ U_i=X_i+R_i\).

The condition for resident \(i\) to receive signals is that at least \(1\) base station lies within the interval \([L_i,U_i]\). Hereafter, we refer to this state as “covering the interval.”

Even if multiple base stations are placed within the same interval, that resident must only be counted once.

2. Only Right Endpoints of Intervals Need to Be Considered

Consider the intervals covered by a certain base station, and let \(q\) be the smallest right endpoint among them.

Moving this base station to the right from its current position up to \(q\) does not cause it to leave any of the intervals it originally covered. This is because the left endpoint of each of these intervals is less than or equal to the current position, and the right endpoint is greater than or equal to \(q\).

Therefore, without decreasing the number of residents who can receive signals, each base station can be shifted to the right endpoint of some interval. Base stations that cover no residents can be moved arbitrarily.

Thus, we only need to consider the deduplicated and sorted right endpoints:

\(P_0<P_1<\cdots<P_{M-1}\)

as candidate positions. The number of candidates satisfies \(M\le N\).

However, even with candidates restricted, enumerating all combinations of choosing \(K\) locations is too large. Furthermore, simply summing the number of residents covered by each base station would double-count residents who can receive signals from multiple base stations.

3. The Number of Newly Covered Residents Depends Only on the Previous Base Station

Suppose we place base stations from left to right. Consider adding a new base station at \(P_j\) to the right of the current rightmost base station at \(P_p\).

For an interval \([L_i,U_i]\) containing \(P_j\), the following holds:

• If \(L_i\le P_p\), then \(L_i\le P_p<P_j\le U_i\), so it is already covered by \(P_p\).
• If \(P_p<L_i\), all previous base stations are strictly to the left of \(L_i\), so it is not yet covered.

Thus, the newly covered intervals are precisely those satisfying:

\(P_p<L_i\le P_j\le U_i\)

Let this count be \(G[p][j]\). To find the number of additionally covered residents, we do not need to remember the positions of base stations placed before \(P_p\). Only maintaining the position of the most recently placed base station in the state is why dynamic programming can be used.

For example, if the previous base station is at \(3\) and the added base station is at \(7\), the interval \([2,8]\) is already covered, while the interval \([5,9]\) is newly covered.

Algorithm

1. Handle the Case Where Everyone Can Be Covered First

In the code, we first find the minimum number of base stations required to cover all intervals using a greedy approach:

1. Sort the intervals in ascending order of their right endpoints.
2. When an uncovered interval appears, place a base station at its right endpoint.

The uncovered interval with the leftmost right endpoint must be covered somewhere within that interval. Placing the base station as far right as possible within it maximizes the chance of covering subsequent intervals, so this greedy approach finds the minimum number of base stations.

If the required number is at most \(K\), the answer is \(N\). Any leftover base stations can be placed at the same location.

Note that this greedy method is solely for finding the “minimum number to cover all intervals.” When base stations are insufficient, “maximizing the number of covered intervals” is handled by the subsequent dynamic programming.

2. Precomputing the Additional Covered Count

For each candidate \(P_j\), we compute the following:

• \(C[j]\): the number of intervals containing \(P_j\)
• \(G[p][j]\): the number of intervals containing \(P_j\) and satisfying \(L_i>P_p\)

Checking all intervals for every pair \((p,j)\) would take \(O(NM^2)\) time. In the code, we speed this up by mapping left endpoints to candidate positions and aggregating them.

For each interval, we find:

\(t_i=\min\{t\mid P_t\ge L_i\}\)

using bisect_left. Since each interval’s own right endpoint is included in the candidates, this index is guaranteed to exist.

Considering only the intervals containing \(P_j\), we count their occurrences into buckets[t_i]. Since

\(L_i\le P_p \iff t_i\le p\)

it follows that:

\(G[p][j]=C[j]-\sum_{t=0}^{p}\mathrm{buckets}[t]\)

Therefore, starting from count = C[j] and subtracting buckets[p] in the order \(p=0,1,\ldots,j-1\), we can determine each \(G[p][j]\). In the code, this is stored in gains[j][p].

3. Dynamic Programming

We define the DP state as follows:

\(dp_t[j]\): the maximum number of intervals that can be covered by placing \(t\) base stations at distinct candidate positions, with the rightmost base station at \(P_j\).

For \(1\) base station:

\(dp_1[j]=C[j]\)

For \(t\ge2\), iterating over all possible positions \(P_p\) of the previous base station gives the transition:

\(dp_t[j]=\max_{t-2\le p<j}\left(dp_{t-1}[p]+G[p][j]\right)\)

To choose \(t\) distinct candidates, we must have \(j\ge t-1\).

From the previous analysis, \(G[p][j]\) accurately represents the “number of newly covered residents” regardless of earlier placements. Thus, this transition avoids any duplicate counting.

The answer is \(\max_j dp_K[j]\).

Placing multiple base stations at the same location does not increase the number of covered residents. Furthermore, if the algorithm did not terminate early, \(K<M\) holds; hence, if fewer than \(K\) locations are used, we can always add unused candidates. Since adding candidates never decreases the number of covered residents, restricting the DP to selecting \(K\) distinct candidates is completely fine.

In the code, only the DP array of the previous count is maintained and updated using dp and new_dp.

Complexity

Let \(M\) be the number of candidate positions, where \(M\le N\).

• Time complexity: \(O(N\log N+NM+M^2+KM^2)\), which is \(O(KN^2)\) in the worst case
• Space complexity: \(O(N+M^2)\), which is \(O(N^2)\) in the worst case

Precomputing the additional counts takes \(O(NM+M^2)\) time, and the dynamic programming takes \(O(KM^2)\) time. Space is primarily used to store gains.

Implementation Details

• Intervals are closed intervals. Since a resident can receive signals even if a base station is at an endpoint, inclusion is checked with left <= point <= right.

• The condition for being newly covered is left > previous base station position. If they are equal, it is already covered.

• Duplicate candidate positions are removed, but duplicate resident intervals are not. Residents at the same location with the same range are each counted as \(1\) resident.

• In the greedy algorithm, a base station is added only when left > last. Since intervals are processed in order of their right endpoints, it is otherwise covered by the last placed base station.

• Use a separate array for DP updates to avoid reusing values updated within the same iteration.

  Source Code

import sys
from bisect import bisect_left


def main():
    input = sys.stdin.buffer.readline
    n, k = map(int, input().split())

    intervals = []
    for _ in range(n):
        x, r = map(int, input().split())
        intervals.append((x - r, x + r))

    intervals.sort(key=lambda interval: interval[1])

    needed = 0
    last = -10**30
    for left, right in intervals:
        if left > last:
            needed += 1
            last = right

    if k >= needed:
        print(n)
        return

    points = sorted(set(right for _, right in intervals))
    m = len(points)
    indexed = [
        (left, right, bisect_left(points, left))
        for left, right in intervals
    ]

    gains = []
    dp = [0] * m

    for j, point in enumerate(points):
        buckets = [0] * (j + 1)
        count = 0
        for left, right, threshold in indexed:
            if left <= point <= right:
                buckets[threshold] += 1
                count += 1

        dp[j] = count
        row = [0] * j
        for p in range(j):
            count -= buckets[p]
            row[p] = count
        gains.append(row)

    for used in range(2, k + 1):
        new_dp = [-1] * m
        start = used - 2
        for j in range(used - 1, m):
            row = gains[j]
            best = -1
            for p in range(start, j):
                value = dp[p] + row[p]
                if value > best:
                    best = value
            new_dp[j] = best
        dp = new_dp

    print(max(dp))


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-6-astra-medium.