The Bridge to Home

This post is in reference to SPOJ 17660 The Bridge to Home WAYHOME.

You have a group of people on one side of a river, and it may only be crossed by a bridge; the bridge can take 1 or 2 at a time. All bridge-crossers must carry the lone flashlight, meaning each trip across must alternate — flashlight goes one way then back. Each person has a given “time to cross”, and two people crossing takes the longest time of the two. What is the minimum time (T) to cross?

e.g. You have times-to-cross of delim{lbrace}{3, 5, 10}{rbrace}. So a solution is as follows:

3 & 10 across = 10
3 back = 3
3 & 5 across = 5
T = 18

The algorithm has several cases as follows:

1. Remaining <= 2: simply cross

2. Remaining == 3: finish up, lo & mid, lo back, lo & hi

3. Remaining > 3: shuttle two highest
lo = lowest
lo2 = 2nd lowest
hi2 = 2nd highest
hi = highest

N.B. Take the best of the two below. Using max below for clarity.

3a. lo chauffeurs hi across, comes back and does the same for hi2: max(lo, hi) + lo + max(lo, hi2) + lo

3b. lo chauffeurs lo2 and lo returns, hi and hi2 cross and lo2 (aha!) returns: max(lo, lo2) + lo + max(hi, hi2) + lo2

My solution is in git and below:

Leave a Reply

Your email address will not be published. Required fields are marked *