The audiobook readers
A studio is recording an audiobook of War and Peace. The chapters of one part are handed out to k readers; each chapter is read whole by one person, all the readers work at the same time, and the part is done when the busiest one finishes. The length of each chapter is known in minutes; in the tests these are real chapters of the novel (in the Russian original) read at 150 words a minute. How should the chapters be handed out so that the part is done as early as possible?
Input
The first line holds the number of chapters n and the number of readers k (1 ≤ n ≤ 20, 1 ≤ k ≤ 6). The second holds the n chapter lengths in minutes, integers from 1 to 60.
Output
The smallest possible working time of the busiest reader, in minutes.
Examples
Example 1
5 2 3 3 2 2 2
6
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 14 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
The most natural thing: take the chapters in decreasing order of length and give each to whoever is least busy right now. Check it on an example: chapters 3, 3, 2, 2, 2 and two readers.
2Hint 2
An exact answer comes from search: give each chapter in turn to each reader. That is kn options, about a trillion for 20 chapters and four readers. Which branches of the search tree can be left unopened without losing anything?
3The idea
A search with the prunings from the article, all at once. The incumbent is the best answer found, and from the very start it is the answer of the greedy method from the first hint. Prune a branch if some reader is already at the incumbent or above; if the same chapter is offered to two readers with equal loads, try only the first; if the remaining chapters do not fit in the readers’ “room” (each can take at most incumbent − 1 − load more); and stop altogether as soon as the incumbent equals the lower bound max(the longest chapter, ⌈sum / k⌉). Hand out the chapters from long to short.
4Walkthrough
Why the greedy method is wrong on the example. It gives the threes to different readers and then the three twos: 3 + 2 + 2 = 7 and 3 + 2 = 5. Better is 3 + 3 = 6 and 2 + 2 + 2 = 6: the two threes together, although each separately “should” go to the free reader. Greed looks one step ahead and does not see that the threes are better off together. Ronald Graham proved in 1969 that this greedy method is off by a factor of at most 4/3, but it is off: on eight tests out of fourteen.
Each pruning is safe, that is, it does not throw away a branch with an answer better than the incumbent: in a branch where a reader is already at the incumbent or above, all plans are no better than the incumbent; two readers with equal loads are interchangeable, and the second one’s branch is a mirror copy of the first one’s; if the room is less than the chapters left, they cannot be handed out better than the incumbent; and no plan can beat the lower bound. The detailed proof is in the article’s section “Why nothing is lost”.
On the real chapters this is enough with a huge margin: the reference solution in Python needs less than a hundredth of a second for the longest test. But there are no guarantees: there are inputs where the same search runs through millions of nodes, and the measurement in the article shows such spikes.
4+Solution
5Complexity
In the worst case O(kn), like any search: the problem is hard (splitting numbers into two equal piles reduces to it). In practice, thousands of nodes, sometimes a handful.
6Common mistakes
- Greed. Wrong on the example and on seven more tests, by a minute in some, by three in others.
- Search without pruning. Correct, but 420 ≈ 1012 nodes do not fit in the time.
- Pruning “above the average”. You may not prune a branch where someone reads more than ⌈sum / k⌉: the average is a lower bound, but it cannot always be reached, and then such a pruning throws away every solution. In most tests you would get away with it, but in the last two the lower bound cannot be reached: three half-hour chapters cannot be split between two readers at 45 minutes each.
- Stopping at a “good” answer. You may stop only at the lower bound, not when the answer “has stopped improving”: an improvement may come in the last branch.
Algorithms behind it
O(kⁿ) in the worst case
2 problems
PAR
Technique
Backtracking
Build a solution step by step, check at once and retreat from dead ends: sudoku, queens, colourings.
O(bᵈ) in the worst case
2 problems