Конспект: как читать задачу и как её переформулировать

Понятия

Вид ответа - есть ли / сколько / все / лучший. Одна фраза при разных видах - разные задачи; у «всех» размер ответа - нижняя граница времени.

Бюджет - время на ответ, умноженное на скорость простых операций машины.

Перебор по определению - программа, которая перебирает всех кандидатов и проверяет каждого буквально по условию. Медленная, но без идей - значит, без ошибок в идеях. Это исполняемая спецификация.

Край - вход на границе допустимого: пусто, один элемент, все равны, касание, повторы, наибольший размер.

Переформулировка - назвать объект, который ищется (перестановка, подмножество, дерево, граф, точки, многоугольник, строка), и ограничения на него.

Интервальный граф - вершины-отрезки на прямой, рёбра - пересечения. Жадная раскраска по началу точна: число цветов = наибольшее число одновременно идущих отрезков.

Что унести

ПЯТЬ ВОПРОСОВ К ПРОСЬБЕ
из чего вход: объекты, повторы, порядок, гарантии
вид ответа: есть ли / сколько / все / лучший
что значит «лучше»: критерий, равенство, нужен ли точный оптимум
размер: 10, 10³, 10⁶, больше
края: пусто, один, все равны, касание, равные времена
нет ответа на вопрос -> спросить; некого спросить -> выбрать явно

БЮДЖЕТ (CPython 3.12 на этой машине)
сложение в цикле 15 млн/с, запись в dict 6 млн/с, sorted 3 млн/с
рабочая цифра: Python 10⁷ в секунду, компилируемый 10⁸-10⁹
предел n при бюджете 10⁷ | 10⁹:
  n 10⁷ | 10⁹   n log n 5,3·10⁵ | 4·10⁷   n² 3162 | 31 622
  n³ 215 | 1000   2ⁿ·n 19 | 25   n! 10 | 12
не хватает в тысячи раз -> другой класс; в разы -> константа, замер
sorted против слияния на Python: 47 мс и 940 мс, оба n log n

РУКАМИ, ПЕРЕБОР, КРАЯ, ПОТОМ БЫСТРЫЙ
наибольшая сумма подотрезка [-2, -3, -1]: 0 с пустым, -1 без
Кадане max(0, ...) = «пустой можно»; без пустого - max(x, ...)
переговорки 8-10, 9-10, 10-11: [нач, кон) - 2, [нач, кон] - 3
касание = порядок событий с равным временем: конец раньше начала

СЛОВА -> ОБЪЕКТ
порядок, маршрут, расстановка   -> перестановка
группа, команда, пакет          -> подмножество
иерархия, подчинение            -> дерево
связи, зависимости, конфликты   -> граф
где, ближайший, внутри          -> точки, многоугольники
текст, шаблон, похожесть        -> строки
зависимости модулей -> топологическая сортировка, цикл виден сам
экзамены (любые конфликты) -> раскраска, NP-трудна
встречи (интервалы) -> жадно по началу, n log n, точно

Ловушки джокера

Оптимизировать не ту задачу. Неделя на быстрый подсчёт, а нужен был список - или наоборот.

Ответ не помещается. «Все пары похожих» на миллионе - до 5 · 10¹¹ пар; это видно одной строкой арифметики до кода.

Квадрат «на всякий случай». n = 2 · 10⁵ - это 2 · 10¹⁰ проверок, полчаса вместо двух секунд.

Пропущенное разрешение на перебор. n ≤ 20 в условии - не опечатка, а подсказка: 2ⁿ допустим.

Толкование края выбрано молча. Быстрый алгоритм всегда что-то решает про пустой вход и касание; без перебора не видно, что именно.

«Наша задача особенная». Почти всегда у неё есть название; иногда - структура, которая делает её лёгкой (интервалы вместо произвольного графа).