Reading evenings
A poem is read aloud over k evenings: the lines in order, at least one line each evening, no line split. An evening of L characters is tiring by L²: a long evening is harder than two short ones. Divide the lines into k evenings so that the total tiredness is smallest, and print it.
The third and fourth tests are the 5273 lines of “Eugene Onegin” in the Russian original (by the number of characters in each line), over 10 and 30 evenings.
Input
The first line holds n and k (1 ≤ n ≤ 6000, 1 ≤ k ≤ min(n, 30)). The second holds the line lengths a1, …, an (1 ≤ ai ≤ 100).
Output
The smallest sum of the squared lengths of the evenings.
Examples
Example 1
5 2 3 1 4 1 5
100
Example 2
9 3 10 10 10 1 1 1 10 10 10
1329
Limits
- Time · Python
- 5000 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
A DP over the number of evenings and the lines read: bestg[i] is the least tiredness if the first i lines are read over g evenings. Trying the start of the last evening gives k · n²/2, half a billion steps. What can be said about where the last evening starts as i grows?
2Hint 2
Check the quadrangle inequality for the cost of an evening w(j, i) = (pi − pj)², where p are prefix sums. Call the sums of three pieces A, B, C and compare (A + B)² + (B + C)² with (A + B + C)² + B².
3The idea
The difference between the right and left sides is 2AC ≥ 0, so the inequality holds, and by the monotonicity theorem the best start of the last evening does not decrease with i. Each layer is computed by divide and conquer: the middle by trying the window, the halves in narrowed windows.
4Walkthrough
A layer is a stack of intervals (lo, hi, olo, ohi). For the middle mid try j from olo to min(mid − 1, ohi) and take the best arg; the left half gets the window [olo, arg], the right one [arg, ohi]. Unreachable states (more evenings than lines) are infinity; they must be skipped or added as infinity, not as a large integer, or the sum overflows.
4+Solution
5Complexity
O(k n log n): about two million cost evaluations with k = 30 and n = 6000. The answer is at most (6 · 10⁵)² = 3.6 · 10¹¹ and fits in 64 bits.
6Common mistakes
- Trying the start of the evening. This is
wrong.py: on “Onegin” over ten evenings it is already 140 million steps, and in the third test time runs out. - Greed. “Read until the average is reached” gives evenings of 30, 23 and 10 in the second sample, 1529 instead of 1329: the lines have different lengths, and a boundary shifted by a line is sometimes better.
- A window without the limit j < i. The last evening cannot be empty: the right edge of the window is cut down to mid − 1.
- Overflow with infinity. MaxInt64 + d² overflows; infinite states must be skipped.