1 / 3
Jul 2020

For problem Ferry2.

Is there a bug in the official solution? Unless I’ve made a mistake in my calculations, my testing on udebug suggests so. (See UVa10125 and LA24773 if you want to try for yourself.).

Consider this test case

16
Begynnelse Brygge road 37
Brygge Bestemmelse ferry 15 1 0
Bestemmelse Veiskillet road 20
Veiskillet Overfarten ferry 20 2 5 25
Overfarten Ferje ferry 30 1 56
Ferje Grusvei road 25
Grusvei Havneby ferry 30 1 1
Havneby Slutt ferry 50 1 3
Slutt Bomvei road 7
Bomvei Leknes ferry 15 1 0
Leknes Tromso road 80
Tromso Bodo ferry 30 3 10 30 50
Bodo Borkenes road 55
Borkenes Harstad ferry 20 2 5 25
Harstad Sortland road 25
Sortland Oslo ferry 12 1 45

The answer given by both official solutions on udebug is:

Test Case 1: 09:57:00 64.00

My solution (which gets WA (edit: now AC)) gives:

Test Case 1: 09:57:00 75.00

These are my calculations. Have I made a mistake?

  1. Driving at the 80 kph all the time. This gives the shortest possible journey time, but may not be the optimum speed.
From         To             Start    Next Ferry    Wait    Travel Time  Finish
Begynnelse   Brygge        00:00:00                         00:27:45   00:27:45
Brygge       Bestemmelse   00:27:45   01:00:00   00:32:15   00:15:00   01:15:00
Bestemmelse  Veiskillet    01:15:00                         00:15:00   01:30:00
Veiskillet   Overfarten    01:30:00   02:05:00   00:35:00   00:20:00   02:25:00
Overfarten   Ferje         02:25:00   02:56:00   00:31:00   00:30:00   03:26:00
Ferje        Grusvei       03:26:00                         00:18:45   03:44:45
Grusvei      Havneby       03:44:45   04:01:00   00:16:15   00:30:00   04:31:00
Havneby      Slutt         04:31:00   05:03:00   00:32:00   00:50:00   05:53:00
Slutt        Bomvei        05:53:00                         00:05:15   05:58:15
Bomvei       Leknes        05:58:15   06:00:00   00:01:45   00:15:00   06:15:00
Leknes       Tromso        06:15:00                         01:00:00   07:15:00
Tromso       Bodo          07:15:00   07:30:00   00:15:00   00:30:00   08:00:00
Bodo         Borkenes      08:00:00                         00:41:15   08:41:15
Borkenes     Harstad       08:41:15   09:05:00   00:23:45   00:20:00   09:25:00
Harstad      Sortland      09:25:00                         00:18:45   09:43:45
Sortland     Oslo          09:43:45   09:45:00   00:01:15   00:12:00   09:57:00
  1. Driving no faster than 64 kph, i.e. the answer given by the official solution.
From         To             Start    Next Ferry    Wait    Travel Time  Finish
Begynnelse   Brygge        00:00:00                         00:34:41   00:34:41
Brygge       Bestemmelse   00:34:41   01:00:00   00:25:19   00:15:00   01:15:00
Bestemmelse  Veiskillet    01:15:00                         00:18:45   01:33:45
Veiskillet   Overfarten    01:33:45   02:05:00   00:31:15   00:20:00   02:25:00
Overfarten   Ferje         02:25:00   02:56:00   00:31:00   00:30:00   03:26:00
Ferje        Grusvei       03:26:00                         00:23:26   03:49:26
Grusvei      Havneby       03:49:26   04:01:00   00:11:34   00:30:00   04:31:00
Havneby      Slutt         04:31:00   05:03:00   00:32:00   00:50:00   05:53:00
Slutt        Bomvei        05:53:00                         00:06:34   05:59:34
Bomvei       Leknes        05:59:34   06:00:00   00:00:26   00:15:00   06:15:00
Leknes       Tromso        06:15:00                         01:15:00   07:30:00
Tromso       Bodo          07:30:00   07:30:00   00:00:00   00:30:00   08:00:00
Bodo         Borkenes      08:00:00                         00:51:34   08:51:34
Borkenes     Harstad       08:51:34   09:05:00   00:13:26   00:20:00   09:25:00
Harstad      Sortland      09:25:00                         00:23:26   09:48:26
Sortland     Oslo          09:48:26   10:45:00   00:56:34   00:12:00   10:57:00

The slower driving speed means that the ferry sailing at 09:45 is missed by 3 minutes 26 seconds, and so causes an hour’s delay.

  1. Driving no faster than 75 kph, i.e. my answer.
From         To             Start    Next Ferry    Wait    Travel Time  Finish
Begynnelse   Brygge        00:00:00                         00:29:36   00:29:36
Brygge       Bestemmelse   00:29:36   01:00:00   00:30:24   00:15:00   01:15:00
Bestemmelse  Veiskillet    01:15:00                         00:16:00   01:31:00
Veiskillet   Overfarten    01:31:00   02:05:00   00:34:00   00:20:00   02:25:00
Overfarten   Ferje         02:25:00   02:56:00   00:31:00   00:30:00   03:26:00
Ferje        Grusvei       03:26:00                         00:20:00   03:46:00
Grusvei      Havneby       03:46:00   04:01:00   00:15:00   00:30:00   04:31:00
Havneby      Slutt         04:31:00   05:03:00   00:32:00   00:50:00   05:53:00
Slutt        Bomvei        05:53:00                         00:05:36   05:58:36
Bomvei       Leknes        05:58:36   06:00:00   00:01:24   00:15:00   06:15:00
Leknes       Tromso        06:15:00                         01:04:00   07:19:00
Tromso       Bodo          07:19:00   07:30:00   00:11:00   00:30:00   08:00:00
Bodo         Borkenes      08:00:00                         00:44:00   08:44:00
Borkenes     Harstad       08:44:00   09:05:00   00:21:00   00:20:00   09:25:00
Harstad      Sortland      09:25:00                         00:20:00   09:45:00
Sortland     Oslo          09:45:00   09:45:00   00:00:00   00:12:00   09:57:00

Any ideas?

edit: I’ve discovered the solutions on uDebug are not official solutions provided by the problem setter. They’ve mostly been donated by someone who got AC.

  • created

    Jul '20
  • last reply

    Jul '20
  • 2

    replies

  • 721

    views

  • 2

    users

  • 3

    links

For any readers, the problem setter says:

Thank you, you are right. The uDebug’s solutions were updated.