UVa 10037 - Bridge

Summary:

(A very famous puzzle actually) \(N\) people trying to cross the bridge with one flashlight. Only groups with at most \(2\) people can cross the bridge, and a group has to carry flashlight in order to cross. Each person has a speed, which is the time needed for him to cross the bridge. Furthermore, the time needed for a group to cross the bridge is as fast as the slowest person in that group. Find the minimum time needed to cross everyone off to the other side.

Solution:

There is a greedy "intuition" (or is it? :( ) as follows:

/* Suggested Greedy algo: Incremental construction: The idea is to always bring the first and second slowest to the other side with the help of the first and second fastest say the fastests are A<B and the slowest are X>Y then we have 2 cases: 1. M = (A,X) + (A,0) + (A,Y) + (A,0) M = 2*A + X + Y 2. M' = (A,B) + (A,0) + (X,Y) + (B,0) M' = 2*B + A + X And incrementally choosing the minimum of M and M' at each step. Proof? I dont know */

The proof to the intuition is somewhat more elaborate, by representing the problem as a graph problem.