A reel of cable
A warehouse sells cable in pieces of standard lengths: a piece li metres long costs ci tenge, and there are any number of buyers for each kind of piece. The warehouse has one roll L metres long. It is cut into standard pieces of any kinds in any quantities, and the remainder, if it is shorter than any piece or not worth cutting, is thrown away. How many tenge can the roll bring in?
Rolls can be very long, up to a trillion metres: this is not one drum but a plant’s yearly output, conveniently counted as one roll.
Input
The first line holds n and L (1 ≤ n ≤ 100, 1 ≤ L ≤ 1012). Then come n lines: the length of a piece li in metres and its price ci in tenge (1 ≤ li ≤ 100, 0 ≤ ci ≤ 2·106).
Output
The largest revenue in tenge.
Examples
Example 1
2 10 3 5000 5 8000
16000
Example 2
2 7 2 1000 9 99000
3000
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 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
If the roll were short, the unbounded knapsack would be enough: g[x] is the best revenue from x metres. But a table of 1012 cells will not fit. Which piece will take up almost the whole of a long roll?
2Hint 2
Let b be the piece with the highest price per metre. Cut as many pieces b as possible, and the remainder in the best way. Check this on the first example: a 10 m roll, pieces of 3 m for 5000 and 5 m for 8000.
3Hint 3
Take, in some best cutting, lb pieces other than b, and look at the sums of the lengths of the first of them, 0, the first, the first two, …, modulo lb. What can be done with a group of pieces whose total length is divisible by lb?
4The idea
Among the best cuttings there is one with fewer than lb pieces other than b. So they take up less than lb · 100 ≤ 104 metres, and everything else is pieces b. Compute the unbounded knapsack g[x] only up to D = min(L, lb · max li) and try how many metres x ≤ D to give to the “other” pieces: the answer is the maximum of g[x] + ⌊(L − x) / lb⌋ · cb.
5Walkthrough
Why fewer than lb other pieces can be left. Suppose there are at least lb; write out any lb of them in a row and compute the lb + 1 sums of the lengths of their beginnings, from the empty one to the full one. There are only lb remainders modulo lb, so two sums give the same remainder, and the pieces between them together have length m · lb. Replace this group with m pieces b: the length is the same, and the revenue does not decrease, since each piece of the group has a price per metre no higher than b’s. There are fewer other pieces now; repeat until there are fewer than lb of them.
Each candidate g[x] + ⌊(L − x) / lb⌋ · cb is an honest cutting, so the answer is no more than the best. And no less: for the best cutting from the proof, the other pieces take up some x ≤ D metres, g[x] is no less than their revenue, and at least as many pieces b fit into the remaining L − x metres as in that cutting.
The best piece is chosen by comparing c1 · l2 > c2 · l1 in integers, without division. Revenue goes up to 2·1018, which still fits in int64.
The greedy idea from the second hint fails on the very first example: three pieces of 3 m give 15,000 and a metre of waste, while two pieces of 5 m give 16,000. Sometimes it pays to cut one or two fewer of the best pieces so that the remainder fits without loss.
5+Solution
6Complexity
O(n · D), where D ≤ 104: about a million steps however long the roll.
7Common mistakes
- A table for the whole roll. A trillion cells will not fit into any memory.
- All the best pieces first, then the remainder. Fails the first example: see the editorial.
- The best piece by price per metre in floating point. With nearly equal prices per metre, division can confuse the order; compare products.