BRDG - EDITORIAL

Practice

Contest

Author: Ankur Goel

Tester: Ankur Goel

Editorialist: Ankur Goel

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&#8970N/2&#8971−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