Overview

On an \(H \times W\) grid, \(N\) shooting stars move toward the upper-left direction. Each shooting star disappears after a certain amount of time. Find the minimum number of cameras needed to photograph all the shooting stars.

Analysis

Each shooting star moves from its initial position \((R_k, C_k)\) to \((R_k - t, C_k - t)\) at each time step \(t\), and eventually exits the grid and disappears. The key insight is that this movement is along the main diagonal (\(x - y =\) constant).

In other words, shooting star \(k\) only passes through the interval \([R_k - (\min(R_k, C_k) - 1),\ R_k]\) on diagonal \(d = R_k - C_k\). Therefore, shooting stars on the same diagonal can be considered together, and cameras can be placed independently for each diagonal.

Furthermore, to cover all intervals of shooting stars on the same diagonal, an interval scheduling approach can be used. That is, by sorting intervals by their starting points and placing cameras as far to the right as possible when needed, we can cover many intervals efficiently.

Naively scanning the entire grid or trying all combinations would obviously TLE since \(H, W\) can be up to \(10^9\). Additionally, the number of shooting stars can be up to \(2 \times 10^5\), so efficient processing is necessary.

Algorithm

1. From each shooting star’s initial position \((R_k, C_k)\), compute the diagonal ID \(d = R_k - C_k\) and calculate the interval \([low,\ high]\) that the shooting star passes through:

   • \(low = R_k - (\min(R_k, C_k) - 1)\)
   • \(high = R_k\)

2. Group intervals by diagonal.

3. For each diagonal, sort the intervals by starting point and use a greedy method to find the minimum number of cameras (= minimum number of points to cover all intervals):

   • If a new interval starts after the position where the last camera was placed, place a camera at the endpoint of that interval.
   • This allows covering as many subsequent intervals as possible.

4. The sum of cameras across all diagonals is the answer.

Concrete Example

For example, suppose we have the following shooting stars:

Shooting Star	Initial Position \((R, C)\)	Diagonal \(d = R - C\)	Interval \([low, high]\)
1	(3, 2)	1	[2, 3]
2	(4, 3)	1	[2, 4]
3	(2, 4)	-2	[1, 2]

• Diagonal \(d = 1\): Intervals [2,3], [2,4] → Can be covered with 1 camera (camera at position 3)
• Diagonal \(d = -2\): Interval [1,2] → Can be covered with 1 camera

→ Total: 2 cameras

Complexity

• Time complexity: \(O(N \log N)\)
  (Dominated by sorting intervals for each diagonal)
• Space complexity: \(O(N)\)
  (Storing shooting star information and interval lists for each diagonal)

Implementation Notes

• Correctly computing each shooting star’s interval (especially edge cases)

• The crucial part is classifying intervals by diagonal, sorting them, and processing greedily

• Manage last_selected as “the last position where a camera was placed” and determine whether the next interval is already covered

• In Python, using sys.stdin.read() enables fast input processing

  Source Code

import sys
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    H = int(data[0])
    W = int(data[1])
    N = int(data[2])
    
    meteors = []
    for i in range(N):
        r = int(data[3 + 2*i])
        c = int(data[4 + 2*i])
        # 各流れ星の初期位置 (r, c)
        # この流れ星のパスは (r-t, c-t) for t=0 to min(r,c)-1
        # これは対角線に沿ったパスで、全ての点は同じ (r-c) の値を持つ
        diag = r - c  # diagonal identifier
        start_t = 0
        end_t = min(r, c) - 1
        # 実際の座標範囲: (r - t, c - t) で t = 0 to end_t
        # つまり、行は r から r - end_t まで、列は c から c - end_t まで
        # 座標範囲は [r - end_t, r] x [c - end_t, c]
        # しかし、これは同じ対角線上の連続した区間
        
        # より正確には、(x, y) が対角線 d 上にあるとは x - y = d
        # 各流れ星のパスは対角線 (r - c) 上の区間 [(r - end_t, c - end_t), (r, c)]
        # すなわち (r - end_t) から r までの行について (row, row - d) を通る
        
        # したがって、各流れ星は対角線 d = r - c 上のある区間に対応する
        # この区間は [r - end_t, r] = [r - (min(r,c) - 1), r]
        low = r - (min(r, c) - 1)
        high = r
        meteors.append((diag, low, high))
        
    # 対角線ごとにグループ分け
    from collections import defaultdict
    diag_to_intervals = defaultdict(list)
    for d, low, high in meteors:
        diag_to_intervals[d].append((low, high))
        
    count = 0
    # 各対角線について、区間スケジューリング問題を解く
    # 最小区間被覆ではなく、区間を選んで全区間をカバーする最小選択 -> これは区間スケジューリング
    # すべての区間をカバーする最小の点の数 = 最小ヒットセット = 区間グラフの最大独立集合の補集合？
    # 実際には、各区間をカバーする点（カメラの設置位置）の最小数を求める問題
    # これは区間グラフにおける最小クリーク被覆 = 最大独立集合（一般にはNP-hardだが区間グラフでは多項式）
    # 正確には、最小の点の集合Sで、各区間Iに対して s in S かつ s in I なるものが存在するようなSの最小サイズ
    # => 区間の始点でソートして貪欲法
    
    for intervals in diag_to_intervals.values():
        # intervals: list of (low, high)
        intervals.sort()  # low順にソート
        if not intervals:
            continue
        res = 0
        last_selected = -float('inf')
        for low, high in intervals:
            if last_selected < low:
                # 新しいカメラが必要
                res += 1
                last_selected = high  # 最も右にカメラを設置することで、今後来る区間もカバーしやすい
            else:
                # すでにカバーされているが、より右にカメラを設置することで今後をカバーできるようにする？
                # 貪欲に最後尾に配置するのが最適
                last_selected = min(last_selected, high)
        count += res
        
    print(count)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.