The problem
A rail runs from 0 to length and must be cut at every position in marks (different whole numbers strictly between 0 and length, in any order). A cut splits one piece into two, and costs the length of the piece being cut. The order of the cuts changes the total. Return the smallest total.
cheapest_cuts(10, [4]) # 10
cheapest_cuts(7, [1, 3, 4, 5]) # 16: cut at 3, 1, 5, then 4
Limits
- Up to 150 marks; the length can be up to 10⁹.
- Trying every order of the cuts is far too slow. Memoised recursion is fine here: it goes at most 150 calls deep.
Builds on ADDP-3 Interval DP.
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 | No marks | Not run | |
| 2 | One mark | Not run | |
| 3 | Two marks | Not run | |
| 4 | The order matters | Not run | |
| 5 | Marks out of order | Not run | |
| 6 | Middle first is not best | Not run | |
| 7 | Marks near the ends | Not run | |
| 8 | Twelve marks | Not run | |
| 9 | Twenty marks | Not run | |
| 10 | 150 marks | Not run | |
| 11 | 150 evenly spaced marks | Not run |