## 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{C_{0}, C_{1},…,C_{⌊N/2⌋−1}},

with

C_{k} = (N − 2 − k)t_{1} + (2k + 1)t_{2} + Σ t_{i(3 to n)} −Σ

t_{N}+1−2_{i(1 to k)}. (1)

For example, when N = 6, this amounts to

min{4t_{1} + t_{2} + t_{3} + t_{4} + t_{5} + t_{6}, 3t_{1 }+ 3t_{2} + t_{3} + t_{4} + t_{6}, 2t_{1} + 4t_{2} + t_{4} + t_{6}}.

The difference between C_{k−1} and C_{k} is 2t_{2 − t1 − tN−2k+1.}

Thus, the optimal value of k

can be determined easily by locating the value 2t_{2} − t_{1} in the sorted list of t_{i}’s.

## Author’s Solution

Author’s solution can be found here