Материал, мимо которого мы прошли
-2.08.14 День 1.
- Двумерное дерево отрезков
- Дерево сортировки слиянием. поиска k-й порядковой статистики на отрезке за O(log3 n), O(log2 n).
- Персистентный стек.
- Персистентное дерево отрезков.
- Метод сканирующей прямой. Превращение offline-решения в online с помощью персистентности.
- Задача поиска k-й порядковой статистики на отрезке за O(log n).
- Персистентное декартово дерево. RBST.
- Сжатое двумерное дерево отрезков.
-1.08.14 День 2.
- Задача LCA. Решение за log(n) на запрос
- Heavy-Light Decomposition
- Задача Dynamic Connectivity. Решение за q √q, q log2(n)
- Задача Dynamic 2-Connectivity. Решение за q √q, q log(n)
- Выражение операций Build, Add, Merge друг через друга.
- Добавление операции слияния к структурам данных с операцией add.
- Добавление операции слияния к структурам данных с операцией build и без разделения.
0.08.14 День 3.
- СНМ. Реализация в виде набора подвешенных деревьев.
- Ранговая эвристика, оценка сложности запроса.
- Эвристика переподвешивания к корню, амортизированная оценка сложности запроса.
- Обе эвристики вместе, амортизированная оценка сложности запроса.
- Сведение LCA к RMQ±1. Решения за O(n), O(log n) и O(n log n), O(1) (sparse table).
- Решение за O(n), O(1) (Farach-Colton-Bender).
- Сведение RMQ к LCA, решение за O(n), O(1)
- Задача LA (level ancestor). Решения за O(n log n), O(log n) (двоичный подъем) и O(n), O(log n) (long path decomposition).
- Комбинация двух предыдущих решений: решение за O(n log n), O(1).
- Решение за O(n), O(1) (Farach-Colton-Bender): микро- и макровершины, предобработка всевозможных микродеревьев.
1.08.14 День 4.
- Бор.
- Суффиксные ссылки на боре. Автомат Ахо-Корасик.
- Поиск набора образцов в тексте за O(|S| + |T|).
- Полиномиальные хеши. Поиск хеша подстроки за O(1).
- Лексикографическое сравнение строк за O(log n) с использованием хешей.
- Суффиксный массив. Построение за O(n log2 n) с использованием хешей.
- Выбор модуля, парадокс дней рождения.
- Строки Туе-Морса. Доказательство наличия большого числа коллизий на таких строках по модулю, равному степени 2.
- Простые строки. Алгоритм Дюваля.
- Поиск наименьшего циклического сдвига за O(n).
2.08.14 День 5.
- Построение суффиксного массива за O(n log2 n) без использования хешей.
- Оптимизация до O(n log n) с использованием сортировки подсчетом.
- Технические оптимизации:
- использование только одной сортировки на каждом шаге
- останавливаться, когда все классы эквивалентности различны.
- LCP двух строк. Алгоритм Касаи.
- Нахождение LCP двух суффиксов:
- с использованием алгоритма Касаи и структуры данных (O(log n), O(1)),
- сохраняя класссы эквивалентности на каждом шаге построения суффиксного массива. (O(log n)).
- Суффиксное дерево, построение из суффиксного массива за O(n).
- Поиск количества различных подстрок за O(n).
- Поиск подстроки в строке за O(|S| * log n), оптимизация до O(|S| + log n).
4.08.14 День 6.
- Понятие правого контекста подстроки относительно строки, свойства.
- Суффиксный автомат: состояния, переходы, суффиксные ссылки.
- Перестроение автомата при добавлении одного символа.
- Доказательство линейности построения и линейности размера.
- Применения: количество различных подстрок, количество вхождений данной подстроки.
5.08.14 День 7.
- Окончание доказательства линейности построения суффиксного автомата.
- Комплексные числа, арифметика.
- Связь умножения комплексных чисел с полярными координатами на плоскости. Корни из единицы.
- Определение дискретного преобразования Фурье (ДПФ) и обратного ДПФ для последовательности.
- Формулы для ДПФ и обратного ДПФ, проверка того факта, что они являются обратными операциями.
- Схема "разделяй и властвуй" для вычисления ДПФ (алгоритм Cooley-Tukey), оценка сложности.
- Реализация: рекурсивная схема, bit-reverse, нерекурсивная схема, оптимизации.
- Применения: быстрое перемножение многочленов, длинных чисел, поиск подстроки с минимальным расстояним Хэмминга от данной строки.
- Уменьшение количества вычислений ДПФ.
6.08.14 День 8.
- Постановка задачи о максимальном потоке и минимальном разрезе
- Теорема Форда-Фалкерсона. Поиск потока за E|f|.
- Алгоритм Эдмонса-Карпа. Поиск потока за E2V
- Масштабирование. Поиск потока за E2log(Max)
- Алгоритм Куна. Поиск паросочетания за VE.
- Алгоритм Диница. Поиск потока за V2E
- Алгоритм Диница c масштабированием. Поиск потока за VElog(Max)
- LR-поток и LR-циркуляция
7.08.14 День 9.
- Задачи о потоке минимальной стоимости
- Критерий минимальности стоимости потока
- Алгоритм отмены циклов отрицательного веса
- Алгоритм пропускания потока по кратчайшим путям
- Потенциалы Джонсона
- Проталкивание предпотока. Оценка O(V2E) для общего алгоритма
- Проталкивание предпотока. Оценка O(V3) для "поднять и в начало"
8.08.14 День 10.
- Выпуклая оболочка за O(n log n)
- Две ближайшие точки из множества: разделяй и влавствуй за O(n log n)
- Две наиболее удаленные точки: вращающиеся ножницы за O(n)
- Принадлежность точки невыпуклуму многоугольни за O(n): подсчет углов и пускание луча
- Принадлежность точки выпуклуму многоугольнику за O(log n)
- Расстояние от прямой до выпуклого многоугольника, проверка пересечения: O(log n)
- Касательные из точки до многоугольника: O(log n)
- Сумма Минковского. Построение для выпуклых многоугольников за O(n)
- Расстояние между двумя выпуклыми многоугольниками, проверка пересечения и другие применения суммы Минковского
- Сканирующая прямая в геометрии. Проверка наличия пересечения среди n отрезков за O(n log n)
- Локализация: поиск точки в планарном графе, оффлайн и онлайн за O(log n)
- Принадлежность точки невыпуклому многоугольнику за O(log n)
9.08.14 День 11.
- Понятие игры на ацикличном графе.
- Анализ результата игры и количества ходов.
- Понятие прямой суммы игр. Эквивалентность по Гранди.
- Классификация ацикличных игр с точностью до эквивалентности. Вычисление функции Гранди игры.
- Классификация цикличных игр с точностью до эквивалентности. Теория Смитта.
10.08.14 День 12.
- Алгоритм проверки непустоты пересечения n полуплоскостей за O(n) в среднем.
- Алгоритм построения минимального покрывающего круга для n точек за O(n) в среднем.
- Вероятностный алгоритм Каргера для global min-cut.
- Алгоритм Штор-Вагнера для global min-cut.