Билеты

1. Персистентность + Segment Tree Beats. Персистентное ДО, как работает, асимптотика по времени и памяти. STB пример решения задач, с доказательством ассимптотики: %=, = в точке, сумма. Min=, сумма, max.
2. Геометрия. Поиск касательных к выпуклому многоугольнику из точки. Сумма Минковского, алгоритм подсчета. Проверка пересечения полуплоскостей
3. Теория чисел. Решето Эратосфена за линию. Дискретное логарифмирование. Первообразный корень, поиск первообразного корня из числа по модулю. Тест Рабина-Миллера. Алгоритм ро-Полларда.
4. FFT. Идея, комплексные корни из единицы. Прямое преобразование за O(n * log n). FFT по модулю.
5. Ахо-Корасик. Общая идея, бор. Определение суффсылок и суперсуффсылок. Построение. Динамический Ахо-Корасик с добавлением/удалением строк в словарь.
6. Суффиксный массив, построение за O(n * log n). LCP, Алгоритм Касаи-Аримуры-Арикавы-Ли-Парка
7. Суффиксный автомат: вершина автомата (что хранит), структура автомата (переходы и суфссылки), что такое правый контекст, алгоритм построения суфавтомата.
8. Центроидная декомпозиция, определение и поиск центроида, примеры задач. Heavy-light декомпозиция, оценка времени работы, операции в поддереве
9. Оптимизации динамики. CHT, LiChao принцип работы, ассимптотика. Оптимизация Кнута, Разделяй и властвуй, 1D1D, время работы, условия для корректной работы, асимптотика. Лямбда оптимизация, условие выпуклости для корректной работы алгоритма.
10. Slope Trick. Применение Slope Trick в задаче "Настойки". (max, +) - свертка. Сделать разность соседних не более h по модулю за минимальное количество действий.
11. Потоки: Что такое сеть, остаточная сеть, слоистая сеть. Алгоритмы Форда-Флакерсона, Эдмондса-Карпа, Диница. Асимптотики работы алгоритмов, их доказательства. Решение задачи паросочетания потоками.
12. Стоимостные потоки: Алгоритм поиска MCMF, доказательство корректности. Потенциалы Джонсона - начальная расстановка, их изменения, доказательства.