Учебник

Разборы алгоритмов: как приём устроен, когда он уместен и на чём с ним ошибаются. Читается отдельно от курсов.

Основы

То, без чего не обойтись ни в одной теме: как оценить решение до того, как оно написано.

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Почему быстрее n log n нельзяДоказательство нижней оценки через дерево решений — и что именно оно запрещает, а что нет.4 мин 7Сортировка подсчётом и устойчивостьКогда сравнения не нужны вовсе. И что такое устойчивость — на примере очереди в поликлинику.4 мин 8Поразрядная сортировкаПодсчёт, применённый по разрядам. Как отсортировать миллионы чисел за четыре прохода и почему без устойчивости это не работает.4 мин 9Сортировки в C++sort, stable_sort, nth_element, компараторы и лямбды. И контракт, нарушение которого роняет программу.4 мин 10Сортировки в 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 мин

Линейные алгоритмы

Приёмы, которые заменяют перебор пар одним проходом: префиксные суммы, два указателя, стек и очередь с минимумом.

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Мемоизация и ленивая динамикаРекурсия плюс массив ответов. Экспонента превращается в линию, а порядок обсчёта динамики становится не нужен.4 мин 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Графы: определения и хранениеТри способа хранить граф и таблица, по которой выбирают между ними. Плюс минимум терминов, без которых дальше не обойтись.4 мин 2Дерево: четыре определенияВ условии могут написать любое из четырёх — и все они об одном и том же. Почему они эквивалентны и что из этого следует.4 мин 3Обход в глубинуЧетыре строки, из которых вырастает половина раздела. Компоненты связности, времена входа и выхода, и что делать с глубиной рекурсии.5 мин 4Двудольность и раскраска в два цветаПокрасить граф в два цвета или доказать, что нельзя. Критерий через нечётные циклы и почему на трёх цветах всё ломается.4 мин 5Дерево обхода и поиск цикловРёбра графа распадаются на четыре вида, и по виду ребра сразу видно, есть ли цикл. Разные критерии для ориентированного и неориентированного случая.4 мин 6Топологическая сортировкаВыстроить вершины в ряд так, чтобы все рёбра шли слева направо. Через времена выхода и через степени входа.4 мин 7Диаметр дереваДва обхода вместо перебора всех пар. Алгоритм в пять строк, доказательство длиннее алгоритма — и почему в общем графе так нельзя.3 мин 8Компоненты сильной связностиАлгоритм Косарайю: два обхода и транспонированный граф. Почему работает именно эта комбинация и ни одна другая.5 мин 9Мосты и точки сочлененияОдна величина up[v] решает обе задачи. Вывод формулы, отдельный случай корня и ловушка с кратными рёбрами.4 мин 10Рёберная двусвязностьСжать компоненты, оставить мосты — и любой граф превращается в дерево. Приём, который сводит задачи на графах к задачам на деревьях.3 мин 11Алгоритм ДейкстрыКратчайшие пути из одной вершины во взвешенном графе. Две реализации, одна забытая строчка — и квадрат вместо логарифма.6 мин 12Алгоритм ФлойдаКратчайшие пути между всеми парами в четыре строки. Восстановление пути, отрицательные циклы и почему порядок циклов менять нельзя.5 мин 13Граф состоянийВершина — не обязательно кружок на картинке. Приём, который превращает задачу «за сколько шагов» в обычный обход.6 мин 14Неявный графРёбер может быть квадрат, а нужных из них — линия. Как не построить лишнего и что делать с координатами до миллиарда.4 мин 15Дерево кратчайших путейИз $m$ рёбер для кратчайших путей важны $n-1$. Плюс запуск обхода сразу из множества вершин.4 мин 16Бинпоиск и кратчайшие путиМаксимизируется минимум — значит, внутри проверки будет обход. Разбор задачи, где это видно целиком.4 мин 17Алгоритм Форда — БеллманаКратчайшие пути при отрицательных весах. Обычная динамика, с которой исторически и начался сам термин.4 мин 18Единственность топологической сортировкиПорядок единственный тогда и только тогда, когда между каждой парой соседей в нём есть ребро. Проверяется одним проходом.2 мин 19Кактусы и цикл чётной длиныЕсли два цикла делят ребро, чётный цикл найдётся сам. Остаётся случай, когда циклы не пересекаются, — а это кактус.3 мин 20Восстановление массива по суммам на отрезкахУсловия вида «сумма на отрезке равна x» — это рёбра графа. Обход даёт и ответ, и проверку на противоречивость.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 мин

Отрезки и сканирующая прямая

Отрезок как пара событий: покрытие, объединение, вложенность, дуги на окружности и переход на плоскость.

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Задачи на строки: какой приём когдаЧетыре инструмента с сильно разными сильными сторонами. Таблица выбора и типовые постановки.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Динамика на ациклическом графеТопологический порядок — это и есть порядок пересчёта. Плюс разбор, что такое «динамика вперёд» и «назад».3 мин 4Подсчёт путейПутей может быть экспоненциально много, а посчитать их — линия. И приём, который сводит «через набор вершин» к произведению.3 мин 5Динамика по маскамПодмножество как число. Экспонента, но приемлемая — до двадцати с небольшим элементов.4 мин