The problem
Stations lie along a line at positions x[0] < x[1] < …. A train starts at the first station and ends at the last. It may stop at any stations in between. Each run from one stop to the next stop, i to j, costs (x[j] − x[i]) ** 2 + c. Find the cheapest total.
cheapest_trip([0, 1, 2], 1) # 4: stop at 1
cheapest_trip([1, 2, 3, 4, 5], 6) # 20: stop at 3
Limits
- Up to 150,000 stations; positions up to about 10⁹ (a thousand million); c up to 10¹² (a million million).
- Trying every earlier stop for every station is about 10¹⁰ steps (ten thousand million). Aim for O(n).
- Answers can be near 10¹⁸. Keep to whole numbers.
Builds on ADDP-6 DP optimisations.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
11 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | One station | Not run | |
| 2 | Two stations | Not run | |
| 3 | Stopping helps | Not run | |
| 4 | Stopping costs too much | Not run | |
| 5 | Free stops | Not run | |
| 6 | Five stations | Not run | |
| 7 | Far apart | Not run | |
| 8 | Eight stations | Not run | |
| 9 | 150,000 stations | Not run | |
| 10 | Even spacing | Not run | |
| 11 | Long runs between stops | Not run |