Overview

The condition that resident \(i\) can receive the signal can be rephrased as: “there is a base station within the interval \([X_i-R_i,\;X_i+R_i]\).” In other words, this is a problem where we are given \(N\) intervals and want to place \(K\) points to maximize the number of intervals that contain at least one point (interval stabbing / maximum coverage problem).

Analysis

1. Rephrasing as an Interval Problem

Letting \(L_i = X_i - R_i,\; R'_i = X_i + R_i\), resident \(i\) can receive the signal \(\iff\) at least one of the chosen points falls into \([L_i, R'_i]\). Hereafter, we simply write this interval as \([L_i,R_i]\).

2. Coordinates Are Real Numbers, but There Are Only \(N\) Candidates

Even though we are allowed to choose arbitrary real coordinates, we cannot handle an infinite number of candidates directly. However, the following holds:

There exists an optimal solution in which every point is placed at the right endpoint \(R_i\) of some interval.

Reason: Suppose \(S\) is the set of intervals covered by a point \(p\) (i.e., covered thanks to \(p\)). If we move \(p\) to the right, it will remain inside all intervals in \(S\) up to \(\min_{i\in S} R_i\). By moving \(p\) to that position, \(p\) will coincide with the right endpoint of some interval. Repeating this process for each point proves the claim.

Therefore, it is sufficient to consider only the \(m\ (\le N)\) unique coordinates among \(R_1,\dots,R_N\) as candidates.

3. Why Naive Approaches Fail

An exhaustive search over all \(\binom{m}{K}\) ways to choose \(K\) points from the \(m\) candidates will not finish in time. In addition, greedily choosing the point that stabs the maximum number of intervals is not optimal because this is an instance of the maximum coverage problem (e.g., if one point stabs intervals \(A\) and \(B\), while other points stab only \(A\) or only \(B\), for \(K=2\) it can be better to choose the latter two points).

Thus, we use dynamic programming (DP). The key challenge here is avoiding double-counting intervals.

4. Key Lemma to Avoid Double-Counting

Let the candidate coordinates be sorted as \(c_1 < c_2 < \dots < c_m\), and suppose we place points from left to right. Suppose the most recently placed point is \(c_i\), and the point currently being placed is \(c_j\) (\(i<j\)). Then:

If an interval \([L,R]\) contains \(c_j\) and satisfies \(L \le c_i\), it must also contain \(c_i\).

(Proof: Since \(c_i < c_j \le R\) and \(L \le c_i\), it follows that \(c_i \in [L,R]\).)

Therefore, the number of intervals containing \(c_j\) that have not been counted yet is exactly: $\(\text{cnt}[j][i] = \#\{\,k : L_k \le c_j \le R_k \ \text{and}\ L_k > c_i \,\}\)\( (if \)L_k > c_i\(, its left endpoint is strictly to the right of all existing points \)\le c_i$, so it has not been counted yet). With this, each interval is counted exactly once at the leftmost chosen point that covers it.

Algorithm

1. For each resident, construct the interval \([L_i,R_i]=[X_i-R_i,\,X_i+R_i]\).
2. Deduplicate and sort the right endpoints \(R_i\) to form the candidate coordinates \(c_1<\dots<c_m\). For convenience, define \(c_0=-\infty\) (representing “no points placed yet”).
3. Precompute \(\text{cnt}[j][i]\) (\(1\le j\le m\), \(0\le i<j\)). For a fixed \(j\), each interval \([L,R]\) containing \(c_j\) contributes \(+1\) to all \(i\) satisfying \(c_i < L\). Thus, by finding the position of \(L\) via binary search, we can compute the values for all \(i\) simultaneously using a difference array + prefix sums.
4. DP:
   • \(dp_t[j] =\) “maximum number of covered intervals using \(t\) points, with the \(t\)-th point placed at \(c_j\)”
   • Transitions: \(dp_t[j] = \max_{0\le i<j}\bigl(dp_{t-1}[i] + \text{cnt}[j][i]\bigr)\) (\(dp_0[0]=0\))
   • The answer is the maximum value among all \(dp_t[j]\) for \(t=1,\dots,\min(K,m)\).
5. Although we are required to place exactly \(K\) points, multiple points can be placed at the same coordinate, so it is completely fine if the number of distinct points actually used is \(t\ (\le K)\). Therefore, we can simply iterate \(t\) up to \(\min(K,m)\) and take the maximum.

Complexity

Letting \(m \le N\):

• Time Complexity: \(O(N^2\log N + K N^2)\) (precomputation takes \(O(m(n\log m + m))\), DP takes \(O(K m^2)\)). Since \(N\le 250\), this is around \(250^3 \approx 1.6\times 10^7\) operations.
• Space Complexity: \(O(N^2)\) (for the \(\text{cnt}\) table)

Implementation Notes

• Counting \(\text{cnt}[j][i]\) in \(O(N)\) every time would take \(O(K N^3)\), which is too slow. For a fixed \(j\), for the left endpoint \(L\) of each interval containing \(c_j\), compute bl = bisect_left(cands, L) (= the number of candidates \(c_i\) such that \(c_i < L\)), and apply diff[0] += 1; diff[bl+1] -= 1. Taking the prefix sums will compute all values for \(i=0..m\) at once. Here, \(i=0\) corresponds to \(c_0=-\infty\), and \(\text{cnt}[j][0]\) represents “the total number of intervals containing \(c_j\)”.

• Initialize the DP table with a sufficiently small negative value (NEG) to distinguish unreachable states. Placing the \(t\)-th point at \(c_j\) requires \(j\ge t\), so those entries will naturally remain NEG.

• Since there is no benefit in \(t\) exceeding \(m\), break the loop at min(K, m). Additionally, breaking immediately when the answer reaches \(N\) speeds up execution.

• Because coordinates satisfy \(|X|\le 10^9,\ R\le 10^9\), \(L,R\) can reach around \(2\times10^9\) (in languages like C++, 32-bit signed integers barely fit, but long long is recommended).

• Note that it is sufficient to use only the right endpoints of the intervals as candidates (including left endpoints is also correct, but the argument for the lemma \(L\le c_i \Rightarrow \text{contains } c_i\) and the consistency of the DP work out cleanly and self-contained when using only right endpoint candidates).

  Source Code

import sys
from bisect import bisect_left

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); K = int(data[1])
    Ls = [0]*n; Rs = [0]*n
    for i in range(n):
        x = int(data[2+2*i]); r = int(data[3+2*i])
        Ls[i] = x - r
        Rs[i] = x + r
    cands = sorted(set(Rs))
    m = len(cands)
    NEG = -(1 << 30)

    # cnt[j][i] = number of intervals with L > c_i and L <= c_j <= R
    cnt = [None]*(m+1)
    for j in range(1, m+1):
        p = cands[j-1]
        diff = [0]*(m+2)
        for i in range(n):
            li = Ls[i]
            if li <= p and p <= Rs[i]:
                bl = bisect_left(cands, li)
                diff[0] += 1
                diff[bl+1] -= 1
        s = 0
        arr = [0]*(m+1)
        for i in range(m+1):
            s += diff[i]
            arr[i] = s
        cnt[j] = arr

    dp = [NEG]*(m+1)
    dp[0] = 0
    ans = 0
    tmax = K if K < m else m
    for t in range(1, tmax+1):
        nd = [NEG]*(m+1)
        for j in range(1, m+1):
            cj = cnt[j]
            best = NEG
            for i in range(j):
                v = dp[i]
                if v > NEG:
                    w = v + cj[i]
                    if w > best:
                        best = w
            nd[j] = best
        cur = max(nd)
        if cur > ans:
            ans = cur
        if ans >= n:
            break
        dp = nd
    print(ans)

main()

---

This editorial was generated by claude5opus-high.