Overview

This problem asks us to minimize the number of times \(K\) a speaker is played, after optimally choosing the speaker’s placement position, so that sound reaches all booths lined up in a straight line. We solve it using binary search on the answer \(K\) and interval intersection checking for each \(K\).

Analysis

Key Insight: Fixing \(K\) turns the condition into interval constraints

When playing \(K\) times, the condition for sound to reach booth \(i\) is:

\[K \times (V - |X_i - P|) \geq D_i\]

Rearranging this:

\[|X_i - P| \leq V - \lceil D_i / K \rceil\]

Letting \(r_i = V - \lceil D_i / K \rceil\), the condition that \(P\) must satisfy is:

\[X_i - r_i \leq P \leq X_i + r_i\]

In other words, each booth defines an interval saying “I want \(P\) to be within this range.” To satisfy the conditions for all booths simultaneously, we just need to verify that the intersection of all intervals is non-empty.

Problem with the naive approach

Trying all possible values of \(P\) won’t work since coordinates can be up to \(10^9\). Also, \(K\) can be up to \(10^{18}\), making exhaustive search impossible.

Solution: Monotonicity with respect to \(K\)

As \(K\) increases, \(\lceil D_i / K \rceil\) decreases, making \(r_i\) larger and thus widening the intervals. Therefore, the feasibility check “is \(K\) feasible” is monotone (always Yes from some value onward), and binary search can be applied.

Algorithm

1. Impossibility check: If \(V = 0\), sound cannot reach anywhere, so output -1. When \(K \to \infty\), we get \(r_i = V - 1\), so if the intersection of intervals \([X_i - (V-1),\, X_i + (V-1)]\) is empty, output -1.

2. Binary search: Binary search over the range \([1,\, \max(D_i)]\) for \(K\).

3. Feasibility function feasible(K):

   • For each booth, compute \(r_i = V - \lceil D_i / K \rceil\)
   • If \(r_i < 0\), immediately return False
   • Compute the intersection of all intervals \([X_i - r_i,\, X_i + r_i]\); return True if non-empty
   • Intersection computation: check whether the maximum of left endpoints \(\leq\) the minimum of right endpoints

Complexity

• Time complexity: \(O(N \log(\max D_i))\)
  • Binary search runs \(O(\log(\max D_i))\) times, each check takes \(O(N)\)
  • Since \(\max D_i \leq 10^{18}\), \(\log\) is about \(60\) iterations
• Space complexity: \(O(N)\)

Implementation Notes

• Integer ceiling division: \(\lceil D_i / K \rceil\) is computed as (D_i + K - 1) // K.

• Integer coordinates guaranteed: Since \(X_i\), \(V\), and \(K\) are all integers, \(r_i\) is also an integer. Interval endpoints are integers, so if \(lo \leq hi\), an integer \(P\) always exists.

• Setting the upper bound: The worst case is when a booth is at distance \(V-1\) and only receives volume \(1\) each time, requiring \(K = \max(D_i)\) plays. This serves as a safe upper bound.

• Overflow prevention: Since \(D_i\) can be up to \(10^{18}\), Python’s arbitrary-precision integers can be used directly, which is an advantage.

  Source Code

import sys
from math import ceil

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    V = int(input_data[idx]); idx += 1
    
    booths = []
    for i in range(N):
        X = int(input_data[idx]); idx += 1
        D = int(input_data[idx]); idx += 1
        booths.append((X, D))
    
    # For a given K, we need to find an integer position P such that for all booths i:
    # K * max(V - |X_i - P|, 0) >= D_i
    # This means: V - |X_i - P| >= ceil(D_i / K)  (when ceil(D_i/K) > V, impossible)
    # => |X_i - P| <= V - ceil(D_i / K)
    # Let r_i = V - ceil(D_i / K). If r_i < 0 for any i, then K is not enough.
    # Otherwise, P must satisfy: X_i - r_i <= P <= X_i + r_i for all i.
    # So P must be in [max(X_i - r_i), min(X_i + r_i)] and there must be an integer in this range.
    
    def feasible(K):
        lo = -10**18
        hi = 10**18
        for X, D in booths:
            needed = (D + K - 1) // K  # ceil(D/K)
            r = V - needed
            if r < 0:
                return False
            lo = max(lo, X - r)
            hi = min(hi, X + r)
            if lo > hi:
                return False
        # Check if there's an integer in [lo, hi]
        # lo and hi are integers (since X, r are integers), so just check lo <= hi
        return lo <= hi
    
    # First check if it's possible at all. 
    # The maximum K we'd ever need: for each booth, we need K * max(V - |X_i - P|, 0) >= D_i.
    # The best case for a booth is when |X_i - P| = 0, giving K * V >= D_i, so K >= ceil(D_i / V).
    # But we also need all booths within distance < V from P.
    
    # Check feasibility: even with K = infinity, we need all booths reachable from some P.
    # With K->inf, ceil(D_i/K) -> 1 (for D_i >= 1), so r_i = V - 1.
    # We need intersection of [X_i - (V-1), X_i + (V-1)] to be non-empty.
    # Actually for K large enough, ceil(D_i/K) = 1 (when K >= D_i), r_i = V-1.
    # But we should also consider: if V = 0, then no sound reaches anywhere (unless D_i = 0, but D_i >= 1).
    
    if V == 0:
        print(-1)
        return
    
    # Check if there exists any P that can reach all booths (with enough K).
    # With K->infinity, we need r_i = V - 1 >= 0, which is true since V >= 1.
    # And intersection of [X_i - (V-1), X_i + (V-1)] must be non-empty.
    lo_check = -10**18
    hi_check = 10**18
    for X, D in booths:
        lo_check = max(lo_check, X - (V - 1))
        hi_check = min(hi_check, X + (V - 1))
    
    if lo_check > hi_check:
        print(-1)
        return
    
    # Binary search on K
    # Lower bound: 1
    # Upper bound: max(ceil(D_i / 1)) but that's just max(D_i). 
    # Actually we need tighter: upper bound is when P is optimal.
    # Safe upper bound: for each booth, worst case K * 1 >= D_i (if booth is at distance V-1), so K = max(D_i).
    
    max_D = max(D for _, D in booths)
    
    left, right = 1, max_D
    
    # Check if K=max_D works (it should if feasibility passed)
    if not feasible(right):
        # Shouldn't happen, but just in case
        print(-1)
        return
    
    while left < right:
        mid = (left + right) // 2
        if feasible(mid):
            right = mid
        else:
            left = mid + 1
    
    print(left)

solve()

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