Nesting boxes
After a move there are empty boxes left over, and you want to put them away in the storeroom as compactly as possible, like nesting dolls, one inside another. Every box has a rectangular bottom, and the height does not matter: the boxes have no lids, and a nested box simply stands inside. A box fits into another if its bottom can be placed on the other’s bottom with both sides strictly smaller: a tight fit will not go in. A box may be turned by 90 degrees, but it is placed squarely, walls along walls.
How many boxes can be gathered into one nest, a chain in which each next box fits into the previous one?
Input
The first line holds n (1 ≤ n ≤ 100,000). Then n lines: the sides of a box’s bottom ai and bi in millimetres (1 ≤ ai, bi ≤ 109), in any order.
Output
One number: the greatest number of boxes in one nest.
Examples
Example 1
7 400 300 300 500 250 350 350 250 600 450 200 200 610 460
5
Example 2
4 300 300 300 400 300 500 300 600
1
Limits
- Time · Python
- 3000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 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 box can be turned. How do you write each box so that “does one fit into the other” is checked by comparing two pairs of numbers, without trying rotations?
2Hint 2
If the boxes are sorted by the short side, a chain is an increasing subsequence of the long sides. Almost. What do you do with boxes that have the same short side?
3Hint 3
A hint to the hint: within a group with the same short side, arrange the long sides so that at most one box of the group can get into an increasing subsequence.
4The idea
Turn each box short side first: a pair (s, l), s ≤ l. Box (s₁, l₁) fits into (s₂, l₂) only if s₁ < s₂ and l₁ < l₂: the other rotation gives nothing, since if the long side is smaller than the other box’s short side, so is the short one. Sort by the short side ascending, and with an equal short side by the long side descending. The answer is the length of the strictly increasing subsequence of the long sides.
5Walkthrough
After sorting, any nest is an increasing subsequence of the long sides: the inner boxes come before the outer ones because their short side is smaller. The converse is also true, and this is where the descending order within groups works. Take a strictly increasing subsequence of the long sides. Two boxes with the same short side cannot both get into it: within their group they go in decreasing order of the long side. So neighbours in the chain have different short sides, and since the sort is ascending by them, they strictly rise. The long sides rise by construction. Each next box of the chain is wider and longer, that is, each box in the chain fits into the next.
The increasing subsequence is found with the ladder in O(n log n): bisect_left, because a tight fit does not go in and equal long sides do not extend the chain.
In the first example the boxes 300 × 400 and 300 × 500 do not fit into each other, although one is larger along the long side. After sorting they come as 300 × 500, 300 × 400, and only one gets into the increasing subsequence. The answer is 5: 200 × 200, 250 × 350, 300 × 400, 450 × 600, 460 × 610.
5+Solution
6Complexity
O(n log n): the sort and a binary search for each box. A two-dimensional problem reduced to a one-dimensional one by a single correct sort.
7Common mistakes
- Both sides ascending. Boxes with the same short side line up into a “chain”: 300 × 400 and 300 × 500 give two nested boxes, which is impossible. The first example gives 6 instead of 5.
- Forgetting to turn. A box 350 × 250 and a box 250 × 350 are the same, but without turning the sort sees them differently and loses nests.
- bisect_right. It lets boxes with an equal long side into the chain, but a tight fit does not go in.
- An O(n²) table over all pairs. Correct, but with a hundred thousand boxes it is five billion checks.