Overview

If we treat each resident \(i\) as an interval \([X_i-R_i,\; X_i+R_i]\), the problem becomes: “Place \(K\) points to maximize the number of intervals pierced (covered) by at least one point.” We can restrict the candidate locations to the left endpoints of the intervals and solve this using DP that tracks the “position of the last placed base station”.

Analysis

1. Rephrasing as an Interval Problem

The condition for resident \(i\) to receive the signal is \(|X_i - P|\le R_i\), which is $\(L_i = X_i - R_i \le P \le X_i + R_i = R'_i\)\( Thus, resident \)i\( corresponds to the interval \)I_i=[L_i, R’_i]\(, and the problem reduces to placing \)K\( points such that at least one point is contained in \)I_i$ (the maximum stabbing problem).

2. Candidate Positions: Left Endpoints Suffice

Although there are infinitely many real coordinates, we can show that in an optimal solution, it suffices to restrict the base station locations to the “left endpoints of some intervals”.

Let \(S\) be the set of intervals covered by a base station at \(P\). If we shift \(P\) to the left, as long as \(P \ge \max_{i \in S} L_i\), the condition \(L_i \le P \le R'_i\) remains satisfied for all \(i \in S\) (moving to the left only relaxes the right endpoint constraint). Therefore, even if we shift \(P\) leftward to \(\max_{i\in S} L_i\), the set of covered intervals does not decrease. This position is the left endpoint of an interval. Base stations that cover no intervals do not affect the answer, so they can be ignored.

Hence, the candidate positions are at most \(N\) unique points among \(L_1,\dots,L_N\) (after removing duplicates).

3. Why Naive Approaches Fail

• Brute Force: Choosing \(K\) points out of \(M\ (\le 250)\) candidates gives \(\binom{M}{K}\) combinations, which is far too large.
• Greedy: Repeatedly choosing the point that covers the most intervals is not optimal. For example, picking a large cluster in the middle might prevent covering intervals on both sides (greedy approaches for set cover problems generally do not yield optimal solutions).

4. Key Observation for DP

Sort the candidate positions in ascending order as \(c_1 < c_2 < \dots < c_M\), and we will select the base station positions from left to right. Let \(S(j) = \{i \mid L_i \le c_j \le R'_i\}\) (the set of intervals containing \(c_j\)).

The key observation here is the following property:

Lemma: Let \(j_0 < j < j_2\). If an interval \(I_i\) contains both \(c_{j_0}\) and \(c_{j_2}\), then \(I_i\) also contains \(c_j\).

This holds because an interval is a contiguous set of points (\(L_i \le c_{j_0} < c_j < c_{j_2} \le R'_i\)).

From this lemma, we can see that when we place a new base station at \(c_{j_2}\), the newly covered intervals are precisely those that do not contain the immediately preceding placed position \(c_j\). This is because any interval containing \(c_{j_2}\) and also covered by some base station prior to \(c_j\) must also contain \(c_j\) (by the lemma); thus, any interval in \(S(j_2)\setminus S(j)\) is guaranteed to have not been covered yet.

In other words, the core insight is that we only need to remember the immediately preceding position to compute the incremental gain without overcounting.

Algorithm

1. For each resident, compute \(L_i = X_i-R_i,\ R'_i = X_i+R_i\).
2. Sort and remove duplicates from the candidate positions \(\{L_i\}\), obtaining \(c_1<\dots<c_M\).
3. For each \(j\), represent the set of intervals containing \(c_j\), \(S(j)\), using a bitset.
4. Precompute the difference table \(\mathrm{cnt}[j_2][j] = |S(j_2) \setminus S(j)| = |S(j_2)\ \&\ {\sim}S(j)|\) (using bitset’s count()).
5. DP:
   • \(dp[1][j] = |S(j)|\)
   • \(dp[t+1][j_2] = \max_{j < j_2} \left( dp[t][j] + \mathrm{cnt}[j_2][j] \right)\)
6. The answer is \(\max_{1\le t\le K,\ j} dp[t][j]\).

Values for \(t < K\) can also be candidates for the answer because leftover base stations can simply be placed at the same coordinates as already placed stations (placing multiple stations at the same coordinate is allowed). Moreover, when \(K > M\), placing stations at all \(t=M\) candidate positions will cover every interval at its left endpoint, making the answer \(N\) (the DP can be terminated early once \(j\) can no longer be increased).

Example

For \(N=3, K=1\) and intervals \([0,2],[1,5],[4,6]\), the candidates are \(0,1,4\). - \(S(0)=\{1\},\ S(1)=\{1,2\},\ S(4)=\{2,3\}\)

Since \(K=1\), the answer is \(\max(1,2,2)=2\). If \(K=2\), we could transition, for example, from \(j=1\) (coordinate \(1\), \(dp=2\)) to \(j=2\) (coordinate \(4\)); since \(\mathrm{cnt} = |\{2,3\}\setminus\{1,2\}| = 1\), the value becomes \(3\), allowing everyone to receive the signal.

Complexity

Assuming \(M \le N\):

• Time Complexity: Precomputing the difference table takes \(O(N^3/w)\) (\(w=64\), speedup with bitset), and the DP takes \(O(K N^2)\), giving an overall time complexity of \(O(N^3)\) (for \(N=250\), about \(1.5\times10^7\) operations, which is well within the time limit).
• Space Complexity: \(O(N^2)\) (an \(M\times M\) int array for the difference table, roughly \(250^2\)).

Implementation Notes

• Since \(|X_i| \le 10^9,\ R_i \le 10^9\), \(X_i \pm R_i\) can reach up to \(2\times10^9\), which can overflow a 32-bit int. Handle them using long long.

• Make sure to remove duplicates from the candidate positions (having duplicate candidate coordinates will not align with the strictly increasing condition in the DP and will lead to redundant computations).

• Since \(N \le 250\), bitset<256> is sufficient. The count of newly covered intervals can be found directly with (bs[j2] & ~bs[j]).count().

• Initialize the DP table with a sufficiently small negative value (such as \(-10^6\)) representing unreachable states, to avoid transitioning from unreachable states.

• Restrict transitions to \(j < j_2\) (from left to right). This normalizes the choice to “selecting base stations in increasing order of coordinates”, which is necessary to apply the lemma.

• Take the maximum over all \(t \le K\) for the final answer (it is not necessary to use all stations at distinct positions).

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, K;
    if(scanf("%d %d", &N, &K) != 2) return 0;
    vector<long long> L(N), Rt(N);
    for(int i = 0; i < N; i++){
        long long x, r;
        scanf("%lld %lld", &x, &r);
        L[i] = x - r;
        Rt[i] = x + r;
    }
    // candidate positions: left endpoints
    vector<long long> cand = L;
    sort(cand.begin(), cand.end());
    cand.erase(unique(cand.begin(), cand.end()), cand.end());
    int M = (int)cand.size();

    vector<bitset<256>> bs(M);
    for(int j = 0; j < M; j++){
        long long p = cand[j];
        for(int i = 0; i < N; i++){
            if(L[i] <= p && p <= Rt[i]) bs[j].set(i);
        }
    }

    // cntmat[j][i] = number of intervals containing cand[j] but not cand[i]
    vector<vector<int>> cntmat(M, vector<int>(M, 0));
    for(int j = 0; j < M; j++){
        for(int i = 0; i < M; i++){
            bitset<256> t = bs[j] & (~bs[i]);
            cntmat[j][i] = (int)t.count();
        }
    }

    const int NEG = -1000000;
    // dp[t][j]: max covered with t stations, last at cand[j]
    vector<int> dpPrev(M, NEG), dpCur(M, NEG);
    int ans = 0;
    for(int j = 0; j < M; j++) dpPrev[j] = (int)bs[j].count();
    for(int j = 0; j < M; j++) ans = max(ans, dpPrev[j]);

    for(int t = 1; t < K; t++){
        for(int j = 0; j < M; j++) dpCur[j] = NEG;
        for(int j = 0; j < M; j++){
            if(dpPrev[j] < 0) continue;
            int base = dpPrev[j];
            const vector<int>* row;
            for(int j2 = j + 1; j2 < M; j2++){
                int v = base + cntmat[j2][j];
                if(v > dpCur[j2]) dpCur[j2] = v;
            }
            (void)row;
        }
        bool any = false;
        for(int j = 0; j < M; j++){
            if(dpCur[j] > ans) ans = dpCur[j];
            if(dpCur[j] > NEG) any = true;
        }
        if(!any) break;
        dpPrev = dpCur;
    }

    printf("%d\n", ans);
    return 0;
}

---

This editorial was generated by claude5opus-high.