prac64's blog

An extension of the boat-river problem, what is the general answer ?
By prac64, history, 6 years ago, In English

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 ?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

EDIT: not necessarily optimal

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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:

    1. Send 1 and 2 to the other side
    2. Send 1 back
    3. Send n and n  -  1 to the other side
    4. Send 2 back
    5. Decrement n by 2, and repeat

    The other way is

    first we ferry 1 and some person pi over, and then 1 back

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I do not quite understand, could you please explain in a little bit more detail ? gepardo

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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).

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          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 !

          → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Yeah this is right. I tried to think about a case like this but didn't find one.

      → Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

This is awesome.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem to Test Code

→ Reply