Problem Links
Author: Ankur Goel
Tester: Ankur Goel
Editorialist: Ankur Goel
Difficulty
Medium
Problem
N people begin on the same side of a bridge. You must help them across to the other side. It is night. There is one flashlight. A maximum of two people can cross at a time. Any party who crosses, either one or two people, must have the flashlight to see. The flashlight must be walked back and forth, it cannot be thrown, etc. Each person walks at a different speed. A pair must walk together at the rate of the slower person’s pace, based on this information,Find the minimum time required for all people to cross the bridge
Explanation
The minimum time to cross the bridge is
min{C0, C1,…,C⌊N/2⌋−1},
with
Ck = (N − 2 − k)t1 + (2k + 1)t2 + Σ ti(3 to n) −Σ
tN+1−2i(1 to k). (1)
For example, when N = 6, this amounts to
min{4t1 + t2 + t3 + t4 + t5 + t6, 3t1 + 3t2 + t3 + t4 + t6, 2t1 + 4t2 + t4 + t6}.
The difference between Ck−1 and Ck is 2t2 − t1 − tN−2k+1.
Thus, the optimal value of k
can be determined easily by locating the value 2t2 − t1 in the sorted list of ti’s.
Author’s Solution
Author’s solution can be found here