วีดีโอ

Динамическое программирование на подотрезках, поддеревьях, подмножествах. Задача нахождения гамильтонова цикла. Задача коммивояжёра. Задача о количестве рюкзаков, необходимых для переноса данного множества предметов. Meet-in-the-middle. Задача о рюкзаке со стоимостями. Задача о наибольшей клике в графе.

Динамическое программирование на подотрезках, поддеревьях, подмножествах. Задача нахождения гамильтонова цикла. Задача коммивояжёра. Задача о количестве рюкзаков, необходимых для переноса данного множества предметов. Meet-in-the-middle. Задача о рюкзаке со стоимостями. Задача о наибольшей клике в графе.

Немного о паросочетаниях. Постановка "задачи о марьяже". Устойчивые паросочетания. Наличие различных устойчивых паросочетаний. Алгоритм Гэйла-Шепли. Свойства алгоритма. Упорядоченность устойчивых паросочетаний. "Задача о соседях", отсутствие устойчивого решения в общем случае. Рассуждения о применении алгоритма Гэйла-Шепли для зачисления выпускников школ в вузы в России.

Бор. Построение бора. Некоторые применения бора. Алгоритм Ахо-Корасик поиска множества строк в строке.

Окружности. Пересечение прямой и окружности, пересечение окружностей, касательная к окружности из точки, общая касательная к двум окружностям. Многоугольники. Площадь многоугольника. Проверка принадлежности точки многоугольнику. Принадлежность точки выпуклому многоугольнику. Построение выпуклой оболочки (алгоритм Грэхема). Касательные к выпуклому многоугольнику, параллельные данной прямой и про...

z-функция. Определение, алгоритм вычисления за линейное время. Применения: поиск подстроки в строке, количество различных подстрок, поиск периода в подстроке. Подсчёт количества подстрок-палиндромов. Алгоритм Манакера. Префикс-функция. Определение, алгоритм вычисления за линейное время. Применения. Поиск подстроки в строке - алгоритм Кнута-Морриса-Пратта. Автомат КМП.

Окружности. Пересечение прямой и окружности, пересечение окружностей, касательная к окружности из точки, общая касательная к двум окружностям. Многоугольники. Площадь многоугольника. Проверка принадлежности точки многоугольнику. Принадлежность точки выпуклому многоугольнику. Построение выпуклой оболочки (алгоритм Грэхема). Касательные к выпуклому многоугольнику, параллельные данной прямой и про...

Декартова система координат. Точки, вектора. Полярные координаты, переход между декартовыми координатами и полярными. Функция atan2. Скалярное произведение. Векторное (псевдоскалярное, "косое") произведение векторов на плоскости. Их свойства, нахождение через координаты. Применение: принадлежность точки прямой, лучу, отрезку. Площадь треугольника, расстояние от точки до прямой, от точки до отре...

Двудольные графы. Паросочетания. Максимальное и наибольшее паросочетание. Удлиняющий путь. Алгоритм Куна. Реализация и оптимизация алгоритма Куна. Теорема Холла (теорема о женихах и невестах). Минимальное вершинное покрытие. Теорема Кёнига. Построение минимального вершинного покрытия на основе наибольшего паросочетания. Максимальное независимое множество. Разбиение ориентированного ациклическог...

Нахождение компонент сильной связности в ориентированном графе и построение конденсации графа. Алгоритм Косарайю (с двумя DFS). Алгоритм Тарьяна (с одним DFS). Задача 2-SAT, решение с использованием компонент сильной связности. Критерий отсутствия решения. Построение эйлерова цикла в графе.

Алгоритм обхода в глубину. Времена входа и времена выхода, их свойства. Классификация рёбер. Нахождение циклов в ориентированном и неориентированном графе. Мосты, нахождение мостов при помощи одного DFS. Компоненты рёберной двусвязности, алгоритм построения при помощи одного DFS. Точки сочленения, нахождение при помощи одного DFS. Компоненты вершинной двусвязности, нахождение при помощи одного ...

Задача LCA (Lowest common ancestor, наименьший общий предок). Алгоритм с использованием двоичный подъёмов. Алгоритм с использованием эйлерова обхода. Алгоритм Тарьяна для offline-запросов. Задача LA (Level ancestor, предок на заданной высоте). Алгоритм с использованием двоичных подъёмов. Алгоритм с использованием "длинных путей". Алгоритм с использованием Ladders ("лестницы", удвоенные длинные ...

Корневая декомпозиция. Структуры данных, с использованием корневой декомпозиции. Split rebuild. Корневая декомпозиция по запросам. "Легкие" и "тяжёлые" объекты. Алгоритм Мо.

Двоичное дерево поиска, проблема балансировки. Идея декартова дерева. Построение и единственность декартова дерева. Операции split и merge. Добавление и удаление элементов при помощи split и merge. Поддержка размеров поддеревьев. Нахождение k-го элемента в поддереве. Разбиение поддерева на деревья заданного размера. Декартово дерево по неявному ключу, операции с ним. Групповые запросы (сумма, м...

ЛКШ-2024, параллель 6. Лекция 1: Структуры данных. sparse table, дерево Фенвика, дерево отрезков.

Что едят преподаватели в Сириусе? Дегустация десерта "Вагаси Моти" с фруктовой начинкой

Установка компиляторов и сред разработки в Windows для использования на олимпиадах

ЛКШ-2023-зима, параллель 5 . Лекция 7: Кодирование с исправлением ошибок, задачи с двойным запуском.

ЛКШ-2023-зима, параллель 5 . Лекция 4: Алгоритм A*.

ЛКШ-2023-зима, параллель 5 . Лекция 1: Стереометрия.

ЛКШ-2023, параллель 5. Лекция 12: Алгоритмы на корневых деревьях (LCA, LA и другие задачи).

ЛКШ-2023, параллель 5. Лекция 11: Минимальное остовное дерево. Система непересекающихся множеств.

ЛКШ-2023, параллель 5. Лекция 10: Вычислительная геометрия: окружности, многоугольники.

ЛКШ-2023, параллель 5. Лекция 9: Вычислительная геометрия: вектора, углы, прямые.

ЛКШ-2023, параллель 5. Лекция 8: Алгоритмы на строках.

ЛКШ-2023, параллель 5. Лекция 7: Динамическое программирование, часть 2. Читает Александр Чистяков.

ЛКШ-2023, параллель 5. Лекция 6: Динамическое программирование. Читает Хетаг Дзестелов.

ЛКШ-2023, параллель 5. Лекция 5: Декартово дерево по неявному ключу. Сканирующая прямая.

ЛКШ-2023, параллель 5. Лекция 4: Декартово дерево.