Материал, мимо которого мы прошли
29.07.13 День 1.
- Персистентный стек.
- Персистентное дерево отрезков.
- Метод сканирующей прямой. Превращение offline-решения в online с помощью персистентности.
- Задача поиска k-й порядковой статистики на отрезке за O(log n).
- Персистентное декартово дерево. RBST.
- Сжатое двумерное дерево отрезков.
30.07.13 День 2.
- Система непересекающихся множеств. Доказательство оценки времени работы.
- Dynamic Connectivity Problem Offline.
- Задача LCA. Метод двоичного подъема.
- Offline-алгоритм поиска LCA с использованием СНМ.
- Разреженные таблицы (Sparse Table).
- Сведение RMQ к LCA за O(n). Построение декартова дерева по отсортированному (по ключам) массиву за O(n).
- Сведение LCA к RMQ±1 за O(n). Эйлеров обход.
- Решение задачи RMQ±1 за O(n), O(1) (алгоритм Фарах-Колтона - Бендера).
- Перемножение битовых матриц с помощью метода четырех русских и битового сжатия.
31.07.13 День 3.
- Z-функция.
- Префикс-функция строки. Бор.
- Префикс-функция для бора - суффиксные ссылки. Автомат Ахо-Корасик.
- Поиск набора образцов с помощью автомата Ахо-Корасик.
- Полиномиальное хеширование строк. Лексикографическое сравнение строк.
- Строки Туе-Морса. Парадокс дней рождения.
- Алгоритм Дюваля.
01.08.13 День 4.
- Поразрядная сортировка.
- Суффиксный массив. Построение с помощью хеширования.
- Алгоритм Карпа-Миллера-Розенберга.
- Алгоритм Касаи-Ли-Аримуры-Арикавы-Парка.
- Поиск подстроки в строке за O(m + log(n)).
- Алгоритм Кяркяйнена-Сандерса.
02.08.13 День 5.
- Суффиксный автомат.
- Правые контексты. Связь состояний автомата и правых контекстов. Свойства вложенности. Дерево правых контекстов.
- Изменение состояний и переходов автомата при добавлении символа.
- Алгоритм построение суффиксного автомата.
- Доказательство линейности времени работы алгоритма построения.
03.08.13 День 6.
- Корневая декомпозиция. Общая идея.
- Груповые операции и запросы
- Корневая декомпозиция запросов. Dynamic [2-]Connectivity problem Offline
- Отложенные операции
- Вставка/удаление в корневую декомпозицию. Split/Merge. Переворот.
05.08.13 День 7.
- Постановка задачи о максимальном потоке и минимальном разрезе
- Теорема Форда-Фалкерсона. Поиск потока за E|f|.
- Алгоритм Эдмонса-Карпа. Поиск потока за E2V
- Масштабирование. Поиск потока за E2log(Max)
- Алгоритм Куна. Поиск паросочетания за VE.
- Алгоритм Диница. Поиск потока за V2E
- Алгоритм Диница c масштабированием. Поиск потока за VElog(Max)
- LR-поток и LR-циркуляция
06.08.13 День 8.
- Две теоремы Карзанова (Алгоритм Диница в сетях с целочисленными пропускными способностями).
- Алгоритм Хопкрофта-Карпа для поиска максимального паросочетания за O(EV1/2).
- Задача о глобальном разрезе. Алгоритм Штор-Вагнера.
- Алгоритм Каргера-Штайна.
- Алгоритм проталкивания предпотока.
- Оценка O(V2E) на время работы произвольного алгоритма проталкивания предпотока.
- Алгоритм "Поднять и в начало". Оценка O(V3) на время работы.
07.08.13 День 9.
- Задача о потоке минимальной стоимости.
- Критерий минимальности стоимости потока (отсутствие отрицательных циклов). Теорема Форда-Фалкерсона.
- Алгоритм дополнения вдоль путей минимальной стоимости.
- Алгоритм отмены циклов отрицательного веса.
- Алгоритм Дейкстры с потенциалами Джонсона.
- Задача о назначениях. Решение с помощью сведения к задаче поиска потока минимальной стоимости.
- Венгерский алгоритм решения задачи о назначениях.
08.08.13 День 10.
- Понятие игры на ацикличном графе.
- Анализ результата игры и количества ходов.
- Понятие прямой суммы игр. Эквивалентность по Гранди.
- Классификация ацикличных игр с точностью до эквивалентности. Вычисление функции Гранди игры.
- Классификация цикличных игр с точностью до эквивалентности. Теория Смитта.
11.08.13 День 11.
- Проверка принадлежности точки выпуклому многоугольнику.
- Проверка принадлежности точки невыпуклому многоугольнику.
- Поиск двух пересекающихся отрезков.
- Поиск двух ближайших точек.
- Поиск дух наиболее удаленных точек.
- Проверка пересечения прямой и выпуклого многоугольника.
- Алгоритм проверки непустоты пересечения полуплоскостей.
12.08.13 День 12.
- Алгоритм пересечения полуплоскостей.
- Алгоритм построения минимальной охватывающей окружности.
- Умножение длинных чисел. Алгоритм Карацубы.
- Вычеты по простому модулю. Поиск генератора.
- Дискретное преобразование Фурье.
- Алгоритм Кули-Туки для быстрого преобразования Фурье.
- Нерекурсивная реализация БПФ.