Overview

Since all shooting stars move in the upper-left direction (diagonally), the problem can be reduced to an “interval covering problem” on each diagonal. For each diagonal, we greedily find the minimum set of points that stabs all intervals.

Analysis

Key Observation: Shooting Stars Move Along Diagonals

The \(k\)-th shooting star is at position \((R_k - t, C_k - t)\) at time \(t\). Since both the row and column numbers decrease by \(1\) simultaneously, the difference \(R_k - C_k\) remains constant. In other words, each shooting star moves only along the diagonal where \(R - C = \) constant.

Since shooting stars on different diagonals do not interfere with each other, we can consider each diagonal independently.

Converting to Intervals on a Diagonal

On diagonal \(d = R_k - C_k\), we determine the range of row numbers that shooting star \(k\) passes through.

• Existence condition: \(R_k - t \geq 1\) and \(C_k - t \geq 1\), i.e., \(t \leq \min(R_k, C_k) - 1\)
• Minimum row passed through: \(R_k - (\min(R_k, C_k) - 1) = \max(1,\ d+1)\)
• Maximum row passed through: \(R_k\) (position at time \(0\))

Therefore, on diagonal \(d\), shooting star \(k\) passes through the row interval \([\max(1, d+1),\ R_k]\).

Reduction to the Interval Stabbing Problem

If a camera is placed at \((r, c)\), it can photograph all shooting stars on the same diagonal \(r - c = d\) whose row interval contains \(r\).

This reduces to the minimum point cover problem (Interval Point Cover): “find the minimum number of points needed to stab all given intervals with at least one point each.”

Algorithm

For each diagonal, we apply the classical greedy algorithm:

1. Group shooting stars by diagonal \(d = R_k - C_k\)
2. Within each diagonal, sort intervals \([L_k, R_k]\) (where \(L_k = \max(1, d+1)\)) in ascending order of right endpoint \(R_k\)
3. Process intervals in order; when encountering a shooting star not yet covered by any camera, place a camera at the right endpoint of that interval (placing it at the right endpoint covers as many subsequent intervals as possible)

Concrete example: On diagonal \(d = 0\), there are intervals \([1, 3]\), \([2, 5]\), \([4, 6]\) - \([1, 3]\): not covered → place camera at row \(3\) - \([2, 5]\): row \(3\) is contained in this interval → already covered - \([4, 6]\): row \(3\) is not contained in this interval → place camera at row \(6\) - → Total: 2 cameras

Complexity

• Time complexity: \(O(N \log N)\) (grouping each shooting star and sorting per diagonal; the total sorting cost is \(O(N \log N)\))
• Space complexity: \(O(N)\) (dictionary holding shooting star information)

Implementation Notes

• Although \(H, W\) can be up to \(10^9\) (very large), by grouping into a dictionary by diagonal value \(d = R_k - C_k\), coordinate compression is unnecessary

• The greedy algorithm can be implemented simply by sorting by right endpoint of intervals and maintaining last_placed (the row number where the last camera was placed)

• Although it is guaranteed that no two shooting stars share the same initial position, note that multiple shooting stars can exist on the same diagonal

  Source Code

import sys
from collections import defaultdict

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    H = int(input_data[idx]); idx += 1
    W = int(input_data[idx]); idx += 1
    N = int(input_data[idx]); idx += 1
    
    # Each meteor k starts at (R_k, C_k) and moves to (R_k-t, C_k-t) for t=0,1,...,min(R_k,C_k)-1
    # The path of meteor k is all cells (R_k-t, C_k-t) where the diagonal is R_k - C_k = constant
    # and the position along that diagonal ranges from min(R_k, C_k) steps.
    # 
    # Specifically, on diagonal d = R_k - C_k, the meteor occupies cells where:
    #   if d >= 0: row goes from d+1 to R_k (i.e., col goes from 1 to C_k)
    #   if d < 0:  col goes from -d+1 to C_k (i.e., row goes from 1 to R_k)
    # 
    # We can parameterize by the diagonal d = R - C.
    # On a given diagonal, a meteor starting at (R_k, C_k) covers positions with
    #   row from (max(1, d+1)) to R_k  if d>=0, equivalently col from 1 to C_k
    #   row from 1 to R_k if d<0, equivalently col from (1-d) to C_k... 
    # 
    # Let me think in terms of a parameter along the diagonal. Let's use row number as the parameter.
    # Meteor k on diagonal d = R_k - C_k occupies rows from max(1, d+1) up to R_k.
    # Wait: the meteor goes from (R_k, C_k) towards (1,1) direction.
    # At time t, it's at (R_k - t, C_k - t). This exists while R_k - t >= 1 and C_k - t >= 1.
    # So t can go from 0 to min(R_k, C_k) - 1.
    # The rows visited are R_k, R_k-1, ..., R_k - (min(R_k,C_k)-1).
    # R_k - (min(R_k,C_k)-1) = R_k - min(R_k,C_k) + 1
    #   if R_k <= C_k: = 1
    #   if R_k > C_k: = R_k - C_k + 1 = d + 1
    # So the interval of rows is [max(1, d+1), R_k].
    # 
    # A camera at cell (r, c) with r - c = d on the same diagonal captures any meteor whose
    # row-interval contains r.
    # 
    # Problem reduces to: for each diagonal d, we have a set of intervals [L_k, R_k] on that diagonal.
    # We need to find minimum number of points to stab all intervals. This is a classic greedy:
    # sort by right endpoint, greedily pick the rightmost point of each unstabbed interval.
    
    # Group meteors by diagonal
    diagonals = defaultdict(list)
    
    for i in range(N):
        R = int(input_data[idx]); idx += 1
        C = int(input_data[idx]); idx += 1
        d = R - C
        # Interval of rows: [max(1, d+1), R]
        L = max(1, d + 1)
        # The interval is [L, R] on this diagonal
        diagonals[d].append((R, L))  # store (right_end, left_end)
    
    total_cameras = 0
    
    for d, intervals in diagonals.items():
        # Classic interval point cover: sort by right endpoint
        intervals.sort()  # sort by R (right endpoint), then by L
        last_placed = -1
        for right_end, left_end in intervals:
            if last_placed < left_end:
                # Need to place a camera at right_end (greedy: as far right as possible)
                last_placed = right_end
                total_cameras += 1
    
    print(total_cameras)

solve()

---

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