BSEX05 - Editorial

Understanding the Problem

We are given:

  1. A set of houses positioned along a 1D straight road.
  2. A set of sprinklers, each with a fixed coverage radius ( r ).
  3. A sprinkler at position ( s ) can cover the range [s - r, s + r].

Our task is to find the minimum coverage radius ( r ) such that all houses are covered by at least one sprinkler.


Key Observations

  1. Sorting Matters

    • Since the problem involves searching for nearest sprinklers, sorting both houses and sprinklers simplifies the search process.
  2. Binary Search on Answer

    • The radius ( r ) can range from 0 (sprinklers must be at the same positions as houses) to a large number (a worst-case scenario where a single sprinkler covers all houses).
    • Instead of iterating through all possible values of ( r ), we can use binary search to efficiently determine the smallest sufficient radius.
  3. Checking if a Radius is Sufficient

    • Given a radius ( r ), we need to verify whether all houses fall within at least one sprinkler’s coverage.
    • We use binary search (lower_bound and upper_bound) to efficiently determine the range covered by each sprinkler.
    • We maintain an extinguished array to efficiently check coverage using a sweep-line technique.

Approach

1. Sorting Houses and Sprinklers

  • Sorting allows for efficient range lookups using binary search (lower_bound and upper_bound).
  • Sorting both arrays ensures that we can efficiently determine coverage.

2. Checking if a Given Radius ( r ) is Valid

To check if a given ( r ) covers all houses:

  1. Use lower_bound and upper_bound to find the range of houses covered by each sprinkler.
  2. Maintain a extinguished array (difference array technique) to mark the start and end of coverage efficiently.
  3. Sweep through the extinguished array to determine if all houses are covered.

3. Binary Search on the Minimum Radius

  1. Set search space:

    • low = 0 (minimum possible radius).
    • high = 10^9 (large upper bound).
  2. Perform Binary Search:

    • Check if mid radius is sufficient using check().
    • If sufficient, try reducing the radius (high = mid - 1).
    • If not sufficient, increase the radius (low = mid + 1).
    • The smallest valid ( r ) found is the answer.

Complexity Analysis

  1. Sorting Houses and Sprinklers

    • O(N log N) + O(M log M)
  2. Checking a Single Radius ( r )

    • Each sprinkler uses O(log N) binary search operations.
    • We iterate over sprinklers, so total complexity is O(M log N).
  3. Binary Search on ( r )

    • Runs in O(log (max_radius)) = O(log 10^9) which is approx O(30)

Final Complexity

O(N log N) + O(M log M) + O(M log N log 10^9)