Учебник
Разборы алгоритмов: как приём устроен, когда он уместен и на чём с ним ошибаются. Читается отдельно от курсов.
Основы
То, без чего не обойтись ни в одной теме: как оценить решение до того, как оно написано.
1Оценка сложности: зайдёт ли решениеКак по ограничениям задачи понять, какой алгоритм от вас ждут, и прикинуть время работы до того, как код написан.6 мин2Стресс-тестированиеКак найти тест, на котором решение ломается, за минуту вместо часа. Быстрое решение против медленного, генератор и цикл сравнения.6 мин3Отладка: санитайзеры, assert и флагиКак заставить компилятор показывать пальцем на строку с ошибкой вместо «ошибка исполнения» без объяснений.4 мин4Генераторы тестовСлучайный тест находит не всё. Какие тесты ломают решения на самом деле и как их порождать.4 мин
Сортировки
От квадратичных до n log n, от подсчёта до порядковых статистик — и что из этого уже есть в стандартной библиотеке.
1Квадратичные сортировкиПузырёк, вставки и выбор. Зачем их знать, если есть sort, и какая из трёх действительно полезна.7 мин2Сортировка слиянием и подсчёт инверсийПервая сортировка за n log n. И то, ради чего её стоит уметь писать руками: считать инверсии по дороге.6 мин3Быстрая сортировка и разделение массиваРазделяй и властвуй без дополнительной памяти. Почему худший случай квадратичный и почему он всё равно не наступает.6 мин4K-я порядковая статистика за линейное времяНайти k-й по величине элемент, не сортируя массив. Тот же partition, но рекурсия идёт только в одну сторону.4 мин5Пирамидальная сортировка и кучаЧто получится, если научить сортировку выбором доставать минимум быстро. Куча, просеивание и построение за линию.5 мин6Просеивание и изменение ключаВторое просеивание - вверх. Как менять значение уже лежащего в куче элемента и почему ответ «на каком месте он оказался» жёстко задаёт реализацию.3 мин7Приоритетная очередьКуча как структура данных, а не как шаг сортировки. Вместимость, дубликаты, удаление по индексу и то, чего не умеет std::priority_queue.4 мин8Почему быстрее n log n нельзяДоказательство нижней оценки через дерево решений — и что именно оно запрещает, а что нет.4 мин9Сортировка подсчётом и устойчивостьКогда сравнения не нужны вовсе. И что такое устойчивость — на примере очереди в поликлинику.4 мин10Поразрядная сортировкаПодсчёт, применённый по разрядам. Как отсортировать миллионы чисел за четыре прохода и почему без устойчивости это не работает.4 мин11Сортировки в C++sort, stable_sort, nth_element, компараторы и лямбды. И контракт, нарушение которого роняет программу.4 мин12Сортировки в Pythonsorted, list.sort, ключи и компараторы, heapq и bisect. И чем гарантии Python отличаются от C++.4 мин
Поиск
Бинарный поиск как дисциплина инварианта: по массиву, по ответу, по вещественному числу — и всё, что из него вырастает.
1Бинарный поиск: инвариант вместо угадыванияОдин шаблон, в котором нечего перепутать, и правило выбора границ, из-за которого решения падают на закрытых тестах.4 мин2Поиск по ответуКак свести незнакомую задачу к массиву из нулей и единиц — и три приметы, по которым это узнаётся в условии.4 мин3Вещественный поискПочему «пока разность больше эпсилон» — плохое условие остановки, и что писать вместо него.3 мин4Готовый поиск в C++ и Pythonlower_bound, upper_bound, equal_range и модуль bisect. Что они возвращают и где их применять нельзя.3 мин5Тернарный поискЧто делать, когда функция не монотонна, а сначала убывает и потом растёт. И почему обычный бинарный поиск справляется с этим не хуже.6 мин6Интерактивные задачиЗадачи, где судья отвечает на ваши вопросы. Сброс буфера, протокол взаимодействия и локальное жюри, на котором это можно отладить.5 мин7Поиск без сортировкиБинарный поиск не требует отсортированного массива. Ему нужен инвариант — и это совсем не одно и то же.5 мин8Семь задач на поиск по ответуРазбор постановок, которые встречаются чаще всего: коровы в стойла, провода, встреча в точке, принтеры, шарики, выборы. Для каждой — предикат и границы.7 мин9Подсчёты и запросы бинарным поискомСколько раз элемент встречается, какой ближайший, есть ли он на отрезке, где медиана объединения двух массивов. Всё — парами границ.6 мин10Экспоненциальный поискЧто делать, когда правой границы нет: удвоение до первого превышения, а потом обычный бинарный поиск. И поиск по битам как альтернатива.4 мин11Параллельный двоичный поискМного двоичных поисков сразу: корзины по серединам и один прогон процесса на раунд вместо одной проверки на поиск.3 мин
Линейные алгоритмы
Приёмы, которые заменяют перебор пар одним проходом: префиксные суммы, два указателя, стек и очередь с минимумом.
1Префиксные суммы и разностный массивДва зеркальных приёма: быстро отвечать на запросы суммы и быстро прибавлять на отрезке. Почему одновременно так не выйдет.3 мин2Два указателяОкно, которое едет по массиву. Почему это линейно, при каком условии приём применим и что ломается без него.3 мин3Стек ближайших меньшихСтек, в котором лежат только кандидаты, ещё способные пригодиться. Три разные задачи, один и тот же цикл.3 мин4Очередь с минимумомМинимум в окне за константу. Почему с головы снимают по индексу, а не по значению.2 мин5Очередь на двух стеках и амортизацияОдна операция стоит линию, а все вместе — линию. Как это возможно и зачем нужно, когда есть готовый deque.4 мин6Отрезок с максимальной суммойЗадача Кадане: два разных линейных решения, одно понятное, другое короткое. Плюс версия для матрицы.4 мин7Максимальный прямоугольникНаибольший прямоугольник в гистограмме за линию — и как из него получается наибольший прямоугольник из нулей в таблице.4 мин8Сжатие координатЗначения до 10^9 заменяются на номера от 0 до n. Три строки кода, которые открывают доступ к массивам там, где их не завести.3 мин9Подотрезки с заданной суммойДва указателя не работают с отрицательными числами. Префиксные суммы плюс словарь работают всегда — и считают то, что окном не посчитать.4 мин10Задачи на подотрезки: какой приём когдаСводка по всему разделу: по формулировке условия определить, каким из шести приёмов задача решается.4 мин11Многомерные префиксные суммыДвумерный случай обобщается на любое число измерений: 2^k слагаемых, знак по чётности числа левых границ.3 мин12Стек с минимумомХранить рядом с элементом минимум всего, что под ним. Отсюда — очередь с минимумом на двух стеках, альтернатива деку.3 мин13Вычисление выражений стекомПостфиксная запись считается одним проходом без рекурсии. Заодно бесплатно проверяется её корректность.3 мин14Сортировка стекомВагоны, тупик и один разъезд. Задача, где жадность единственно возможна, — а количество ответов оказывается числом Каталана.4 мин15Очередь со вставкой в серединуТретья операция, которой нет ни у одного контейнера. Два дека, между которыми поддерживается баланс.4 мин
Жадные алгоритмы
Брать выгодное сейчас — и понимать, когда это приводит к верному ответу, а когда к правдоподобному вранью.
1Жадность и почему ей нельзя веритьАлгоритм, который на каждом шаге берёт то, что выгодно сейчас. Почему он так часто неверен и почему это не видно на примерах.3 мин2Доказательство обменомКак доказать жадность, не зная, что делает оптимальный алгоритм. Разбор на задаче о расписании.4 мин3Как ломать жадностьСтресс-тест против перебора: сорок строк, которые находят контрпример за секунды. И почему сверка двух своих решений так не работает.3 мин4Классические жадные задачиШесть задач, где жадность верна, — и короткое обоснование для каждой.3 мин5Непрерывный и дискретный рюкзакДве почти одинаковые задачи: одна решается жадностью за n log n, вторая жадностью не решается вовсе. Разбор границы.4 мин6Размен монетЖадность верна для российских монет и неверна для номиналов 1, 3, 4. Замеры, доказательство и способ проверить свою систему.4 мин7Сортировка как жадностьБольшинство жадных решений — это «отсортировать по правильному ключу». Как вывести ключ обменом соседей, а не угадать.5 мин8Жадность с кучейКогда одной сортировки мало: решение зависит от того, что уже набрано. Дедлайны с отказами, слияние файлов, минимум аудиторий.4 мин9Жадность на отрезкахЧетыре задачи про отрезки, где всё решает выбор ключа сортировки: проколоть, покрыть, объединить, выбрать непересекающиеся.4 мин10Жадность на строках и числахУдалить k цифр, чтобы число стало минимальным, — за линию через стек. И почему брать «первую попавшуюся большую цифру» неверно.4 мин
Теория чисел
Делимость, простые числа, разложение на множители и арифметика по модулю.
1НОД и НОКАлгоритм Евклида с доказательством, связь через разложение на множители и формула, в которой легко переполниться.4 мин2Простые числа и решетоПроверка на простоту до корня, решето Эратосфена и минимальный простой делитель, который заменяет разложение.3 мин3Разложение на множители и делителиКак разложить число до корня, почему делителей мало и как посчитать их число, не перебирая.3 мин4Арифметика по модулюОстатки, быстрое возведение в степень и деление, которого нет. Плюс ловушка с отрицательными числами.3 мин5Расширенный алгоритм ЕвклидаТот же Евклид, но по дороге он находит коэффициенты уравнения ax + by = НОД. Отсюда — обратные элементы и все целые решения линейных уравнений.6 мин6Линейное решетоРешето, в котором каждое составное вычёркивается ровно один раз. С доказательством — и с честным ответом, почему на практике оно часто медленнее Эратосфена.6 мин7Сравнения и китайская теоремаКогда уравнение ax ≡ b (mod m) разрешимо и сколько у него корней. Восстановление числа по остаткам и то, зачем это на самом деле нужно.6 мин8Комбинаторика по модулюБиномиальные коэффициенты за константу после линейной подготовки: факториалы, обратные факториалы одним проходом и типовые формулы.5 мин9Переполнение и выбор типаГде именно ломается целочисленная арифметика: i*i вместо sqrt, порядок в НОК, отрицательный остаток и почему long long везде — тоже плохая идея.5 мин10Простота и разложение больших чиселЧто делать, когда число до 10^18 и перебор до корня уже не проходит: тест Миллера—Рабина и ро-алгоритм Полларда.6 мин
Рекурсия и перебор
Стек вызовов, ленивая динамика и генерация комбинаторных объектов — от перестановок до скобочных последовательностей.
1Рекурсия и стек вызововЧто физически происходит при вызове функции, почему глубина ограничена и на какой она обрывается. С замерами.4 мин2Мемоизация и ленивая динамикаРекурсия плюс массив ответов. Экспонента превращается в линию, а порядок обсчёта динамики становится не нужен.5 мин3Перебор последовательностейОдин шаблон, из которого получаются все переборные задачи: строки, перестановки, разбиения. Плюс почему порядок выходит лексикографическим сам собой.4 мин4Перестановки и подмножестваДва самых частых переборных объекта: n! перестановок через массив «использовано» и 2^n подмножеств через битовые маски.4 мин5Отсечения в перебореНе заходить в ветку, где ответа заведомо нет. Приём, который превращает неработающий перебор в проходящий, — без изменения идеи.4 мин6Разбиения на слагаемые и множителиКак перебрать все способы представить число суммой или произведением — по одному разу каждый, без повторов и без сортировки в конце.4 мин7Ханойские башниЗадача, решаемая тремя строками — если поверить в решение для n−1. Разбор индукции, из которой оно получается.4 мин8Задача о ферзяхРасставить n ферзей, не бьющих друг друга. Как свести доску к перестановке и почему проверять на лету втрое выгоднее, чем в конце.4 мин9Скобочные последовательностиБаланс, стек и числа Каталана. Как генерировать правильные скобочные последовательности и как считать их, не выписывая.5 мин10Сколько стоит переборТаблица замеров: что успевает перебраться за секунду. И что делать, когда ограничения чуть больше, чем позволяет перебор.4 мин
C++ и STL
Контейнеры стандартной библиотеки, итераторы и места, где язык ведёт себя не так, как ожидается.
1ВекторМассив, который умеет расти. Чем resize отличается от assign, почему push_back дешёвый и когда вектор копируется незаметно.3 мин2Стек, очередь, дек и очередь с приоритетомЧетыре контейнера, у каждого своя короткая жизнь. Чем меньше операций поддерживает структура, тем быстрее она работает.3 мин3Множества и словариset, map, multiset и их неупорядоченные версии. Что возвращают insert и erase, и почему lower_bound надо вызывать методом.4 мин4ИтераторыУмные указатели на элемент. Полуинтервалы, приоритет операторов и почему итератор внезапно перестаёт работать.5 мин5Типы и знаковостьЧто куда помещается, почему size() без знака ломает цикл и зачем существует __int128.5 мин6Свои структурыПочему пара пар — плохая идея, как научить структуру сравниваться и вводиться, и что делает const в объявлении оператора.5 мин7Компараторы и лямбдыКак отсортировать не так, как по умолчанию. Синтаксис лямбд, захват переменных и требование, нарушение которого роняет sort.5 мин8Алгоритмы стандартной библиотекиПолтора десятка функций из <algorithm> и <numeric>, которые экономят десятки строк: unique, iota, accumulate, partial_sum и остальные.5 мин9Ввод и выводЗамеры: cin без ускорения читает два миллиона чисел 395 мс, с ускорением — 71. Плюс getline, точность вывода и чтение до конца файла.4 мин10Неопределённое поведениеПочему «локально работает, а на сервере падает» — это почти всегда ваша ошибка. Каталог случаев и способ их ловить.4 мин
Динамическое программирование
Состояние, переход, база и порядок обсчёта. Классические постановки от лестницы до рюкзака.
1Что такое динамикаСостояние, переход, база и порядок. Четыре вопроса, ответы на которые и есть решение задачи.6 мин2Одномерная динамикаСостояние — одно число. Переходы вперёд и назад, расширение состояния и типичные постановки.5 мин3База, порядок и недостижимые состоянияТри места, где динамика ломается молча: неверная база, неверный порядок обсчёта и состояние, которого не бывает.4 мин4Динамика по таблицеСостояние — клетка. Пути в сетке, препятствия, стоимость пути и порядок обхода, который читается прямо из формулы.4 мин5Восстановление ответаДинамика посчитала число, а в условии просят сам ответ. Два способа его достать и правило для лексикографического минимума.3 мин6Наибольшая возрастающая подпоследовательностьКвадратичное решение, решение за n log n и то, как одно превращается в другое. Плюс строгость сравнения, на которой все спотыкаются.5 мин7Наибольшая общая подпоследовательность и редакционное расстояниеДве задачи на паре строк с одинаковой таблицей. Разбор переходов, разница между подпоследовательностью и подстрокой.5 мин8Рюкзак и достижимые суммыЧетыре варианта одной задачи: каждый предмет по разу, сколько угодно раз, ограниченное число раз и просто достижимые суммы.5 мин9Динамика по подотрезкамСостояние — пара границ, порядок обсчёта — по возрастанию длины. Склейка, палиндромы и почему это кубическое решение.6 мин10Оптимальное дерево поискаКлассическая динамика по подотрезкам, где стоимость зависит от глубины. Плюс оптимизация Кнута, которая убирает один множитель n.3 мин11Экономия памятиТаблица не помещается в лимит. Скользящие строки, свёртка в один массив и цена, которую за это платят.4 мин12Выигрышные и проигрышные позицииДинамика, в которой состояние — позиция игры, а значение — исход. Два правила, из которых выводится всё остальное.4 мин13Динамика по цифрамСколько чисел до 10^18 обладают нужным свойством. Состояние — позиция цифры, флаг прижатия к границе и признак начала числа.5 мин14Как придумать динамикуПорядок действий, каталог состояний по типу условия и список ошибок, которые стоит проверить прежде, чем менять решение.5 мин
Графы
Хранение, обход в глубину и обход в ширину и всё, что из них растёт: компоненты, двудольность, кратчайшие пути в невзвешенном графе, циклы, топсорт, сильная связность, мосты. Дальше — веса: Дейкстра, Флойд, Форд — Беллман.
1Графы: определения и хранениеТри способа хранить граф и таблица, по которой выбирают между ними. Плюс минимум терминов, без которых дальше не обойтись.4 мин2Дерево: четыре определенияВ условии могут написать любое из четырёх — и все они об одном и том же. Почему они эквивалентны и что из этого следует.4 мин3Обход в глубинуЧетыре строки, из которых вырастает половина раздела. Компоненты связности, времена входа и выхода, и что делать с глубиной рекурсии.5 мин4Двудольность и раскраска в два цветаПокрасить граф в два цвета или доказать, что нельзя. Критерий через нечётные циклы и почему на трёх цветах всё ломается.4 мин5Неявный графРёбер может быть квадрат, а нужных из них — линия. Как не построить лишнего и что делать с координатами до миллиарда.4 мин6Обход в ширинуОчередь вместо стека — и обход начинает выдавать кратчайшие расстояния. Почему это работает, как восстановить путь и что ломается, если помечать вершину не в тот момент.8 мин7Обход в ширину, когда рёбра неравныеДек вместо очереди для весов 0 и 1, разбиение ребра для весов 1 и 2, вёдра Диала для маленьких весов — три способа не доставать Дейкстру.6 мин8Граф состоянийВершина — не обязательно кружок на картинке. Приём, который превращает задачу «за сколько шагов» в обычный обход.6 мин9Диаметр дереваДва обхода вместо перебора всех пар. Алгоритм в пять строк, доказательство длиннее алгоритма — и почему в общем графе так нельзя.3 мин10Дерево обхода и поиск цикловРёбра графа распадаются на четыре вида, и по виду ребра сразу видно, есть ли цикл. Разные критерии для ориентированного и неориентированного случая.4 мин11Топологическая сортировкаВыстроить вершины в ряд так, чтобы все рёбра шли слева направо. Через времена выхода и через степени входа.4 мин12Компоненты сильной связностиАлгоритм Косарайю: два обхода и транспонированный граф. Почему работает именно эта комбинация и ни одна другая.5 мин132-SATЛогическая задача, которая целиком превращается в графовую: литералы — вершины, импликации — рёбра, ответ — компоненты сильной связности.5 мин14Мосты и точки сочлененияОдна величина up[v] решает обе задачи. Вывод формулы, отдельный случай корня и ловушка с кратными рёбрами.4 мин15Рёберная двусвязностьСжать компоненты, оставить мосты — и любой граф превращается в дерево. Приём, который сводит задачи на графах к задачам на деревьях.3 мин16Единственность топологической сортировкиПорядок единственный тогда и только тогда, когда между каждой парой соседей в нём есть ребро. Проверяется одним проходом.2 мин17Алгоритм ДейкстрыКратчайшие пути из одной вершины во взвешенном графе. Две реализации, одна забытая строчка — и квадрат вместо логарифма.6 мин18Дерево кратчайших путейИз $m$ рёбер для кратчайших путей важны $n-1$. Плюс запуск обхода сразу из множества вершин.4 мин19Бинпоиск и кратчайшие путиМаксимизируется минимум — значит, внутри проверки будет обход. Разбор задачи, где это видно целиком.4 мин20Алгоритм ФлойдаКратчайшие пути между всеми парами в четыре строки. Восстановление пути, отрицательные циклы и почему порядок циклов менять нельзя.5 мин21Алгоритм Форда — БеллманаКратчайшие пути при отрицательных весах. Обычная динамика, с которой исторически и начался сам термин.4 мин22Кактусы и цикл чётной длиныЕсли два цикла делят ребро, чётный цикл найдётся сам. Остаётся случай, когда циклы не пересекаются, — а это кактус.3 мин23Восстановление массива по суммам на отрезкахУсловия вида «сумма на отрезке равна x» — это рёбра графа. Обход даёт и ответ, и проверку на противоречивость.3 мин
Битовые операции
От четырёх идиом про отдельный бит до динамики по подмножествам: маски как множества, подмаски, суммы по подмаскам, битсет, XOR и базис, код Грея, ним.
1Битовые операцииШесть операций, дополнительный код и таблица приоритетов, из-за которой чаще всего и ломается код.3 мин2Биты и маскиЧетыре идиомы про отдельный бит и две про хвост числа. С них начинается любая битовая задача.2 мин3Битовые трюкиСнять младшую единицу, оставить только её, проверить степень двойки, посчитать биты. Короткие идиомы и замеры, насколько они быстрее.2 мин4Маска как множествоЧисло из n битов — это подмножество n-элементного множества. Словарь перевода и перебор всех подмножеств.2 мин5Подмаски и надмаскиИдиома перебора подмасок, почему всего их 3^n, и как перебирать надмаски.2 мин6Суммы по подмаскамПрефиксные суммы на решётке подмножеств: четыре преобразования за O(2^n · n), обращение Мёбиуса и где их путают.3 мин7БитсетМассив булевых значений, упакованный по 64 в слово. Когда даёт выигрыш, сколько именно, и чего с ним нельзя.2 мин8Исключающее «или»Почему XOR встречается в задачах чаще остальных операций: обратимость, связь со сложением и жадность по старшему биту.3 мин9Линейный базис по XORМетод Гаусса над полем из двух элементов: сколько значений достижимо, какое наибольшее и выражается ли данное число.2 мин10Код ГреяНумерация, в которой соседние числа отличаются одним битом. Формула в одну строку, обращение и где это нужно.2 мин11Динамика по подмножествамСостояние — маска использованных элементов. Коммивояжёр, разбиение на пары, покрытие множества и замеры, до каких n это живёт.2 мин12Ним и функция ГрандиПочему в задачах про игры внезапно появляется XOR: значения Гранди, mex и сумма игр.3 мин13Бор с глобальными операциямиДвоичный бор с младшим битом сверху: xor всему множеству ленивой маской, прибавление единицы — обменом детей.3 мин
Геометрия
Векторы, два произведения и всё, что из них следует: прямые, отрезки, расстояния и пересечения.
1Точки и векторыВся вычислительная геометрия — это арифметика над парами чисел. Базовые операции и то, почему точка и вектор в коде одно и то же.3 мин2Скалярное произведениеОдно число, по знаку которого видно, смотрят векторы в одну сторону или в разные. Проекция, перпендикулярность и угол.3 мин3Векторное произведениеЧисло, по знаку которого видно, слева или справа. Площадь, повороты и связь со скалярным произведением.4 мин4Шаблон по геометрииСтруктура точки с операторами, ввод-вывод и один конструктор, из-за которого теряют часы.4 мин5Точность и эпсилонПочему нельзя писать == для вещественных чисел, как выбрать эпсилон и когда без него можно обойтись вовсе.4 мин6Прямая: три представленияПочему y = kx + b не годится, что такое нормаль и направляющая и как переходить между формами без деления.5 мин7Расстояние до прямой и проекцияДве формулы — через уравнение и через векторное произведение. Проекция точки, симметричная точка и ловушка с направлением нормали.4 мин8Пересечение прямыхСистема из двух уравнений, определитель и три случая ответа. Плюс способ, который не требует помнить формулу.4 мин9Точка на прямой, луче и отрезкеТри проверки, отличающиеся одним условием. Все три — в целых числах, без единого деления.4 мин10Пересечение отрезков и расстояние до отрезкаЗнаки векторных произведений плюс проверка прямоугольников — и коллинеарный случай перестаёт быть проблемой.5 мин11ОкружностиПересечение прямой с окружностью через проекцию центра. Пересечение двух окружностей сводится к первой задаче вычитанием уравнений.5 мин12Площадь многоугольникаСумма косых произведений по всем рёбрам. Точка отсчёта берётся любая — даже снаружи, и это работает.3 мин13Углы и полярная сортировкаКогда угол действительно нужен — считать его через atan2. А сортировать точки по углу лучше вообще без углов.3 мин14Замечательные точки треугольникаБиссектриса, вписанная и описанная окружности, центр масс. Четыре формулы, которые выводятся, а не запоминаются.2 мин15Точка внутри многоугольникаЛуч из точки и подсчёт пересечений — для произвольного многоугольника. Для выпуклого — двоичный поиск за логарифм.3 мин16Выпуклая оболочкаНаименьший выпуклый многоугольник, содержащий все точки. Строится сортировкой и двумя проходами со стеком.2 мин17Касательные к окружностиТочки касания из внешней точки находятся без тригонометрии: проекция и сдвиг вдоль перпендикуляра.2 мин18Большие координаты: где кончается 64 битаСколько разрядов нужно на векторное произведение и площадь при координатах до 10^9, и что делать, когда их не хватает.2 мин19Вращающиеся калиперыДиаметр множества точек за линию после построения оболочки: два указателя, идущие по выпуклому контуру.2 мин20Минимальная покрывающая окружностьАлгоритм Уэлцля: три вложенных цикла, которые вопреки виду работают за линейное время в среднем.2 мин
Отрезки и сканирующая прямая
Отрезок как пара событий: покрытие, объединение, вложенность, дуги на окружности и переход на плоскость.
1События и порядок сортировкиОтрезок превращается в два события, дальше остаётся один проход. Вся сложность — в том, как сортировать события при совпадающих координатах.3 мин2Баланс: сколько отрезков покрывает точкуОдна переменная, которая растёт на открытии и падает на закрытии. Самая покрытая точка, число слоёв и связь со скобочной последовательностью.3 мин3Запросы как событияЕсли запросы можно прочитать заранее, они становятся частью того же прохода. Офлайн-обработка и порядок событий трёх типов.3 мин4Объединение отрезковДлина покрытия, число связных кусков и сами куски — за один проход по событиям. Плюс сравнение с сортировкой по левому концу.3 мин5Вложенные отрезкиУбрать все отрезки, лежащие внутри других. Правильный компаратор при равных левых концах — половина решения.3 мин6Дуги на окружностиРасписание, где смена переходит через полночь. Два способа разрезать окружность и не потерять ни одного случая.3 мин7Площадь объединения прямоугольниковСканирующая прямая переходит на плоскость. Решение через сжатие координат, которое пишется за десять минут и не требует дерева отрезков.3 мин8Ближайшая пара точекСканирующая прямая с окном: множество точек, отсортированное по y, из которого выбрасываются далёкие. Простое решение классической задачи.4 мин9Множество отрезков онлайнСканирующая прямая требует знать все события заранее. Когда их знать нельзя, отрезки держат в `set` и ищут соседей через `lower_bound`.5 мин10Задачи про отрезки: какой приём когдаСводка по разделу и по соседним: у задач про отрезки четыре разных техники, и выбор определяется формулировкой.3 мин
Хеши
Полиномиальное хеширование строк, хеши подстрок, коллизии и взломы, хеши множеств и деревьев.
1Что такое хеш-функцияСопоставить объекту число так, чтобы сравнение чисел заменяло сравнение объектов. Четыре требования и почему каждое существенно.3 мин2Полиномиальное хешированиеСтрока как число в системе счисления с основанием p. Схема Горнера, выбор параметров и одна деталь, без которой всё ломается.3 мин3Модульная арифметика в кодеОперация взятия остатка дорогая, и в половине случаев её можно не выполнять. Три функции и структура, которые убирают целый класс ошибок.4 мин4Хеши подстрокОдин предподсчёт за линию — и хеш любой подстроки за константу. Формула, её вывод и типичная ошибка в границах.3 мин5Коллизии и парадокс дней рожденияПочему модуля 10^9 хватает для ста тысяч сравнений и не хватает для миллиона строк. Как считать нужный размер хеша.3 мин6Как ломают хешиМодуль 2^64 ломается строкой длины 128 — с воспроизводимым примером. Что с этим делать и почему помогает случайное основание.3 мин7Сравнение подстрокНаибольший общий префикс бинарным поиском за логарифм — и лексикографическое сравнение любых двух подстрок следом за ним.3 мин8Период строкиНаименьшая строка, повторением которой получается данная. Перебор делителей за n log n и трюк со сдвигом, работающий и для неполного повторения.3 мин9Хеширование множествХеш, не зависящий от порядка: случайное число каждому элементу и XOR или сумма. Различие между множеством и мультимножеством — в выборе операции.3 мин10Хеши деревьевПроверить, что два дерева одинаковы с точностью до перенумерации вершин. Хеш поддерева через отсортированный список детей.3 мин
Строки
Бордеры и префикс-функция, поиск подстроки, автомат, z-функция, бор, Манакер и Ахо — Корасик. Точные алгоритмы там, где хешей мало.
1Бордеры и префикс-функцияПрефикс, равный суффиксу. Одна лемма, из которой выводится весь алгоритм, и внутренний цикл, который выглядит квадратичным, но не является им.4 мин2Поиск подстрокиСклеить шаблон с текстом через разделитель — и задача сводится к уже написанной префикс-функции. Плюс версия, которой хватает памяти на один шаблон.3 мин3Автомат префикс-функцииЗаранее посчитать, куда ведёт каждый символ из каждого состояния. Тогда шаг по тексту стоит константу, а откаты становятся не нужны.3 мин4Z-функцияДля каждой позиции — длина совпадения с началом строки. Другой способ считать то же самое, с другим худшим случаем.4 мин5БорДерево, где буквы живут на рёбрах, а строки — на путях от корня. Общие префиксы хранятся один раз.3 мин6Запросы к боруНайти минимальную строку не меньше данной, найти k-ю по порядку, удалить строку. Один счётчик, без которого всё это ломается.5 мин7Манакер: все палиндромы за O(n)Для каждого центра - радиус наибольшего палиндрома. Тот же приём с самым правым окном, что и в z-функции, только окно теперь палиндромное.5 мин8Неточное совпадениеВхождения образца, где разрешено ошибиться в k символах. Z-функция в две стороны и приём «прыгать через ошибку».3 мин9Ахо - КорасикПоиск сразу всех образцов набора за один проход по тексту. Бор плюс суффиксные ссылки, то есть префикс-функция на дереве.5 мин10Нормализация: когда «равны» значит не «равны»Совпадение с точностью до сдвига, поворота алфавита или перестановки букв. Приём один: свести к инварианту и искать точное равенство.4 мин11Задачи на строки: какой приём когдаЧетыре инструмента с сильно разными сильными сторонами. Таблица выбора и типовые постановки.3 мин
Запросы на деревьях
Времена входа и выхода, наименьший общий предок пятью способами, функции на пути и sparse table.
1Времена входа и выходаДва числа на вершину, после которых «является ли предком» проверяется одним сравнением, а поддерево превращается в отрезок массива.3 мин2Двоичные подъёмы и LCAЗапомнить прыжки на степени двойки — и подъём на любую высоту складывается из битов. Два способа искать наименьшего общего предка, оба за логарифм.4 мин3Level Ancestor и лестницыПодняться ровно на k уровней. Один двоичный прыжок плюс обращение в массив — и запрос стоит константу.3 мин4Прыжковые указатели: линейная памятьОдин прыжок на вершину вместо логарифма. Правило, по которому он выбирается, выглядит произвольным — и всё равно даёт логарифм на запрос.4 мин5Функции на путиСумма на пути берётся из префиксов до корня. Минимум так нельзя — но он считается прямо в двоичных подъёмах.3 мин6Эйлеров обход и LCAВыписать вершины в порядке обхода, включая возвраты, — и LCA превращается в минимум на отрезке массива.3 мин7Sparse tableМинимум на отрезке за константу без всяких деревьев. Работает не для любой функции — и понятно, для какой именно.3 мин8LCA офлайн: алгоритм ТарьянаЕсли все запросы известны заранее, LCA считается одним обходом и системой непересекающихся множеств — почти за линию.3 мин
Остовные деревья и СНМ
Лемма о безопасном ребре и три алгоритма из неё. Система непересекающихся множеств и приём «меньшее к большему».
1Остовное дерево и лемма о безопасном ребреОдна лемма, из которой следуют сразу три алгоритма. Доказательство обменом рёбер в цикле.3 мин2Алгоритм ПримаРастим дерево из одной вершины, каждый раз добавляя ближайшую. Это Дейкстра, у которой поменяли одну строку.2 мин3Алгоритм КраскалаОтсортировать рёбра и брать подряд те, что соединяют разные компоненты. Всё содержание — в структуре, которая отвечает на вопрос «в одной ли компоненте».2 мин4Алгоритм БорувкиКаждая компонента одновременно выбирает себе минимальное ребро. Число компонент падает вдвое за итерацию, поэтому итераций логарифм.2 мин5Система непересекающихся множествДве операции: в одном ли множестве, объединить. Две эвристики, каждая по отдельности даёт логарифм, вместе — почти константу.5 мин6Меньшее к большемуСливая два множества, всегда переливайте меньшее в большее. Одна строка превращает квадрат в n log n.3 мин
Динамика на графах
Порядок пересчёта задаёт структура: обход дерева, топологическая сортировка или возрастание маски.
1Динамика на деревьяхПосчитали ответ для поддеревьев детей — собрали ответ для своего. Порядок пересчёта задаёт сам обход.4 мин2Дерево-рюкзакСостояние — вершина и размер. Выглядит как куб, а на деле квадрат — если писать границы циклов честно.4 мин3Смена корняОтвет для всех вершин сразу, а не только для корня. Один обход вниз, один вверх - и не надо запускать динамику n раз.3 мин4Вклад ребраСумму по всем парам вершин не обязательно считать перебором пар. Часто дешевле спросить у каждого ребра, в скольких парах оно участвует.2 мин5Динамика на ациклическом графеТопологический порядок — это и есть порядок пересчёта. Плюс разбор, что такое «динамика вперёд» и «назад».3 мин6Подсчёт путейПутей может быть экспоненциально много, а посчитать их — линия. И приём, который сводит «через набор вершин» к произведению.3 мин7Динамика по маскамПодмножество как число. Экспонента, но приемлемая — до двадцати с небольшим элементов.4 мин
Дерево отрезков
Устройство и запросы, составной узел, спуск, отложенные операции и алгебра пометок, разности, дерево по значениям, разложение по битам, порядковые статистики и сканирующая прямая.
1Зачем нужно дерево отрезковЗадача, в которой запросы и изменения перемешаны, и почему префиксные суммы со sparse table на ней ломаются.2 мин2Устройство и построениеРазбиение массива на отрезки, почему массива размера 4n всегда хватает и как построить дерево за O(n).2 мин3Запрос и изменение элементаПочему любой отрезок разбивается на O(log n) узлов и как это превращается в двадцать строк кода.2 мин4Итеративное деревоДерево без рекурсии на массиве длины 2s: вдвое короче, заметно быстрее и работает не для всех операций.3 мин5Какие функции ложатся в деревоАссоциативность как единственное требование, нейтральный элемент как источник ошибок и идемпотентность как разделитель со sparse table.2 мин6Узел сложнее числаМинимум с количеством, максимальная сумма подотрезка и длина серии: как выводить содержимое узла, а не вспоминать его.3 мин7Спуск по деревуВопрос «где» вместо «сколько»: k-й ноль и первый элемент не меньше x за один логарифм вместо двух.3 мин8Отложенные операцииПрибавление на отрезке, правило проталкивания и случай, когда проталкивать не нужно вовсе.3 мин9Алгебра пометокПрисвоение стирает всё под собой; когда операций две, пометка становится парой с фиксированным порядком.2 мин10Массив разностейОперация на отрезке превращается в два точечных изменения — и пометки становятся не нужны.2 мин11Дерево по значениямИндекс дерева — не позиция, а значение: инверсии за один проход, сжатие координат и место дерева Фенвика.2 мин12Разложение по битамXOR на отрезке и сумма: когда пометки не существует, задача распадается на двадцать независимых деревьев.2 мин13Дерево слияний и порядковые статистикиВ узле хранится не число, а отсортированный массив: сколько чисел меньше x и какое k-е по величине.3 мин14Дерево и сканирующая прямаяДвумерная задача становится одномерной: события по одной координате, дерево по другой.3 мин15Ошибки в дереве отрезковСписок мест, где дерево ломается молча, и способ проверить своё дерево за пять минут.3 мин16Дерево ФенвикаШесть строк вместо восьмидесяти: суммы, разности, дерево по значениям, спуск по битам и лишние измерения — и чего оно не умеет.5 мин
Корневая декомпозиция
Блоки по корню, отложенные метки, перестроение, прыжки и алгоритм Мо. Структура, которая пишется за десять минут и почти всегда проходит.
1Корневая декомпозицияРазбить массив на блоки по корню, для каждого блока хранить сводку. Запрос разваливается на два огрызка и середину из готовых ответов.3 мин2Корневая с обновлениямиТочечное изменение чинит один блок. Прибавление на отрезке - отложенная метка на целые блоки и пересчёт огрызков.3 мин3Вставки, удаления и перестроениеБлоки как список векторов. Вставка портит один блок, а когда он распухает - всю структуру перестраивают целиком, и это дёшево.2 мин4Прыжки по блокамИз каждой клетки заранее известно, куда она выведет за пределы своего блока и за сколько шагов. Путь длиной n проходится за корень.2 мин5Алгоритм МоЕсли запросы можно прочитать заранее, их выгодно переставить. Тогда границы окна суммарно проходят корень от n на запрос.3 мин6Мо с изменениямиТретья координата — время. Шесть операций вместо четырёх, блок n в степени две трети и оценка n в степени пять третьих.3 мин7Мо на деревеПуть между вершинами превращается в отрезок эйлерова обхода. Вместо добавления и удаления — переключение.3 мин8Тяжёлые и лёгкие вершиныСумма степеней равна 2m, поэтому вершин со степенью больше корня — меньше корня. Отсюда треугольники за m корень из m.3 мин9Корневая или дерево отрезковТаблица выбора и честный разбор того, где корневая проигрывает, а где выигрывает.3 мин
Теория игр
Выигрышные и проигрышные позиции, ретроанализ с ничьими, функция Гранди и сумма игр, игры на деревьях и графах, ним и его варианты, игра Уайтхоффа и поиск закономерностей.
1Выигрышные и проигрышные позицииДвое ходят по очереди, кто не может — проиграл. Вся теория держится на двух правилах, и оба выводятся за минуту.2 мин2Ретроанализ и ничьиКогда в графе позиций есть циклы, рекурсия зацикливается, а исход может быть третьим — ничья. Считается обратным обходом со счётчиками.3 мин3Функция ГрандиПозиции мало приписать «выигрышная или проигрышная»: чтобы складывать игры, нужно число. Это число — mex по достижимым позициям.3 мин4Сумма игр и теорема Шпрага — ГрандиИграем в несколько игр сразу, ход — сходить в одной. Значение суммы равно XOR значений слагаемых.3 мин5Гранди на деревьяхОдна и та же картинка задаёт разные игры. Два правила вычисления, и путать их дорого.3 мин6Принцип слиянияЦикл ломает счёт снизу вверх. Оказывается, весь цикл равносилен чётности числа его рёбер.2 мин7Ним и его родственникиКучи камней и XOR. Плюс три варианта, которые встречаются чаще самого нима: ограничение на ход, мизерный, лестничный.3 мин8Игра УайтхоффаДве кучи, ход — взять из одной или поровну из обеих. Проигрышные позиции задаются золотым сечением.3 мин9Как искать закономерностьЗначения Гранди почти никогда не выводят — их считают перебором, смотрят на таблицу и угадывают. Как это делать не наугад.3 мин10Теория игр: что где применятьКороткая таблица: по формулировке условия — какой аппарат брать.2 мин
Паросочетания
Кун и Хопкрофт — Карп, теорема Кёнига и её следствия, покрытие путями, теорема Дилворта и каталог сведений.
1Паросочетания и алгоритм КунаНабор рёбер без общих вершин. Ищется увеличивающими путями за O(VE), а с двумя эвристиками работает заметно быстрее оценки.3 мин2Хопкрофт — КарпЗа проход находится сразу максимальный набор кратчайших увеличивающих путей. Проходов не больше корня из числа вершин.2 мин3Кёниг, покрытие и независимое множествоМинимальное вершинное покрытие равно максимальному паросочетанию. Отсюда независимое множество, рёберное покрытие и обязательные рёбра.4 мин4Покрытие путями и теорема ДилвортаМинимальное число путей, покрывающих ациклический граф, равно n минус паросочетание. С транзитивным замыканием это теорема Дилворта.2 мин5Сведение к паросочетаниюКаталог приёмов: шахматная раскраска, строки против столбцов, отрезки диагоналей, двоичный поиск снаружи и жадность по весам вершин.3 мин
Декартово дерево
Дерево поиска и куча в одном: split и merge, порядковые статистики, неявный ключ, вставки и переносы кусков, отложенные операции.
Персистентность
Структуры, которые хранят все свои версии: путь вместо копии, персистентное дерево отрезков, префикс как версия, откаты вместо версий.