Overview

This problem asks for the minimum cost to illuminate all \(N\) houses lined up in a straight line using \(M\) types of streetlights. Each streetlight can be installed at any real-valued coordinate and illuminates all houses within radius \(R_j\) from its installation position.

Analysis

Key Insight ①: Sort houses and reduce to an interval covering problem

When the house coordinates are sorted, the houses illuminated by a single streetlight form a contiguous interval. This is because the range illuminated by a streetlight is a continuous interval \([p - R_j, p + R_j]\) on the number line, and among the sorted houses, those that are illuminated are necessarily contiguous.

Key Insight ②: Greedy placement

When we want to illuminate as many houses to the right as possible starting from house \(i\) (0-indexed), the optimal placement is to install the streetlight at position \(X_i + R_j\). In this case: - Left end: \(X_i + R_j - R_j = X_i\) (exactly illuminates house \(i\)) - Right end: \(X_i + R_j + R_j = X_i + 2R_j\)

In other words, all houses with coordinates at most \(X_i + 2R_j\) are illuminated.

Problem with the naive approach

If we try all possibilities of “which streetlight to place where to illuminate each house \(i\)”, the state space explodes. However, using the greedy placement described above, we can construct an efficient DP.

Algorithm

DP Definition: \(dp[i]\) = minimum cost to illuminate all of the first \(i\) houses after sorting (houses \(0, 1, \ldots, i-1\))

Initial Value: \(dp[0] = 0\) (the state where no houses need to be illuminated yet)

Transition: From state \(i\) (houses \(0\) through \(i-1\) already illuminated), choose a streetlight to illuminate house \(i\): - Install a streetlight of type \(j\) at \(X_i + R_j\), which illuminates all houses with coordinates \(\leq X_i + 2R_j\) - Use binary search to find the index \(\text{nxt}\), which is one past the last house illuminated - \(dp[\text{nxt}] = \min(dp[\text{nxt}],\ dp[i] + C_j)\)

Answer: \(dp[N]\)

Concrete Example

Suppose houses are at coordinates \([1, 3, 7, 10]\), and there is a streetlight with radius \(2\) and cost \(5\). - Starting from \(dp[0] = 0\), illuminate house \(0\) (coordinate \(1\)) - Install streetlight at \(1 + 2 = 3\) → illuminates houses with coordinates \(\leq 1 + 4 = 5\) → houses \(0, 1\) are illuminated - \(dp[2] = \min(dp[2], 0 + 5) = 5\)

Complexity

• Time complexity: \(O(N \log N + NM \log N)\)
  • \(O(N \log N)\) for sorting
  • \(N \times M\) DP transitions, each with a binary search in \(O(\log N)\)
• Space complexity: \(O(N + M)\)

Since \(N, M \leq 3000\), \(NM = 9 \times 10^6\) transitions is sufficiently fast.

Implementation Notes

• It is essential to sort the house coordinates before performing the DP. Without sorting, we cannot exploit the structure of “illuminating contiguous houses with a single streetlight.”

• Use binary search (bisect_right) to efficiently find the number of houses with coordinates at most \(X_i + 2R_j\).

• Skip transitions from states where dp[i] == INF to avoid unnecessary computation.

• The answer is guaranteed to fit in a \(64\)-bit integer, but in Python there is no need to worry about integer overflow.

  Source Code

import sys
from bisect import bisect_right

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    X = []
    for i in range(N):
        X.append(int(input_data[idx])); idx += 1
    
    lights = []
    for j in range(M):
        R = int(input_data[idx]); idx += 1
        C = int(input_data[idx]); idx += 1
        lights.append((R, C))
    
    X.sort()
    
    # Precompute: for each light type j, and for each starting house i,
    # how many consecutive houses (starting from i) can one light of type j cover?
    # A light of type j with radius R can cover all houses in a contiguous range of width 2*R.
    # If we want to cover houses starting from house i, the optimal placement covers
    # houses from X[i] to X[i] + 2*R. So we find the rightmost house with coordinate <= X[i] + 2*R.
    
    # DP: dp[i] = minimum cost to illuminate houses 0..i-1 (first i houses)
    # dp[0] = 0
    # dp[i] = min over all ways to cover a suffix ending at house i-1
    # For each light type j, if we place it to cover houses starting at house k,
    # it covers houses k..m-1 where m is the furthest house reachable.
    # dp[m] = min(dp[m], dp[k] + C_j)
    
    # Equivalently: dp[i] = min over j, over valid k such that one light of type j
    # can cover houses k..i-1, of dp[k] + C_j
    # For light type j covering houses k..i-1: need X[i-1] - X[k] <= 2*R_j
    # So k >= leftmost index where X[k] >= X[i-1] - 2*R_j
    
    # But this is O(N*M*N) naively. We need to be smarter.
    
    # Alternative approach: dp[i] = min cost to cover houses 0..i-1
    # Transition: for each light type j, from state i (houses 0..i-1 covered),
    # place a light of type j starting to cover house i. It covers houses i..nxt_j(i)-1
    # where nxt_j(i) = number of houses with coordinate <= X[i] + 2*R_j.
    # dp[nxt_j(i)] = min(dp[nxt_j(i)], dp[i] + C_j)
    
    # This is O(N*M) which is 2000*2000 = 4M, acceptable.
    
    INF = float('inf')
    dp = [INF] * (N + 1)
    dp[0] = 0
    
    # Precompute for each (i, j): if we start covering from house i with light j,
    # how far do we get?
    # The light covers [X[i] - R_j, X[i] + R_j] optimally placed at X[i] + R_j (or wherever).
    # Actually, we place the light at position p, covering [p - R_j, p + R_j].
    # We need house i to be covered: |X[i] - p| <= R_j, so p >= X[i] - R_j.
    # To maximize coverage to the right, set p = X[i] + R_j.
    # Then the light covers houses with coordinate <= X[i] + 2*R_j.
    
    for i in range(N):
        if dp[i] == INF:
            continue
        for R, C in lights:
            # Place light to cover from house i onwards as far as possible
            max_coord = X[i] + 2 * R
            # Find number of houses with coordinate <= max_coord
            nxt = bisect_right(X, max_coord)
            if dp[nxt] > dp[i] + C:
                dp[nxt] = dp[i] + C
    
    print(dp[N])

solve()

---

This editorial was generated by claude4.6opus-thinking.