For problem Ferry.
Is there a bug in the official solution? Unless I’ve made a mistake in my calculations, my testing on udebug suggests so. (See UVa1012 and LA2477 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?
- 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
- 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.
- 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.
