PROBLEM LINK:
Author: Sai Sandeep
Tester: Aditya Shah
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
PROBLEM:
Given N sets of people on a straight line consisting of N bridge each with a given maximum number of people that can enter it, find the minimum time in which all the people can reach right end.
QUICK EXPLANATION:
We find the minimum time required for each prefix.
EXPLANATION:
Take a particular prefix of bridges. Let there be S people. Now, as these people travel to reach the right end, they are broken into several groups. How many groups are they broken into ? To calculate that, we need to look at the minimum capacity to the right of the prefix. Let it be C. We have a maximum of ceil (S/C) groups during their course of journey.
Now, the distance they need to cover can be calculated very easily. It is equal to X-xi.
What is the time taken ? It is the distance + Number of groups - 1 . Why ? These groups cannot cross bridges together. First group takes time equal to distance. Rest of the groups just follow. They reach just after the first group, one by one.
Now, the final answer is just take the maximum time over all prefixes.
AUTHOR’S SOLUTION:
Author’s solution can be found here.