An even right edge
A paragraph of n words has to be set in a column W characters wide, without changing the order of words. Word i takes ai characters, neighbouring words in a line are separated by one space, and a line’s length is the sum of the lengths of its words plus the number of spaces. A line cannot be longer than W; each word fits on its own.
A line’s shortfall is how many characters it lacks to reach W. We want the right edge to be even: find the smallest sum of squares of the shortfalls over all lines but the last. The last line can be any length and is not included in the sum.
Input
The first line holds n and W (1 ≤ n ≤ 5·104, 1 ≤ W ≤ 100). The second holds the n word lengths a1, …, an (1 ≤ ai ≤ W).
Output
A single number: the smallest sum of squares of the shortfalls.
The first example is the Russian phrase «Сложение двух чисел — треть наносекунды.» (“Adding two numbers is a third of a nanosecond.”) in a column of 19 characters. Greedy breaking puts three words in the first line and leaves shortfalls of 0 and 12, a sum of 144. Better is «Сложение двух / чисел — треть / наносекунды.» with shortfalls of 6 and 6, a sum of 72. The second example is the introductory paragraph of the article on dynamic programming in a column of 35 characters.
Examples
Example 1
6 19 8 4 5 1 5 12
72
Example 2
90 35 2 7 8 2 4 8 3 9 2 7 7 4 9 2 7 2 7 6 9 11 5 1 5 3 11 7 6 1 5 6 5 1 22 10 5 8 2 9 1 7 8 2 10 1 9 6 1 5 4 7 3 5 2 12 1 2 11 2 6 9 3 9 8 3 7 11 1 7 9 5 2 4 1 5 7 1 9 1 5 7 5 1 5 3 6 1 13 3 6 8
474
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 11 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
Where does the second-to-last line end? If that is known, what can be said about how all the words before it are broken?
2The idea
Let cost[j] be the smallest sum for the first j words if a line breaks after word j. The last of these lines starts with some word i + 1, and everything before it is broken in the best way: otherwise, replacing the beginning with a better one would reduce the sum too. So cost[j] = the minimum over i of cost[i] + (W − the length of words i + 1..j)2, over all i for which the line fits. For j = n the square is not added, as it is the last line. This is the shortest path through the graph of break points from the article.
3Walkthrough
For each j, try the line start i from right to left and grow the line’s length; as soon as it exceeds W, there is no point going further, as the line only gets longer. At most (W + 1)/2 words fit in a line, so each j takes at most 51 steps. The answer is cost[n].
The sum does not exceed n·W2 = 5·108; in Go an ordinary int is enough.
3+Solution
4Complexity
O(n·W) time and O(n) memory.
5Common mistakes
- Greedy breaking. It gives the smallest number of lines, but not an even edge: the first example gives 144 instead of 72.
- Counting the last line. Then the algorithm starts stretching it to the edge at the expense of the other lines.
- Not breaking out of the loop. Trying all i from 0 to j − 1 gives the same answer, but in O(n2): on 50,000 words that is more than a billion steps.
Algorithms behind it
O(n·L)
2 problems
DP
Technique
Dynamic programming
Reduce a problem to subproblems, solve each once and keep the answers in a table.
states × transitions
2 problems