Overview

This problem asks whether you can travel from coordinate \(0\) to coordinate \(L\) on a number line by staying only within the Wi-Fi router coverage areas (intervals). This is known as the “interval covering problem” and can be solved efficiently using a greedy algorithm.

Analysis

Problem Reformulation

Each router covers the interval \([X_i - R_i, X_i + R_i]\). The problem reduces to: “Can we continuously cover \([0, L]\) using these intervals?”

Issues with a Naive Approach

Trying all combinations of intervals would require checking \(2^N\) possibilities, which is too slow for large \(N\) (TLE).

Key Insight

A greedy approach works. From the current position, it is optimal to select the interval that extends furthest to the right among all reachable intervals.

This works because choosing an interval that reaches further right never reduces (and may even increase) the options for the next interval selection.

Concrete Example

For \(L = 10\) with intervals \([0, 3], [2, 6], [5, 10]\): 1. Start at coordinate \(0\). The interval \([0, 3]\) containing \(0\) allows reaching coordinate \(3\) 2. Among intervals starting at coordinate \(3\) or earlier, \([2, 6]\) extends furthest right. We can reach coordinate \(6\) 3. Among intervals starting at coordinate \(6\) or earlier, \([5, 10]\) extends furthest right. We can reach coordinate \(10\) 4. Reached the goal \(L = 10\)! → Yes

Algorithm

1. Compute the coverage interval \([X_i - R_i, X_i + R_i]\) for each router
2. Sort intervals by their left endpoints
3. Check if coordinate \(0\) is covered (if not, output No)
4. Extend the right endpoint greedily:
   • Initialize current_pos (the rightmost reachable position) to \(0\)
   • Among intervals starting at current_pos or earlier, select the one that extends furthest right
   • Set the right endpoint of that interval as the new current_pos
   • Repeat until current_pos >= L
5. If no progress can be made, output No; if \(L\) is reached, output Yes

Complexity

• Time Complexity: \(O(N \log N)\)
  • Sorting takes \(O(N \log N)\)
  • The greedy loop examines each interval at most once, so it takes \(O(N)\)
• Space Complexity: \(O(N)\)
  • \(O(N)\) for storing the intervals in an array

Implementation Notes

1. Sort by left endpoint of intervals: This allows efficient sequential processing of “intervals starting at or before the current position”

2. Reuse index i: By managing i outside the loop and never revisiting intervals, we achieve overall \(O(N)\) complexity

3. Detecting when no progress is possible: When best_right == current_pos, no interval can extend our position, so we output No

4. Check coverage of coordinate \(0\): If the starting point is not within any coverage area, movement cannot begin at all, so this must be verified first

Source Code

def solve():
    N, L = map(int, input().split())
    
    intervals = []
    for _ in range(N):
        x, r = map(int, input().split())
        left = x - r
        right = x + r
        intervals.append((left, right))
    
    # Sort intervals by left endpoint
    intervals.sort()
    
    # Check if coordinate 0 is covered
    # Track the rightmost reachable position
    current_right = 0
    
    # Check if there is an interval covering coordinate 0
    covers_start = False
    for left, right in intervals:
        if left <= 0 <= right:
            covers_start = True
            break
    
    if not covers_start:
        print("No")
        return
    
    # Extend the rightmost position greedily
    # Among intervals reachable from current position, choose the one extending furthest right
    current_pos = 0
    i = 0
    
    while current_pos < L:
        # Find the interval starting at current_pos or earlier that extends furthest right
        best_right = current_pos
        
        while i < N and intervals[i][0] <= current_pos:
            best_right = max(best_right, intervals[i][1])
            i += 1
        
        # If no progress was made
        if best_right == current_pos:
            print("No")
            return
        
        current_pos = best_right
    
    # If current_pos >= L, the destination is reachable
    print("Yes")

solve()

---

This editorial was generated by claude4.5opus.