Коробки-матрёшки
После переезда остались пустые коробки, и их хочется убрать в кладовку как можно компактнее — матрёшкой, одну в другую. Дно у всех коробок прямоугольное, высота не важна: коробки без крышек, и вложенная просто стоит внутри. Коробка входит в другую, если её дно можно поставить на дно другой так, чтобы обе стороны были строго меньше: впритык не влезет. Коробку можно повернуть на 90 градусов, но ставят её ровно, стенками вдоль стенок.
Сколько коробок можно собрать в одну матрёшку — цепочку, где каждая следующая коробка входит в предыдущую?
Вход
В первой строке — n (1 ≤ n ≤ 100 000). Дальше n строк: стороны дна коробки ai и bi в миллиметрах (1 ≤ ai, bi ≤ 109), в любом порядке.
Выход
Одно число — наибольшее число коробок в одной матрёшке.
Примеры
Пример 1
7 400 300 300 500 250 350 350 250 600 450 200 200 610 460
5
Пример 2
4 300 300 300 400 300 500 300 600
1
Ограничения
- Время · Python
- 3000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Коробку можно повернуть. Как записать каждую коробку так, чтобы «входит ли одна в другую» проверялось сравнением двух пар чисел без перебора поворотов?
2Подсказка 2
Если отсортировать коробки по короткой стороне, цепочка — это возрастающая подпоследовательность длинных сторон. Почти. Что делать с коробками, у которых короткая сторона одинаковая?
3Подсказка 3
Подсказка к подсказке: внутри группы с одной короткой стороной расставьте длинные стороны так, чтобы из группы в возрастающую подпоследовательность могло попасть не больше одной коробки.
4Идея
Поворачиваем каждую коробку короткой стороной вперёд: пара (s, l), s ≤ l. Коробка (s₁, l₁) входит в (s₂, l₂), только если s₁ < s₂ и l₁ < l₂: другой поворот ничего не даёт — если длинная сторона меньше короткой стороны другой коробки, то и короткая меньше. Сортируем по короткой стороне по возрастанию, а при равной короткой — по длинной по убыванию. Ответ — длина строго возрастающей подпоследовательности длинных сторон.
5Разбор
После сортировки любая матрёшка — это возрастающая подпоследовательность длинных сторон: внутренние коробки стоят раньше внешних, потому что их короткая сторона меньше. Обратное тоже верно, и тут работает убывание внутри групп. Возьмём строго возрастающую подпоследовательность длинных сторон. Две коробки с одинаковой короткой стороной в неё попасть не могут: в своей группе они идут по убыванию длинной стороны. Значит, у соседей цепочки короткие стороны разные, а раз сортировка по ним возрастает — строго растут. Длинные растут по построению. Каждая следующая коробка цепочки шире и длиннее, то есть в цепочке каждая коробка входит в следующую.
Возрастающую подпоследовательность ищем лестницей за O(n log n): bisect_left, потому что впритык коробка не влезает и равные длинные стороны цепочку не продолжают.
В первом примере коробки 300 × 400 и 300 × 500 не входят друг в друга, хотя по длинной стороне одна больше. После сортировки они идут как 300 × 500, 300 × 400, и в возрастающую подпоследовательность попадает только одна. Ответ 5: 200 × 200, 250 × 350, 300 × 400, 450 × 600, 460 × 610.
5+Решение
6Сложность
O(n log n): сортировка и двоичный поиск на каждую коробку. Двумерная задача свелась к одномерной одной правильной сортировкой.
7Типичные ошибки
- Обе стороны по возрастанию. Коробки с одинаковой короткой стороной выстраиваются в «цепочку»: 300 × 400 и 300 × 500 дают две вложенные коробки, которых не бывает. Первый пример даёт 6 вместо 5.
- Забыть повернуть. Коробка 350 × 250 и коробка 250 × 350 одинаковые, а без поворота сортировка видит их по-разному и теряет матрёшки.
- bisect_right. Пропускает в цепочку коробки с равной длинной стороной, а впритык они не входят.
- Таблица O(n²) по всем парам. Верна, но при ста тысячах коробок — пять миллиардов проверок.