0757MediumArrayMath

Drone Race To The Beacon

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A courier drone sits on the depot at (0, 0) of an unbounded integer grid. A beacon waits at beacon = [bx, by], and each entry of patrols gives the starting cell of one patrol unit.

Time advances in turns. On every turn the drone and every patrol each either hold still or step one cell north, south, east or west, all at the same moment. The patrols are told the drone's whole route in advance and move to stop it.

The drone is intercepted if a patrol shares its cell at any moment, counting the turn on which the drone first stands on the beacon: a patrol arriving there on that same turn still counts as an interception. Once the drone has stood on the beacon without being intercepted it is safe and later turns do not matter.

Return true if the drone has a route that gets it onto the beacon without being intercepted, and false otherwise. The beacon may sit on the depot, and several patrols may share a starting cell.

Examples

Example 1

Input: patrols = [[-3, 4], [7, -2]], beacon = [-1, -1]
Output: true

The drone can step to (-1, 0) on turn 1 and onto the beacon on turn 2. Neither patrol can be standing on (-1, 0) by turn 1 or on (-1, -1) by turn 2, so nothing intercepts it.

Example 2

Input: patrols = [[6, 1]], beacon = [3, 3]
Output: false

The patrol can walk onto the beacon and hold still there before the drone is able to stand on it, so every route the drone might take ends in an interception.

Example 3

Input: patrols = [[1, 1], [9, 9]], beacon = [0, 3]
Output: false

The patrol starting at (1, 1) can be standing on the beacon on the same turn the drone first reaches it, and arriving together still counts as an interception. The patrol at (9, 9) is far away and never matters.

Constraints

1 <= patrols.length <= 100
patrols[i].length == 2
-10^4 <= patrols[i][j] <= 10^4
beacon.length == 2
-10^4 <= beacon[i] <= 10^4

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def can_reach_beacon(patrols: list[list[int]], beacon: list[int]) -> bool:

Java

public boolean canReachBeacon(int[][] patrols, int[] beacon)

The intended approach

Time O(p) for p patrols: one pass over the list.Space O(1).

Because a patrol may hold still, the beacon is the only cell worth contesting: whoever can be standing there no later than the drone decides the outcome. So compare the grid-move count from the depot to the beacon against the grid-move count from each patrol's start to the beacon, and refuse as soon as one patrol's count is not larger.

Pythonentry point: can_reach_beacon

def can_reach_beacon(patrols, beacon):
    # Time O(p) for p patrols, space O(1).
    bx, by = beacon
    own = abs(bx) + abs(by)
    for gx, gy in patrols:
        if abs(gx - bx) + abs(gy - by) <= own:
            return False
    return True

The obvious version

Search the lattice route by route. A patrol can be standing on a cell on turn t exactly when it needs at most t moves to get there, so expand the drone's reachable cells turn by turn and drop any cell a patrol could already be occupying. The drone escapes if the beacon survives that filter. Costs work proportional to the area spanned by the input.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_can_reach_beacon(patrols, beacon):
    target = (beacon[0], beacon[1])
    pts = [(0, 0), target] + [(g[0], g[1]) for g in patrols]
    lox = min(p[0] for p in pts) - 2
    hix = max(p[0] for p in pts) + 2
    loy = min(p[1] for p in pts) - 2
    hiy = max(p[1] for p in pts) + 2

    def free(cell, turn):
        for gx, gy in patrols:
            if abs(gx - cell[0]) + abs(gy - cell[1]) <= turn:
                return False
        return True

    start = (0, 0)
    if not free(start, 0):
        return False
    if start == target:
        return True
    seen = {start}
    frontier = [start]
    turn = 0
    while frontier:
        turn += 1
        nxt = []
        for x, y in frontier:
            for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                cell = (x + dx, y + dy)
                if not (lox <= cell[0] <= hix and loy <= cell[1] <= hiy):
                    continue
                if cell in seen:
                    continue
                seen.add(cell)
                if not free(cell, turn):
                    continue
                if cell == target:
                    return True
                nxt.append(cell)
        frontier = nxt
    return False

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in