Sawing a log
A log L centimetres long has to be sawn at the marked places. The sawmill charges for each cut as many tenge as there are centimetres in the piece being sawn: the whole piece is pulled through the machine. You choose the order of the cuts. What is the least you have to pay?
For example, a 10 cm log with marks at 2, 4 and 7 can be sawn from left to right: 10 + 8 + 6 = 24 tenge. But starting at 4 gives 10 + 4 + 6 = 20.
Input
The first line holds L and n (2 ≤ L ≤ 106, 1 ≤ n ≤ 150). The second holds n distinct marks in increasing order, each strictly between 0 and L.
Output
One number: the smallest payment in tenge.
Examples
Example 1
10 3 2 4 7
20
Example 2
100 6 25 50 51 52 53 54
191
Limits
- Time · Python
- 2000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Look at the very first cut. After it the two pieces are sawn independently of each other. Which problems are left, and how are they like the original?
2Hint 2
The piece between marks i and j is also a log with its own marks. How much does its first cut cost, wherever it is?
3The idea
Add the ends of the log to the marks: x0 = 0, xn+1 = L. cost[i][j] is the smallest payment for all the cuts inside the piece from xi to xj. The first cut of this piece, at some mark k, i < k < j, costs xj − xi for any k, and then the pieces [i, k] and [k, j] are sawn separately: cost[i][j] = xj − xi + mink(cost[i][k] + cost[k][j]). This is interval DP.
4Walkthrough
Compute the intervals in increasing order of length: each relies only on shorter ones. Pieces with no marks inside cost zero. The answer is cost[0][n + 1].
In the second example the log is 100 cm with marks at 25, 50, 51, 52, 53, 54. The mark nearest the middle is 50, and starting there seems sensible: 208 tenge. It is better to start at 54: then the five close marks end up on a short piece 54 cm long, and the long 46 cm tail is not sawn any more. That gives 191.
4+Solution
5Complexity
O(n²) intervals with O(n) choices of the first cut each: O(n³) time, O(n²) memory. With n = 150 that is about six hundred thousand steps. For large n Knuth’s observation helps: the best mark for [i, j] lies between the best ones for [i, j − 1] and [i + 1, j], and the time drops to O(n²); more in the article on DP optimisations.
6Common mistakes
- Sawing in the middle. Fails the second example: the central mark is not necessarily the best.
- Sawing in order from left to right. You pay for the long remainder again and again: 24 instead of 20 in the first example.
- Intervals in the wrong order. If cost[i][j] is computed in increasing order of i, then cost[k][j] for k > i is not ready yet; you need an order by length or i decreasing.