The general boat river problem is that, you have a river and a boat, the boat can carry atmost 2 people at once. The objective is for all people to cross over to the other side of the river.
Each person limits the time it takes to cross the river when that person is in it. Example: if a A has a limit of 1 and B has a limit of 2 and they cross the river while in the same boat then it takes 2 minutes for them to cross i.e. max(A,B)
Now in the general problem some small number of fixed limits are given, lets say 1,2,5,6, and the minimum time for every person to cross the river is asked. In this case the answer is 13, first 1&2 go, then 1 comes back, then 5&6 go, then 2 comes back, then 1&2 go to the other side, now every one has crossed.
But what if an array of limits is given ? lets say of size 10? or 20? or 50?, how do you solve this then ? What is the complexity to solve it programatically ?
EDIT: not necessarily optimal
Consider the case 3 10 10 10. Your algorithm will give 43 as an answer. But the correct strategy here is to repeat the step "move 3 and 10 to the other side, return 3 back if necessary" three times, the total time is 36.
The correct approach to this problem is as follows. We don't use one way to move people, each time we choose the best of two ways.
First way is described by you:
The other way is
repeated two times, with biggest possible pis. Also consider some corner cases, e. g. n = 1 and n = 2.
BTW, such problem did exist on Polish OI, you can submit it on Szkopyl.
I do not quite understand, could you please explain in a little bit more detail ? gepardo
Sorry for the late reply.
Let's sort the people in non-decreasing order of time needed to cross the river and denote them as p0, p1, ..., pn - 1.
Denote F(x, y, z) as the following operation: people px and py go to the other side of the river, and pz returns back. If nobody returns back, z = - 1.
For n = 1 and n = 2 the problem is trivial to solve.
For n = 3 it's always optimal to do F(0, 2, 0), then F(0, 1, - 1).
Now consider n > 3. We should move pn - 2 and pn - 1 to the other side, then solve the problem for smaller n. Consider two ways of doing it and take the most optimal one:
First is: F(0, n - 2, 0), F(0, n - 1, 0).
Second is: F(0, 1, 0), F(n - 2, n - 1, 1).
So, the problem is solvable in O(n).
Thank you very very much, this is simple enough for me to understand !
I love how easy it is to get answers to lesser known questions like this in the codeforces community, thanks codeforces and gepardo !
Yeah this is right. I tried to think about a case like this but didn't find one.
This is awesome.
Problem to Test Code