Bridge Crossing (Torch)

Problem. $n$ people must cross a bridge at night. They have one torch, the bridge holds at most two people at a time, and the torch must accompany every crossing. Person $i$ takes $t_i$ minutes; a pair moves at the slower person’s speed. Minimise the total time.

The classic instance: times $\{1,2,5,10\}$. The naive “fastest person shuttles everyone” gives 19 minutes. The optimum is 17.

The optimal solution for $\{1,2,5,10\}$

1,2 cross      -> 2      (1 and 2 on the far side)
1   returns    -> 1
5,10 cross     -> 10     <- send the two SLOWEST together
2   returns    -> 2
1,2 cross      -> 2
                 ----
                   17

The insight: pair the two slowest people together, so the second-slowest crossing is absorbed into the slowest one, instead of paying for it separately.

The greedy — $O(n\log n)$

Sort ascending. Repeatedly reduce the problem to the $n-2$ fastest, choosing the cheaper of two strategies for moving the two slowest across:

Strategy	Cost
A — fastest shuttles: $t_0+t_{n-1}$, then $t_0+t_{n-2}$	$2t_0+t_{n-1}+t_{n-2}$
B — two fastest ferry: $t_1$, $t_0$, $t_{n-1}$, $t_1$	$t_0+2t_1+t_{n-1}$

long long bridgeCrossing(vector<int> t) {
    sort(t.begin(), t.end());
    int n = t.size();
    long long total = 0;
    int i = n - 1;
    while (i >= 3) {
        total += min((long long)t[0] + 2LL * t[1] + t[i],       // strategy B
                     2LL * t[0] + t[i] + t[i-1]);               // strategy A
        i -= 2;
    }
    if (i == 2) total += t[0] + t[1] + t[2];                    // three left
    else if (i == 1) total += t[1];                             // two left
    else total += t[0];                                         // one left
    return total;
}

$O(n\log n)$, dominated by the sort.

Why only these two strategies

Any optimal schedule can be rearranged so that:

1. the two slowest cross together (otherwise you pay $t_{n-1}$ and $t_{n-2}$ on separate trips);
2. only the fastest two ever return (a slower returner is never better);
3. the problem then reduces to the remaining $n-2$ people.

That reduction is an exchange argument, and it collapses an exponential search into a two-way choice per pair.

The DP alternative

For safety, or for variants where the greedy is unproven, a bitmask DP over “who has crossed” plus the torch’s side is $O(2^n{n}^2)$ — fine for $n\le 20$ and impossible to get wrong.

// dp[mask][side] = minimum time with `mask` on the far bank and the torch on `side`

Use it to verify the greedy on random small inputs. That combination — write both, stress test — is the reliable way to trust a greedy you have only half-proved. See Stress Testing.

Variants

Variant	Note
Boat holds $k>2$	greedy generalises but is harder to prove; DP is safer
Different return costs	DP
Some people cannot cross together	DP with feasibility masks
Minimise the number of crossings	$2n-3$ for $n\ge 2$
Multiple torches	changes the structure entirely
Torch has a limited lifetime	add a feasibility check

The family it belongs to

Puzzle	Structure
Bridge and torch	pair up, one returns
Wolf, goat, cabbage	constraint on unattended items
Missionaries and cannibals	counting constraint per bank
Jealous husbands	pairing constraint
River crossing with a raft of capacity $k$	general BFS

All are state-space searches (BFS or DP over subsets); the bridge problem is unusual in also having a clean greedy, which is what makes it worth studying.

Why it is worth knowing

It is a compact example of a counter-intuitive greedy that is nevertheless provable: sending the two slowest together — wasting the fastest person’s trip — beats the obvious shuttle strategy. Whenever an obvious greedy feels forced, it is worth asking whether pairing the two worst items is better than handling them separately; the same idea appears in Huffman coding and in several scheduling problems.

See also: Exchange Arguments · Wolf, Goat and Cabbage · Bitmask DP