1. Билет
1. Теорема Эйлера (для планарного графа)
2. RSQ и RMQ на меняющейся матрице, 2D деревья отрезков и Фенвика [O(n²), O(log²n)].
3. Трансверсальный матроид (паросочетания) (определение, док-во того, что это матроид, алгоритм, который из этого следует)
2. Билет
1. Задача о назначениях, транспортная задача (формулировки задач, сведение их к mincost потоку)
2. Функция Смита. Способ подсчета за O(EsqrtE). Доказательство LOSE/WIN/DRAW. bonus: Доказательство XOR-а.
3. Задачи: Поиск слов в тексте, наибольшая общая подстрока, наибольший подпалиндром (все они решаются хэшами за O(NlogN)).
3. Билет
1. Полиномиальный хэш от строки. А также подсчет хэша от подстроки, как суммы на отрезке.
2. 2 метода Online поиска LCA (двоичный подъем [O(nlogn), O(logn)] и Эйлеров обход дерева [O(n), O(logn)] а также [O(nlogn), O(1)] с помощью SparseTable)
3. Суффиксный массив хэшами за O(Nlog²N), сравнение хэшами строк на больше меньше. LCP за O(NlogN). Суффиксный массив цифровой сортировкой за O(N²)
4. Билет
1. Лемма Холла (только формулировка)
2. Док-во невозможности r-приближения задачи коммивояжера в графе, в котором не выполняется неравенство треугольника при P != NP (сведение к задаче про гамильтонов цикл)
3. Обучение Нейрона с помощью Градиентного спуска.
5. Билет
1. Игры на ацикличных графах = динамическое программирование. O(E). LOSE/WIN, максимизировать/минимизировать число ходов.
2. Пути в дереве. Веса ребер дерева не меняются, RSQ и RMQ (RSQ = [O(n), O(1)] + LCA, RMQ = [O(n), O(logn)] + LCA).
3. Раскраска ребер двудольного графа в max Degee цветов.
6. Билет
1. MST (Прим, Краскал) (время работы, собственно алгоритм, без док-во)
2. Алгоритм Куна (отличие от базого алгоритма, bonus: док-во).
3. RSQ: Меняющийся массив, дерево Фенвика [O(n), O(logn)], собственно дерево, преимущество над деревом отрезков, bonus: док-во корректности
7. Билет
1. floyd (время работы, реализация)
2. Графовый матроид (определение, док-во того, что это матроид, алгоритм, который из этого следует)
3. Offline поиск LCA (алгоритм Тарьяна, O(n*), собственно алгоритм, рассказ про СНМ (хранить, как лес + сжатие путей + подвешинвать меньшее к большему), bonus: док-во корректности работы)
8. Билет
1. Полиномиальный хэш от строки. А также подсчет хэша от подстроки, как суммы на отрезке.
2. 2-SAT: Жадное решение за O(VE), bonus: док-во.
3. Операции с декартовом деревом по явному ключу: Insert, Delete, K-th, Add(L, R), GetSum(L, R) (1) Выразить эти операции через Split и Merge (2) реализовать их независимо.
9. Билет
1. Укладка в R³, на сфере
2. Обучение Нейрона с помощью Л.П (если все неравенства разрешими, если не все разрешимы - 2 метода = наращивать, или удалять лишние)
3. Алгоритм Диница (bonus: док-во времени работы O(VE²))
10. Билет
1. Задача классификации. Что такое нейрон. Разделение "хорошего" и "плохого" на >= 2 и <= 1 (просто сказать, что такое Нейрон)
2. КД-дерево [O(NlogN), O(sqrtN)], использует O(N) памяти. Преимущество над 2D деревом отрезков (не память). bonus: Док-во времени работы.
3. Теорема о дополняющем чередующемся пути для паросочетания в произвольном графе.
11. Билет
1. Las-Vegas (про самое часто встречающееся число, про подобные прямоугольники)
2. Декартово Дерево по неявному ключу. Add(L, R), GetSum(L, R), Reverse(L, R), Insert(i), Delete(i) (что из этого умеет дерево отрезков, что нет?)
3. Алгоритм Масштабирования потока (bonus: док-во времени работы O(E²log))
12. Билет
1. Вершинные поток и разрез. Поток и разрез (реберные и вершинные) в неорграфе.
2. RSQ, RMQ: Меняющийся массив, дерево отрезков [O(n), O(logn)], преимущество над деревом Фенвика.
3. Функция Гранди. Способ подсчета за O(E). Применение. Доказательство LOSE/WIN. bonus: Доказательство XOR-а.
13. Билет
1. Паросочетание, контролирующее множество, независимое множество (определения, как соотносятся их размеры, без док-ва)
2. Дейкстра с потенциалами для поиска MinCost flow
3. Iterative Deepening. Связь dfs-а и bfs-а. Почему dfs + Iterative Deepening работает не дольше bfs-а? Автоматический подбор параметров. Iterative Increasing K в билете выше "Выбор первых K ребер".
14. Билет
1. Теорема Брукса (про вершины, формулировка). Док-во того, как можно всегда покрасить в D+1 цвет.
2. Меморизация в переборе: проблемы в случае решения задачи "поиск кратчайшего по весу пути". Решение проблемы.
3. Градиентный спуск, случайный поиск, метод Ньютона (в R, в Rⁿ). Выбор направления, выбор расстояния.
15. Билет
1. Троичный поиск (связь с двоичным поиском и производной)
2. Эвристика Полларда. O(N^1/4). bonus: Док-во времени работы.
3. MST x 2, объянение, почему на практике погрешность меньше теор. оценок, bonus: MST x 3/2 (алгоритм Кристофилдса)
16. Билет
1. Сжатый бор, сжатое суффиксное дерево, получение из суф.массива с LCP за O(N)
2. Алгоритм Эдмондса (сжатие соцветий). Реализация за O(V⁴). bonus: док-во корректности работы.
3. Локальные оптимизации для Коммивояжера (собственно хотя бы 2 локальных оптимизации, док-во конечности процесса, поиск очередной оптимизации за O(N))
17. Билет
1. Док-во того, что K_3,3 и K₅ не планарны. Теорема Куратовского (только формулировка)
2. Алгоритм Эдмондса (поиск в ширину, bonus: док-во времени работы O(VE²))
3. Каргер-Штейн (собственно метод, оценка времени работы O(N⁴*log), улучшение, bonus: оценка времени работы O(N²*log²))
18. Билет
1. Теорема Визинга (про ребра, только формулировка)
2. Теорема Форда-Фалкерсона (max F = min C)
3. Векторный матроид (определение, док-во того, что это матроид, алгоритм, который из этого следует)
19. Билет
1. поиск отрицательного цикла (любой из двух вариантов - или через Флойда, или через Форда-Беллмана)
2. Лемма о дополняющем пути (и алгоритм поиска паросочетания за O(VE), который из нее следует).
3. Поиск вещественных корней многочлена. Время работы = O(N²log)
20. Билет
1. Генетический алгоритм (мутации, скрещивание, отличие от Отжига и Локальных оптимизаций). Дать общее описание.
2. Покрытие дерева путями, сведение запроса на пути к 2D запросу. Решение задач RMQ и RSQ за [O(n), O(log²n)]
3. Покрытие ацикличного графа min числом цепей (сведение к паросочетанию в двудольном графе).
21. Билет
1. ford-bellman, реализация тремя циклами, реализация с break-ом, реализация с очередью.
2. LCP для суффиксного массива за O(N). Алгоритм Касаи для суффиксов. bonus: Случай циклических сдвигов.
3. [L,R] потоки (решение mincost потоком, решение обычным потоком)
22. Билет
1. Бинарный поиск (поиск корней функции, поиск числа в массиве)
2. RSQ, RMQ: Неменяющийся массив [O(n), O(logn)], Sparse table [O(nlogn), O(1)]. RSQ и RMQ на неменяющейся матрице [O(n²), O(1)] для RSQ и [O(n²log²n), O(1)] для RMQ.
3. Прибавление и присваивание на отрезке (в дереве отрезков, время на 1 операцию = O(logn)).
23. Билет
1. Решение задачи "Кто автор этого стиха? Пушкин или Лермонтов?" (сказать, как это делать с помощью одного Нейрона)
2. Декартово Дерево по явному ключу. Операции Split и Merge.
3. Дерево отрезков декартовых деревьев (на примере задачи "сколько чисел на отрезке [i,j] имеют величину от L до R").
24. Билет
1. bfs (время работы, реализация, док-во корректности)
2. Ретроанализ, игры на графах с циклами. O(E). LOSE/WIN/DRAW, максимизировать/минимизировать число ходов.
3. Матроиды. Определение. Алгоритм Радо-Эдмондса. bonus: Док-во.
25. Билет
1. Теорема Дилворта. Формулировка. Док-во неравенства в одну сторону.
2. Квадродерево на матрице [O(n²), O(n)]. Преимущество над 2D деревом отрезков, bonus: док-во времени работы.
3. Веса ребер дерева меняется, RSQ за [O(n), O(logn)] (Эйлеров обход + фишечка)
26. Билет
1. Алгоритм раскраски вершин планарного графа в 6 цветов.
2. 2-SAT: Решение за O(E). Док-во времени работы. bonus: Док-во корректности.
3. Лемма Татта-Берджа. Формулировка. Док-во неравенства в одну сторону. bonus: Док-во неравенства в другую сторону.
27. Билет
1. Бор. Суф.дерево. Способы хранения бора (массив, список, дерево поиска, хэш-таблица, общая хэш-таблица для всех вершин).
2. Алгоритм Ахо-Корасика. Сам алгоритм. (1) построение полного автомата next[vertex, char] (2) версия с линейной памятью, bonus: док-во времени работы в (2).
3. Локальные оптимизации. Оптимизация произвольной функции f : AnySpace → R. Cлучайный поиск. Градиентный спуск. Оптимизация для задачи коммивояжера.
28. Билет
1. Поток, разрез (определение,)
2. Усовершенствованные поиски для f : R → R (2 варианта, основная мысль = разделить отрезок на ~100 частей )
3. MinCost поток. Отсутствие отрицательных циклов. Лемма о дополняющем пути для MinCost потока.
29. Билет
1. Monte-Karlo (собственно метод)
2. Алгоритм разбиения графа на грани за O(E). Выделение внешних граней (смотрим на знак площади грани).
3. Алгоритм Укконена за O(N). Сам алгоритм. bonus: док-во времени работы.
30. Билет
1. dfs (время работы, реализация, док-во корректности)
2. Отжиг. Сам процесс. Отличие от локальных оптимизаций. На примере f : R → R. bonus: На примере задачи "ограничить на плоскости max число точек веревкой длины L".
3. Simplex метод. bonus: Реализация Simplex метода.
31. Билет
1. Связь перебора и жадности. Что лучше? Сортировка ребер в переборе. Выбор первых K ребер.
2. Тест Ферма, тест Миллера-Рабина. O(logN). Док-во корректности отсечений.
3. Алгоритм Демукрона. Собственно алгоритм, bonus: разбор всех крайних случаев и док-во времени работы O(N²).
32. Билет
1. Решето Эратосфена = O(NloglogN), описание алгоритма. bonus: док-во времени работы.
2. 2D дерево отрезков (дерево строится на N точках, [O(NlogN), O(log²N)]. Использует O(NlogN) памяти
3. Nearest (просто описание аллгоритма). bonus: док-во того, что Nearest не хуже построения MST Примом.
33. Билет
1. Формулировка задач 2-SAT, 3-SAT.
2. Алгоритм Хопкрофта-Карпа за O(EsqrtV), bonus: док-во времени работы
3. Паросочетание в произвольном графе. Рандомизированный алгоритм (на основе алгоритма построения паросочетания в двудольном графе)
34. Билет
1. RSQ: Неменяющийся массив [O(n), O(1)]
2. Построение за O(N) декартова дерева по неявному ключу
3. Разбиение путей дерева через LCA на 2 вертикальных, Offline и Online задачи.