Что спрашивают

Коробки имеют сторону и цвет 1 или 2. Во внешнюю коробку можно вложить внутреннюю другого цвета, если её сторона меньше хотя бы на 4. Подарок помещается в любую коробку.

Нужно максимизировать число коробок, затем сторону самой маленькой. N и стороны ≤ 10 000, одинаковые коробки допустимы. Важно, что цветов ровно два.

Приём решения

Отсортируйте коробки по убыванию стороны. Для фиксированного цвета внешней коробки возьмите самую большую этого цвета. Дальше каждый раз выбирайте самую большую подходящую коробку противоположного цвета с разницей не менее 4.

При двух цветах последовательность цветов полностью определяется первым цветом. На каждом уровне жадно выбранная сторона не меньше стороны в любой другой допустимой цепочке с тем же первым цветом: большой предыдущий уровень и выбор самого большого продолжения не ухудшают возможности. Поэтому такой проход максимизирует и длину, и последнюю сторону.

Но самый большой предмет вообще может мешать: его цвет задаёт неподходящую последовательность цветов. Сделайте два прохода, с началом цвета 1 и цвета 2. Выберите лексикографически большую пару (количество, последняя сторона). Если цвета нет, соответствующий проход даёт (0, 0).

После сортировки два прохода занимают O(N). Общее время O(N log N), память O(N). Для трёх и более цветов такое доказательство уже не работает: следующего цвета нет единственного.

Разбор на примере

Ввод

6
42 1
41 2
37 1
33 2
29 1
25 2

Вывод

5 25
Разбор примера по шагам
Начальный цветСтороны выбранных коробокПара для сравнения
142 → 33 → 29 → 25(4, 25)
241 → 37 → 33 → 29 → 25(5, 25)

Если начать с самой большой коробки 42 цвета 1, коробка 41 цвета 2 слишком близка. Останется цепочка 42, 33, 29, 25 из четырёх. Начало 41 цвета 2 даёт 41, 37, 33, 29, 25 — пять коробок. Значит, глобально наибольшую коробку нужно пропустить.

Код на Python и C++

Выражение 3 - color переключает только цвета 1 и 2. Сортировка пары по цвету при одинаковой стороне не влияет на ответ: вложить равные стороны всё равно нельзя.

В C++ функция chain возвращает pair<int, int>, и max сравнивает пары так же, как в Python.

import sys


def chain(boxes, color):
    count = last = 0
    for side, current_color in boxes:
        if current_color == color and (count == 0 or last - side >= 4):
            count += 1
            last = side
            color = 3 - color
    return count, last


def solve(boxes):
    boxes = sorted(boxes, reverse=True)
    return max(chain(boxes, 1), chain(boxes, 2))


if __name__ == '__main__':
    data = list(map(int, sys.stdin.buffer.read().split()))
    boxes = list(zip(data[1::2], data[2::2]))
    print(*solve(boxes))
#include <algorithm>
#include <functional>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

pair<int, int> chain(const vector<pair<int, int>>& boxes, int color) {
    int count = 0, last = 0;
    for (auto [side, current_color] : boxes) {
        if (current_color == color && (count == 0 || last - side >= 4)) {
            count += 1;
            last = side;
            color = 3 - color;
        }
    }
    return {count, last};
}

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> boxes(n);
    for (auto& [side, color] : boxes)
        cin >> side >> color;
    sort(boxes.begin(), boxes.end(), greater<pair<int, int>>());
    auto [count, last] = max(chain(boxes, 1), chain(boxes, 2));
    cout << count << ' ' << last << endl;
}

Типичные ошибки

  • Начать только с самой большой

    Она может задать невыгодный начальный цвет. Нужно независимо проверить оба цвета.

  • Забыть чередование цветов

    Подходящей разницы сторон недостаточно. Соседние коробки обязаны иметь разные цвета.

  • Сначала сравнить последнюю сторону

    Число коробок важнее. Большая внутренняя сторона улучшает ответ лишь при равной длине цепочки.