Материалы для подготовки

Подготовка к олимпиадам по информатике (для продвинутых).

Алгебра:

• Вычисления по модулю. Малая теорема Ферма. Теорема Эйлера

• НОД. НОК. Числовые циклы

• Числа Фиббоначи. Обобщенные числа Фиббоначи. Возведение матрицы в степень. Период Пизано

• Бинарное возведение в степень. Количество перестановок. Количество перестановок с повторениями. Количество сочетаний

• Диофантово уравнение. Расширенный алгоритм Евклида

• Решето Эратосфена. Разложение числа на простые множители. Нахождение степени делителя факториала. Длинная арифметика в фактиризованном виде.

• Алгоритм Миллера-Рабина

• Длинная арифметика. Алгоритм Карацубы

Геометрия:

• Расстояние между двумя точками. Расстояние между точкой и прямой. Расстояние между точкой и плоскостью

• Общее уравнение прямой. Уравнения плоскости

• Точка пересечения двух прямых. Точка пересечения прямой и плоскости

• Проверка двух отрезков на пересечение

• Точки пересечения окружности и отрезка. Точки пересечения сферы и прямой. Точки пересечения двух окружностей

• Площадь многоугольника

• Минимальная выпуклая оболочка. Минимальная выпуклая оболочка в пространстве

Алгоритмы на графах:

• BFS. DFS. Компоненты связности. Топологическая сортировка

• Мосты. Точки сочленения

• DSU. Минимальное остовное дерево. Алгоритм Прима. Алгоритм Краскала

• Компоненты сильной связности. Конденсация графа

• Алгоритм Флойда. Алгоритм Беллмана-Форда. Алгоритм Дейкстры

• Нахождение эйлерова пути и эйлерова цикла в графе

• 2-SAT

• Матричная теорема Кирхгофа

Алгоритмы на деревьях:

• LCA. LCA за O(N) на запрос

• LCA за O(log N) на запрос. Время препроцессинга: O(N*log N)

• LCA за O(1) на запрос. Время препроцессинга: O(N*log N)

• LCA за O(1) на запрос. Время препроцессинга: O(N)

• Эйлеров обход дерева

Потоки и паросочетания:

• Максимальный поток. Минимальный разрез. Алгоритм Эдмонса-Карпа

• Алгоритм Диница

• Алгоритм проталкивания предпотока

• Поток максимальной и минимальной стоимости. Преобразование Джонсона

• Задача о назначениях. Венгерский алгоритм

• Поток с ограничениями на ребра

• Циркуляция минимальной стоимости

• Максимальное паросочетание. Алгоритм Куна

• Покрытие путями ациклического графа

• Максимальное независимое множество в двудольном графе

• Нахождение максимального вершинно-взешенного и реберно-взвешенного паросочетания

• Алгоритм Гомори-Ху

Алгоритмы на строках:

• Префикс-функция. КМП

• Z-функция

• Полиномиальный хэш

• Суффиксный массив с временем построения O(N*log N)

• Суффиксный автомат с временем построения O(N)

• Суффиксное дерево. Алгоритм Укконена

• Алгоритм Манакера

• Бор. Алгоритм Ахо-Корасик

Задачи на запросы:

• Дерево Фенвика. Запросы на поиск максимума, минимума, суммы, k-ой порядковой статистики на дереве Фенвика за время O(log N)

• Дерево отрезков. Сжатое дерево отрезков. Поиск k-ой порядковой статистики при помощи дерева отрезков за время O(log N)

• Дерево сортировки слиянием

• Задача о сумме различных

• Offline-препроцессинг

• Декартово дерево

• Тяжело-легкое разложение дерева

• Sqrt-декомпозиция

• Эвристика «объединить к меньшее с бóльшим»

ДП:

• Задача о рюкзаке

• Задача о нахождении максимальной нулевой подматрицы

• ДП по профилю. ДП по рваному краю

• ДП по выпуклой оболочке (APIO Commando)

• Задача о максимальной возрастающей подпоследовательности

• Расстояние редактирования

• Нахождение k-ого лексикографически пути в ДП

• ДП на дереве. Задача о максимальном паросочетании на дереве

• Перемножение матриц

• Понятие оптимальной стратегии в играх. Функция Шпрага-Гранди.