олимпиады

SRT Приём Двоичный поиск по ответу Если проверить ответ легче, чем найти, и проверка монотонна, — ищем ответ делением пополам. O(log D · стоимость проверки) 2 задачи SRT Алгоритм Троичный поиск Вершина унимодальной функции: сравнить две точки и отбросить часть отрезка. И почему золотое сечение лучше. O(log(L/ε)) вычислений функции 2 задачи DS Приём Монотонный стек Стек с упорядоченными значениями: ближайший больший элемент и наибольший прямоугольник за O(n). O(n) 2 задачи DS Приём Корневая декомпозиция Блоки по √n: целые отвечают сразу, разрезанные — поклеточно; O(√n) там, где дерево отрезков не складывается. И порядок Мо. O(√n) на запрос; Мо — O(n√q) на все 1 задача DS Структура данных Персистентные структуры Каждое изменение — новая версия, старые живы; копируется только путь от корня. Медиана любого периода — разность двух версий. O(log n) на изменение и запрос 1 задача DS Структура данных Декартово дерево Ключ и случайный приоритет: глубина O(log n) в среднем, split и merge, массив с разворотом куска за O(log n). O(log n) в среднем на поиск, вставку, удаление, split и merge 1 задача DS Структура данных Дерево отрезков Минимум, максимум и сумма на любом отрезке с изменениями на ходу: оба действия за O(log n). O(log n) на запрос и на изменение 2 задачи DS Структура данных Дерево Фенвика Суммы на префиксе с изменениями за O(log n) в одном массиве: блоки длиной в младшую единицу номера. O(log n) на сумму префикса и на изменение 2 задачи DS Структура данных Разреженная таблица Минимум любого отрезка за O(1) после O(n log n) подготовки: два перекрывающихся блока длиной 2^k. O(1) на запрос, O(n log n) на построение 2 задачи GRA Алгоритм Поиск в ширину Обходит граф слоями и находит пути с наименьшим числом рёбер за O(V + E). O(V + E) 2 задачи GRA Алгоритм Компоненты сильной связности Группы вершин, где из любой можно дойти до любой: Тарьян за один обход, Косараю за два, O(V + E). O(V + E) 2 задачи GRA Алгоритм 2-SAT Условия «a или b»: граф следствий, компоненты сильной связности и ответ за O(n + m); на настоящих нотах. O(n + m) 1 задача GRA Алгоритм Мосты и точки сочленения Улицы и перекрёстки, без которых граф распадается: один поиск в глубину с числами tin и low, O(V + E). O(V + E) 2 задачи GRA Алгоритм Алгоритм Флойда — Уоршелла Кратчайшие пути между всеми парами вершин за O(n³): динамика по разрешённым пересадкам. O(n³) 2 задачи GRA Алгоритм Максимальный поток Наибольший поток из истока в сток и узкое место сети: Форд — Фалкерсон, Эдмондс — Карп, теорема о разрезе. O(V E²) 2 задачи GRA Алгоритм Алгоритм Диница Наибольший поток фазами: слоистая сеть, блокирующий поток, указатели; O(V²E), а в единичных сетях O(E√V). O(V² E) 2 задачи GRA Алгоритм Паросочетания в двудольном графе Наибольшее число пар в двудольном графе: Кун, Хопкрофт — Карп, теоремы Кёнига и Холла. O(E √V) 2 задачи GRA Алгоритм Поток наименьшей стоимости Поток с наименьшей суммарной ценой: круги отрицательной стоимости, кратчайшие пути с потенциалами, транспортная задача 1930 года. O(F · E log V) 2 задачи GRA Алгоритм Эйлеров путь Пройти каждое ребро ровно раз: правило нечётных вершин и алгоритм Хирхольцера за O(E). O(V + E) 3 задачи GRA Алгоритм Наименьший общий предок Общий предок двух вершин дерева: двоичный подъём за O(log n), обход Эйлера за O(1), Тарьян офлайн. O(log n) на запрос 2 задачи GRA Алгоритм Тяжёлые пути Запросы на путях дерева: тяжёлые пути режут любой путь на O(log n) отрезков массива под деревом отрезков. O(log² n) на запрос 1 задача GRA Алгоритм Центроидная декомпозиция Делим дерево центроидами: log₂ n уровней, и ближайшая отмеченная вершина — за O(log n) после каждой отметки. O(log n) на отметку и на вопрос 1 задача STR Алгоритм Префикс-функция и КМП Все вхождения образца за O(n + m) без шагов назад по тексту; префикс-функция находит и период строки. O(n + m) 2 задачи STR Алгоритм Z-функция Сколько букв от каждой позиции совпадает с началом строки — за O(n); поиск, периоды и повторы подряд. O(n) 2 задачи STR Приём Полиномиальный хеш Хеш любого куска строки за O(1) из хешей начал: сравнение подстрок, окна, общие начала — с оценкой вероятности ошибки. O(n) подготовка, O(1) хеш куска 2 задачи STR Алгоритм Алгоритм Ахо — Корасик Все вхождения тысяч слов за один проход: бор из слов плюс ссылки отказа, как у префикс-функции. O(n + Σ|wᵢ| + z) 1 задача STR Структура данных Суффиксный массив Отсортированные хвосты текста: поиск двоичным поиском, повторы и число разных кусков по соседям. O(n log n) 2 задачи STR Структура данных Суффиксный автомат Все подстроки текста в графе из меньше чем 2n состояний: склейка фразы из кусков «Онегина» за один проход. O(n) 2 задачи STR Алгоритм Алгоритм Манакера Все палиндромы строки за O(n): зеркало внутри самого правого палиндрома; фаги и палиндромы в их ДНК. O(n) 2 задачи DP Приём Динамическое программирование Сводим задачу к подзадачам, решаем каждую один раз и храним ответы в таблице. состояния × переходы 2 задачи DP Алгоритм Задача о рюкзаке Лучший набор вещей под ограничение по весу: таблица n × W и путь по ней назад. O(n·W) 3 задачи DP Алгоритм Наибольшая возрастающая подпоследовательность Самая длинная растущая цепочка элементов в исходном порядке: пасьянс и двоичный поиск за n log n. O(n log n) 2 задачи DP Приём Динамика на отрезках Состояние — отрезок [i, j], переход — где его разрезать: дерево поиска, порядок умножения матриц, распил. O(n³) 2 задачи DP Приём Динамика на деревьях Ответ поддерева — из ответов детей: проход от листьев к корню, а для всех корней сразу — перерасчёт с корня. O(n) 2 задачи DP Приём Динамика по маскам Состояние — подмножество, записанное битами числа: точный коммивояжёр, назначения, раскладки по профилю. O(2ⁿ · n²) для коммивояжёра 2 задачи DP Приём Динамика по цифрам Счастливые билеты в любом диапазоне за проход по цифрам: 55 252 из миллиона и любой из 10¹⁸ — за миллисекунду. O(D · 10 · S) 2 задачи DP Приём Convex hull trick Минимум прямых вместо перебора: 1776 тестов каталога по запускам песочницы — и квадратичная динамика становится линейной. O(n) 2 задачи DP Приём Оптимизации Кнута и «разделяй и властвуй» 45 тысяч городов на карте по классам населения: 3,5 млн вычислений вместо пяти миллиардов — потому что лучший разрез монотонен. O(k · n log n) 2 задачи PAR Приём Жадные алгоритмы Лучший шаг сейчас без оглядки назад: когда это оптимально, когда почти, и как это доказать. обычно O(n log n): сортировка или куча 2 задачи PAR Приём Перебор с возвратом Строить решение по шагу, сразу проверять и отступать из тупика: судоку, ферзи, раскраски. O(bᵈ) в худшем случае 2 задачи PAR Приём Разделяй и властвуй Разрезать, решить части так же, склеить; сколько это стоит — по уровням дерева рекурсии и основной теореме. T(n) = a·T(n/b) + f(n) 2 задачи PAR Приём Встреча посередине Перебрать две половины по отдельности и встретиться в отсортированной таблице: 2·2^(n/2) шагов вместо 2ⁿ. O(2^(n/2) · n) 2 задачи NUM Алгоритм Решето Эратосфена Все простые до n за O(n log log n): вычёркиваем кратные каждого простого, начиная с его квадрата. O(n log log n) 2 задачи NUM Алгоритм Тест Миллера — Рабина Простота числа за k возведений в степень: основания-свидетели ловят составное, лжецов не больше четверти. O(k log³ n) 2 задачи NUM Алгоритм ρ-алгоритм Полларда Делитель p числа n за ~√p шагов: цикл по модулю неизвестного p, черепаха и заяц, НОД. O(√p) умножений по модулю n 1 задача NUM Алгоритм Длинная арифметика Числа длиннее машинного слова: цифры по основанию 10⁹ или 2³⁰, переносы, столбик и дорогая печать. сложение O(n), умножение и деление столбиком O(n²), печать в десятичной записи O(n²) или O(M(n) log n) 2 задачи NUM Алгоритм Быстрое преобразование Фурье Дискретное преобразование Фурье за O(N log N): спектры, свёртки, умножение многочленов и больших чисел. O(N log N) 2 задачи NUM Алгоритм Матрицы и рекуррентности Степень матрицы: пути длины k в графе, линейные рекуррентности, матрица переноса и цепи Маркова. O(m³ log k) для A^k размера m × m 2 задачи GEO Приём Векторы и ориентация Знак векторного произведения — поворот налево или направо; на нём стоит почти вся вычислительная геометрия. O(1) на один поворот 2 задачи GEO Алгоритм Выпуклая оболочка Наименьший выпуклый многоугольник, содержащий все точки, за O(n log n). O(n log n) 2 задачи GEO Алгоритм Площадь многоугольника Площадь по координатам вершин: сумма xᵢyᵢ₊₁ − xᵢ₊₁yᵢ, а её знак — направление обхода. O(n) 2 задачи TEC Приём O-большое Как растёт работа вместе с данными: O, Ω и Θ, правила оценки кода и где асимптотика обманывает. оценка — по тексту программы 1 задача TEC Приём Быстрый ввод и вывод Миллион чисел за десятки миллисекунд вместо секунды: чтение целиком, буфер и одна запись вывода. O(размер входа) 1 задача TEC Приём Префиксные суммы Сумма любого отрезка за O(1) после одного прохода; двумерный вариант считает сумму любого прямоугольника картинки. O(n) на построение, O(1) на запрос 2 задачи TEC Приём Два указателя Два индекса движутся только вперёд и заменяют перебор пар или отрезков одним проходом за O(n). O(n) 2 задачи TEC Приём Сколько операций в секунду Шаги алгоритма, делённые на скорость языка, — и вы знаете, уложится ли программа, ещё до того, как её написали. оценка — секунды в уме 1 задача TEC Приём Мемоизация Запомнить ответ функции для каждого набора аргументов, чтобы не считать его заново: экспонента превращается в многочлен. O(число разных аргументов × работа на один вызов) 2 задачи TEC Приём Сжатие координат Значения до миллиарда заменить их номерами по порядку — и строить массивы и деревья по номерам. O(n log n) на сжатие 2 задачи TEC Приём Битовые трюки Число как набор флажков: маски, младшая единица, подсчёт единиц и перебор подмножеств без рекурсии. O(1) на операцию над словом 1 задача TEC Приём Отсечения Не открывать ветки, где заведомо нет ответа лучше: рекорд, порядок, симметрия, оценки снизу. O(kⁿ) в худшем случае 2 задачи