Overview

The range of base station positions that resident \(i\) can receive signals from is the interval \([X_i-R_i,\ X_i+R_i]\). Therefore, we can formulate this as a problem to place \(K\) points to maximize the number of intervals that contain at least one point.

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

Analysis

1. We only need to consider the right endpoints of intervals as base station positions

Let \([L_i, U_i]\) be the interval corresponding to resident \(i\):

• \(L_i=X_i-R_i\)
• \(U_i=X_i+R_i\)

Suppose a base station is located at coordinate \(p\) and is contained in some set of intervals. Shift this base station to the right up to the minimum of the right endpoints of those intervals.

Let \(q\) be the new position. For all intervals that originally contained the base station,

\(L_i\le p\le q\le U_i\)

holds, so no resident who could previously receive a signal will lose coverage.

Any base station not contained in any interval can be moved to an arbitrary right endpoint. Thus, there exists an optimal solution where all base stations are placed at the right endpoints of intervals.

Let the sorted, unique candidate coordinates of right endpoints be

\(p_0<p_1<\cdots<p_{M-1}\).

The number of candidates is \(M\le N\).

2. Exhaustive search over candidate combinations is intractable

Even after narrowing down the candidates to a finite set, searching through all combinations of \(K\) candidates is intractable because the number of combinations is too large.

Furthermore, simply summing the number of intervals covered by each base station would double-count intervals that contain multiple base stations.

Therefore, we add base stations from left to right and count only the newly covered residents.

3. The number of newly covered intervals depends only on the immediately preceding base station

Suppose the rightmost base station among those already placed is at \(p_i\). We now add a base station at \(p_j\) (\(i<j\)).

Consider an interval \([L_v,U_v]\) that contains \(p_j\). There are two cases:

• If \(L_v\le p_i\):
  Since \(L_v\le p_i<p_j\le U_v\), this interval also contains \(p_i\). Therefore, it is already covered.
• If \(p_i<L_v\):
  Since all existing base stations are located at coordinates \(\le p_i\), none of them fall into this interval. Therefore, it is covered for the first time.

Thus, the condition for an interval to be newly covered is

\(p_i<L_v\le p_j\le U_v\).

For example, if the preceding base station is at \(3\) and the newly added base station is at \(7\), the interval \([5,9]\) is newly covered. On the other hand, the interval \([2,8]\) is already covered by the base station at coordinate \(3\).

Thanks to this property, we do not need to keep track of the positions of all previous base stations; it is sufficient to maintain only the position of the rightmost base station in our state.

Algorithm

1. Construct candidate coordinates

Collect the right endpoints \(U_i\) of all intervals, sort them, and remove duplicates.

Note that if \(K\ge M\), we can place a base station at every candidate coordinate. Since each interval is covered by the base station at its own right endpoint, the answer is \(N\).

Excess base stations can simply be placed on top of already used coordinates, satisfying the “exactly \(K\)” condition.

2. Precompute coverage and increments

Prepare the following arrays:

• \(\mathrm{cover}[j]\): the number of intervals containing \(p_j\)
• \(\mathrm{gain}[i][j]\): the number of newly covered intervals when adding a base station at \(p_j\) given that the rightmost base station is at \(p_i\)

Specifically,

\(\mathrm{cover}[j]=\#\{v\mid L_v\le p_j\le U_v\}\)

\(\mathrm{gain}[i][j]=\#\{v\mid p_i<L_v\le p_j\le U_v\}\quad(i<j)\).

In the implementation, we check the intervals containing each \(p_j\) to increment \(\mathrm{cover}[j]\), and further increment \(\mathrm{gain}[i][j]\) for each \(i<j\) satisfying \(p_i<L_v\).

3. Run dynamic programming

Define \(\mathrm{DP}_t[j]\) as follows:

The maximum number of covered intervals when placing between \(1\) and \(t\) base stations, with the rightmost base station located at \(p_j\).

When placing \(1\) base station:

\(\mathrm{DP}_1[j]=\mathrm{cover}[j]\).

When adding a base station, if the previous rightmost base station was at \(p_i\), we can cover

\(\mathrm{DP}_{t-1}[i]+\mathrm{gain}[i][j]\)

intervals.

Including the option of not adding a base station, the transition is:

\(\mathrm{DP}_t[j]=\max\left(\mathrm{DP}_{t-1}[j],\ \max_{0\le i<j}\left(\mathrm{DP}_{t-1}[i]+\mathrm{gain}[i][j]\right)\right)\).

This transition counts already-covered intervals and newly covered intervals without overlap. Furthermore, removing the rightmost base station always results in a valid prior state, ensuring that all valid configurations are considered.

In the code, only the previous step is stored in dp, and the next step is computed into next. The initialization next = dp corresponds to the choice of not adding a base station.

4. Compute the answer

The answer is

\(\max_{0\le j<M}\mathrm{DP}_K[j]\).

Although the dynamic programming considers “at most \(K\)” base stations, any unused base stations can be placed on top of already occupied coordinates, so the maximum value is identical to the “exactly \(K\)” case.

Complexity

Let \(M\) (\(M\le N\)) be the number of candidate coordinates.

• Time complexity: \(O(N\log N+NM^2+KM^2)\). Precomputation takes \(O(NM^2)\) and dynamic programming takes \(O(KM^2)\). Since \(K,M\le N\), the overall time complexity is \(O(N^3)\).
• Space complexity: \(O(N+M^2)\). This is mainly used to store gain, giving \(O(N^2)\) overall.

Implementation Notes

• Intervals are inclusive of both endpoints. The coverage condition is \(L_v\le p_j\le U_v\).

• The condition for an interval to be newly covered is \(p_i<L_v\). If \(p_i=L_v\), it was already covered by an earlier base station.

• Even though duplicate candidate coordinates are removed, residents with identical intervals are counted separately.

• Since points is sorted in ascending order, once points[i] < L[v] is no longer satisfied, subsequent candidates will not satisfy it either. Thus, the inner loop of the precomputation can be broken early.

• long long is used in the code to calculate the endpoints.

• The DP separates dp and next, always transitioning from the previous step. This prevents adding multiple base stations in the same step.

  Source Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    vector<long long> L(N), R(N), points;
    for (int i = 0; i < N; ++i) {
        long long x, r;
        cin >> x >> r;
        L[i] = x - r;
        R[i] = x + r;
        points.push_back(R[i]);
    }

    sort(points.begin(), points.end());
    points.erase(unique(points.begin(), points.end()), points.end());
    int M = static_cast<int>(points.size());

    if (K >= M) {
        cout << N << '\n';
        return 0;
    }

    vector<int> cover(M, 0);
    vector<vector<int>> gain(M, vector<int>(M, 0));

    for (int j = 0; j < M; ++j) {
        for (int v = 0; v < N; ++v) {
            if (L[v] <= points[j] && points[j] <= R[v]) {
                ++cover[j];
                for (int i = 0; i < j && points[i] < L[v]; ++i) {
                    ++gain[i][j];
                }
            }
        }
    }

    vector<int> dp = cover;
    for (int used = 2; used <= K; ++used) {
        vector<int> next = dp;
        for (int j = 0; j < M; ++j) {
            for (int i = 0; i < j; ++i) {
                next[j] = max(next[j], dp[i] + gain[i][j]);
            }
        }
        dp.swap(next);
    }

    cout << *max_element(dp.begin(), dp.end()) << '\n';
    return 0;
}

---

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