11 января 2020 Геометрия #1
Расстояние от точки до прямой.
Пересечение прямых.
Пересечение прямой и окружности.
Пересечение двух окружностей.
Поиск касательных к окружности.
Проверка на принадлежность точки многоугольнику за \(O(n)\). Два способа: сумма углов и луч.
Алгоритм Джарвиса.
Алгоритм Грэхема.
Алгоритм Эндрю.
Алгоритм Чана.
Поиск пары пересекающихся отрезков за \(O(n \log n)\).
Локализация точки в выпуклом многоугольнике за \(O(\log n)\) на запрос.
Поиск касательных из точки к выпуклому многоугольнику за \(O(\log n)\) на запрос.
Пересечение прямой с выпуклым многоугольником за \(O(\log n)\) на запрос.
Локализация точки в невыпуклом многоугольнике за \(O(\log n)\) на запрос.
Поиск двух ближайших точек в 2D.
Пересечение полуплоскостей за \(O(n^2)\).
18 января 2020 Регион
25 января 2020 Геометрия #2
Поиск двух ближайших точек в 3D.
Вращающийся scanline. Запросы количества точек в полуплоскости. \(O(n^2 + q \log n)\). Возможность применения корневой.
Сумма Минковского и ее применения.
Квадродерево.
Проецирование на случайную прямую.
Проверка на непустоту пересечения полуплоскостей за \(O(n)\).
Поиск минимальной покрывающей окружности за \(O(n)\).
Пересечение полуплоскостей за \(O(n \log n)\).
Триангуляция методом отрезания ушей за \(O(n^2)\)
Диаграмма Вороного за \(O(n^2)\).
Диаграмма Вороного за \(O(n \log n)\).
Триангуляция Делоне.
01 февраля 2020 Строки #2
Суффиксный массив за \(O(n)\).
Дерево палиндромов.
Суффиксный автомат.
Суффиксное дерево.
8 февраля 2020 Графы #2
Минимальные остовы.
Алгоритм Прима.
Алгоритм Крускала.
Алгоритм Борувки.
Поиск мостов онлайн.
Проведение ребер на отрезке.
СНМ.
15 февраля 2020 Математика #3
Теорема Люка.
Функция Мёбиуса.
Свертка Дирихле.
Первообразный корень и его поиск.
Поиск квадратного корня по простому модулю за \(O(\log p)\).
Троичная сбалансированная система счисления.
Битовые свертки: xor
Hockey-stick identity и подсчет различных сумм в треугольнике Паскаля.
Алгоритм Карацубы.
Введение в комплексные числа. Применение комплексных чисел в геометрии.
Быстрое преобразование Фурье.
Теоретико-числовое преобразование Фурье.
Применение Фурье к решению задач.
22 февраля 2020 Потоки #1
Теорема Форда-Фалкерсона и соответствующий алгоритм.
Алгоритм Эдмондса-Карпа.
Масштабирование для Форда-Фалкерсона и Эдмондса-Карпа.
Декомпозиция потока за \(O(E^2)\) и за \(O(VE)\).
LR-потоки.
29 февраля 2020 Потоки #2
Алгоритм Диница.
Масштабирование для Диница.
Оценки Карзанова.
Поиск величины максимального потока в планарном графе.
Стоимостные потоки. Форд-Беллман на очереди, Дейкстра с потенциалами.
7 марта 2020 Открытая
14 марта 2020 Интерактивки Контест
21 марта 2020 Неточные алгоритмы
Алгоритм отжига.
Генетический алгоритм.
Монте-Карло.
Потоковый алгоритм поиска количества различных.
28 марта 2020 Структуры данных #4
Что такое амортизированное время работы?
Метод потенциалов.
Splay-дерево.
Link-cut.
ДО + (ДД/Splay) для dynamic records.
Биномиальная куча.
Фибоначчиева куча.
4 апреля 2020 Паросочетания
Венгерский алгоритм.
Алгоритм сжатия соцветий (поиск максимальных паросочетаний в произвольных графах).
Взвешенное паросочетание в произвольном графе.
11 апреля 2020 Всеросс
18 апреля 2020 Графы #3
Алгоритм двух китайцев.
Дерево доминаторов.
Гамма-алгоритм проверкии графа на планарность.
25 апреля 2020 Потоки #3
Алгоритм проталкивания предпотока
Алгоритм проталкивания предпотока для стоимостного потока
Алгоритм Каргера-Штейна
Алгоритм Штор-Вагнера
2 мая 2020 Матроиды
Определение и основные утверждения. Примеры матроидов.
Алгоритм Радо-Эдмондса поиска базы минимального веса.
Пересечение матроидов.
09 мая 2020 Алгоритмы во внешней памяти
Общие представления. Задачи поиска минимума, переворота, сортировки, join.
List ranking.
Список с возможностью перехода к \(k\)-му следующему за \(O(k/B)\).
B-дерево.
Heap во внешней памяти.
BFS во внешней памяти.
Мин. остов во внешней памяти.