1167HardDynamic ProgrammingHeuristic SearchA* Search

Driving the Trolley to the Mark

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 trolley stands at position 0 on a rail, facing forwards with a speed of 1.

Two controls are available:

Push moves the trolley forward by its speed, then doubles that speed. Facing backwards the speed is negative, so the trolley moves backwards and the speed doubles in size.
Turn sets the speed to 1 when it was negative and to -1 when it was positive. The trolley does not move.

Return the fewest presses needed to bring the trolley to position target.

Examples

Example 1

Input: target = 1
Output: 1

One push carries the trolley one place and it has arrived.

Example 2

Input: target = 7
Output: 3

Three pushes carry the trolley 1, then 2, then 4 places, which is exactly seven.

Example 3

Input: target = 4
Output: 5

Push twice to reach 3, then turn twice to bring the speed back to one without moving, and push once more to land on 4. A third push would have overshot to 7.

Constraints

1 <= target <= 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 racecar(target: int) -> int:

Java

public int racecar(int target)

The intended approach

Time O(target log target) over the states.Space O(target log target) for the states already reached.

Where the trolley can go next depends only on where it stands and how fast it is going, so a position paired with a speed is the whole state of affairs. Every press costs the same, so walking outwards from the starting state a layer at a time settles the fewest presses to reach each state, and the first time the target position turns up, whatever the speed, the count is the answer. The states have to be fenced in or the walk never ends. Overshooting past twice the target, or backing up as far behind the start, is never worth it: from out there the trolley must turn and cover the whole distance again, which costs more than a run that stayed inside. Speeds look after themselves, since a push from inside the fence to inside the fence bounds the speed too. Turning twice in a row simply resets the speed to one and costs two presses, which the walk discovers on its own rather than needing a rule.

Pythonentry point: racecar

def racecar(target):
    from collections import deque
    fence = 2 * target + 1
    seen = set()
    seen.add((0, 1))
    queue = deque([(0, 1, 0)])
    while queue:
        pos, speed, steps = queue.popleft()
        if pos == target:
            return steps
        npos = pos + speed
        nspeed = speed * 2
        if -fence <= npos <= fence and (npos, nspeed) not in seen:
            seen.add((npos, nspeed))
            queue.append((npos, nspeed, steps + 1))
        turned = 1 if speed < 0 else -1
        if (pos, turned) not in seen:
            seen.add((pos, turned))
            queue.append((pos, turned, steps + 1))
    return -1

The obvious version

Work the distance out from the shape of the runs instead of walking states. A run of `k` pushes from rest covers two to the `k` less one. Either that lands exactly on the distance, or the shortest way is to overshoot with `k` pushes, turn, and cover the surplus, or to stop one push short, turn, back up with some number of pushes, turn again, and cover what remains. Taking the best of those over every number of backing-up pushes, and remembering the answers for distances already worked out, settles it.

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_racecar(target):
    known = {}

    def solve(t):
        if t == 0:
            return 0
        if t in known:
            return known[t]
        known[t] = 1 << 30
        k = 0
        while (1 << k) - 1 < t:
            k += 1
        if (1 << k) - 1 == t:
            known[t] = k
            return k
        best = k + 1 + solve((1 << k) - 1 - t)
        short = t - ((1 << (k - 1)) - 1)
        for j in range(k - 1):
            cost = (k - 1) + 1 + j + 1 + solve(short + (1 << j) - 1)
            if cost < best:
                best = cost
        known[t] = best
        return best

    return solve(target)

How this problem was checked

Reference solution executed against 15 test cases — 15 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