Структуры данных (26.09)

1. Массовые операции в дереве отрезков и их применения.

2. Сканирующая прямая.

3. Спуск по дереву отрезков.

4. Неявное дерево отрезков.

5. Merge-sort-tree.

6. Двумерное дерево отрезков.

7. Дерево фенвика.

8. Двумерное дерево фенвика.

Дерево отрезков это самый частый алгоритм в проге. Если вы посмотрите на олимпиадки, то заметите, что каждая вторая задача его использует. Дерево фенвика это тоже прикольный алгоритм, который иногда может заменить дерево отрезков и работать сиильно быстрее.

Декартово дерево (3.10)

1. Декартово дерево по явному ключу

2. Декартово дерево по неявному ключу

3. RBST

Декартово дерево это очень крутая структура данных которая может почти всё, но довольна медленна. Задач непосредственно на декартово дерево мало, но часто решить задачи с использованием его идейно проще.

LCA и эйлеров обход дерева (10.10)

1. Определение наименьшего общего предка двух вершин в дереве (LCA).

2. Двоичные подъёмы, поиск LCA двух вешин за \(O(\log n)\) с предподчсётом \(O(n \log n)\).

3. Эйлеров обход, построение и применения для решения разных задач (LCA вершиин за \(O(\log n)\) с предподсчётом \(O(n)\); сумма на пути за \(O(\log n)\)).

4. Sparse Table, применениия (поиск минимума на отрезке за \(O(1)\); поиск LCA за \(O(1)\)).

5. LCA в онлайне (приписывание листов к дереву)

6. \(k\)-й предок вершины, поиск за \(O(\log n)\), за \(O(1)\).

7. Disjoint sparse table.

На олимпиадках очень часто встречаются задачи на деревья, часто они сводятся к LCA, двоичным подъёмам или эйлеровому циклу. Очень полезно знать эти темы.

Битовые динамики и оптимизации (17.10)

1. Диинамика по профилю / изломанному профилю.

2. Решение np-полных задач с помощью перебора (например поиск гамильтонова цикла за \(O(2^n * n^2)\)).

3. Перебор всех подмасок маски за \(O(3^n)\).

4. Bitset и его применениия (например для решения задачи о рюкзаке за \(O(nm / 32))\).

5. Meet-in-the-middle.

6. Подсчёт суммы по подмножествам за \(O(2^n * n)\) (битовая свёртка).

Любая задача имеет частичную группу на битовый перебор или какую-нибудь битовую муть. Так что в сложных задачах, в которых тяжело придумать решение, битовые оптимизации и динамики очень помогают набрать баллов.

DFS и его продвинутые применения (24.10)

1. Поиск мостов и точек сочленения

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

3. Поиск паросочетаня алгоритмом куна, применениия

4. Поиск эйлерова цикла и пути в графе

5. 2-SAT

Это продвинутые применения DFS, которые часто встречаются в разных задачах. Эти алгоритмы многие часто забывают и из-за этого сливают олимпиады, так что очень полезно их послушать и прорешать контест.

Каниикулы (31.10)

Математика (теория чисел) (7.11)

1. Алгоритм евклида, расширенный алгоритм евклида, применениия.

2. Факторизация числа за \(O(\sqrt{n})\), верхняя оценка числа делителей произвольного числа.

3. Малая теорема Ферма, быстрое возведение в степень по модулю, поиск обратного по простому модулю за \(O(\log p)\).

4. Функция Эйлера, поиск обратного по произвольному модулю за \(O(\log n)\) (2 способа).

5. Решето эратосфена за \(O(n \log \log n)\) и \(O(n)\).

6. Гармонический ряд.

7. Принцип включений и исключений.

8. Задача дискретного логарифмирования за \(O(\sqrt{n})\).

Математика и теория чисел это конечно неприятная фигня, но к сожалению на неё часто дают задачи (особенно на командных олимпиадах и всяких там Codeforces) и общие идеи отсюда часто пригождаются во многих задачах совсем не на математику.

Корневые оптимизации (14.11)

1. Нахождение числа треугольников в графе, идея тяжёлых и лёгких вершин в графе.

2. Идея, что различных по длине строк не больше \(\sqrt{n}\). Использование похожей идеи для решения задачи о рюкзаке за \(O(S \sqrt{S})\).

3. Стандартная идея корневой декомпозиции. Идея split-rebuilt и split-merge.

4. Алгоритм МО, МО на дереве, 3D МО, МО онлайн.

Корневые оптимизации это полезная тема, в последнее время особенно часто на неё дают задачи. Часто во многих задачах с помощью корневых оптимизаций можно решить задачи на частичные группы, написав при этом несложный код.

Геометрия-1 (21.11)

1. Структура вектора и всякие векторные и скалярные поризведения.

2. Проверка отрезков на пересечение.

3. Расстояние от точки до прямой.

4. Проекция точки на прямую.

5. Площадь многоугольника (несколько способов).

6. Проверка принадлежностии точки многоугольнику (несколько способов)

7. Уравнение прямой, простое построение по двум точкам.

8. Пересечение двух отрехков / прямых.

9. Уравнение окружности, пересечение окружности и прямой, пересечение двух окружностей.

10. Построение касательной из точки к окружностии, построение общей касательной двух окружностей.

11. Построение выпуклой оболочки за \(O(n * ans)\).

12. Построение выпуклой оболочки за \(O(n \log n)\)

13. Проверка принадлежности точки выпуклому многоугольнику за \(O(\log n)\).

Если теория чисел была неприятной, то геометрия это прям совсем редкостное ... Но к сожалению она встречается на олмпиадках и мне придеётся страдать и вам её рассказывать, а вам ещё больше страдать и её писать.

Алгоритмы на строках (28.11)

1. Хеши, использование.

2. Z-функция, Префикс функция, алгоритм Манакера.

3. Бор.

4. Ахо карасик, применения.

Алгоритмы на строках это ещё одна интересная тема, которая часто встречается на олимпиадах.

Centroid-декомпозиция и переливания (5.12)

1. Centroid-декомпозиция.

2. Переливания в дереве.

Это два прикольных продвинутых алгоритма, которые помогают решать очень много разных сложных задач на деревья, если они не сводятся к LCA.

Суффиксный автомат (12.12)

Это будет последнее содержательное занятие в 2019, у вас сразу потом будет сессия, так что контест на полезные алгоритмы вы вряд-ли порешаете, и поэтому я расскажу самый крутой и довольно бесполезный алгоритм — суффиксный автомат. Это будет действительно сложный алгоритм, но там много прикольных и красивых идей.

Какой-нибудь упоротый контест (19.12)

Я дам какой-нибудь фановый командный контест типа информатического морского боя, или чего-нибудь такого.

Длинные каникулы

Оптимизации ДП (17.01)

1. Convex-hull trick.

2. Оптимизация “Разделяй и влавствуй”.

3. Оптимизации кнута.

4. Оптимизация \(mod^2\).

5. Оптимизация хранения состояний ДП для ускорения за счёт кэша.

6. Лямбда-оптимизация.

7. Дерево Li-Chao.

Оптимизации ДП это очень важная и полезная тема, именно из-за их незнания я не стал победом всеросса. Ежегодно на всероссе дают хотя-бы по задаче на них, запросто могут дать и на регионе.

Математика-2 (23.01)

1. Повторение комбинаторики (бином Ньютона, треугольник Паскаля).

2. Поиск всяких комбинаторных объектов по номеру.

3. Определение вероятности, простые задачи.

4. Условная вероятность.

5. Матожидание, его линейность.

6. Всякие задачи на матожидание и вероятность.

7. Метод Гаусса.

8. Использование возедения в степень для подсчёта всяких выражений.

Сюдя я решил закинуть всё, что осталось в математике после первой лекции — очень полезную и нужную комбинаторику (хотя наверное вы все её и так знаете), иногда полезную и прикольную теорию вероятности и немного основ линала (когда пойдёте в Вышку, вы его возненавидите)

Семинар по графам (30.01)

Я заранее скину листочки с задачами по графам, вы их немного порешаете и потом разберём. Ну и заодно расскажу что-нибудь полезное про регион, всякие полезные советы (на которые вы правда всё равно забьёте).

Дальше будет регион, после которого количество людей, ходящих на кружок, сократится раза в два, и поэтому дальше мы будем заниматься всякими более сложными и прикольными вещами.

Персистентность и продвинутые структуры данных (5.02)

1. Персистентный стек

2. Персистентное ДО и ДД

3. Задачи на персистеность (типа поиска \(k\)-й порядковой)

4. merge-sort-tree

5. Частичное каскадирование

6. Дерево отрезков по времени, DCP-offline за \(O(n \log^2)\)

Это всякие продвинутые применения структур данных. Они не часто встречаются на олимпиадках, но послушать их полезно.

Геометрия-2 (13.02)

1. Построение касательной из точки к выпуклому многоугольнику из точки за \(O(\log n)\).

2. Пересечение прямой и выпуклого многоугольника за \(O(\log n)\).

3. Поиск двух ближайших точек на плоскости за \(O(n \log n)\), за \(O(n)\).

4. Поиск двух наиболее отдалённых точек на плоскости за \(O(n \log n)\).

5. Квадродерево.

6. Вероятностные алгоритмы: проверка пересечения полуплоскостей на непустоту за \(O(n)\), построение минимальной покрывающей окружности за \(O(n)\).

Как не странно, продвинутая геометрия не такая неприятная как начальная, если конечно её не писать, но я то знаю, что вы контест решать почти не будете. Кстати темы, которые я расскажу здесь, иногда могут встретится на олимпиадах.

Теория игр (20.02)

1. Теория игр, выигрышные и проигрышные стратегии.

2. Ретроанализ.

3. НИМ.

4. Теория Шпрага-Гранди, применения.

Теория игр это ещё одна тема, которую стоит рассказать и которая иногда встречается. Несмотря на то, что математики тут больше, чем проги, это всё равно интересно послушать.

Потоки-1 (27.02)

1. Определение миллиардов нужных терминов.

2. Доказательства всяких теорем (скорее всего вы все забьёте, но формально я должен это рассказать).

3. Алгоритм Форда-Фалкерсона.

4. Алгоритм Эдмонса-Карпа.

5. Алгоритм Динницы.

6. Идея масштабирования.

7. Применения потоков.

Потоки всегда считались юзлесс, пока в прошлом году они не встретились на регионе. Вроечем, в той задачи алгоритмом Куна можно было 80 баллов набрать, так что потоки и остались бесполезными, максимум могут встретится в D всеросса на 50+ баллов. Но в целом это прикольная идея и к потокам можно много задач свести.

?Теоретический семинар (5.03)

Я точно не знаю когда будет открытая, но если не в эти числа, то проведём теоретический семинар на всякие структуры данных и просто прикольные теор. задачи.

Дальше будут всякие сборы, всероссы и точное расписание составить не получится. Ну и из полезных на олимпиадках тем ничего не останется. Так что я буду рассказывать просто всякие крутые алгоритмы, которые стоит слушать только если вам в кайф заниматься всякими упоротыми алгоритмами, а не ради того, чтобы на всеросс и другие олимпиадки натаскаться.