День 01. Графы. dfs.

1. Три цвета dfs. Поиск цикла.

2. Классификация рёбер (древесное, обратное, прямое, перекрёстное)

3. Классификация рёбер в неорграфе (древесное, обратное)

4. topsort. Два способа его построить.

5. КСС

6. Мосты

7. Точки сочленения.

День 02. Остовные деревья

1. Определение MST

2. Лемма о разрезе

3. Алгоритм Краскала

4. Алгоритм Прима

6. СНМ
6.1 Списочная реализация
6.2 Древесная реализация
6.3 Две эвристики
6.4 Два доказательства на O(log) (для двух эвристик)

День 03. Кратчайшие пути.

1. Дейкстра
1.1 Алгоритм
1.2 Время работы
1.3 Реализация с set-ом / кучей.
1.4 Корректность

2. Флойд (без отрицательных циклов).
2.1 Алгоритм
2.2 Корректность
2.3 Оценка на время
2.4 Восстановление пути: два способа (рекурсивный и предыдущая вершина)

3. Форд-Беллман (без отрицательных циклов)
3.0 Постановка задачи
3.1 Алгоритм
3.2 Корректность
3.3 Оценка на время

4. Флойд + отрицательные циклы
4.1. Lm. существует отрицательный цикл <=> существует i: d[i][i] < 0 (с доказательством)

5. Форд-Беллман + отрицательные циклы
5.1 Что происходит если они есть?
5.2 Как найти отрицательный цикл в графе с помощью ФБ.
5.3 Доказательства:
5.3.1 Eсть релаксация на шаге n <=> Есть отр цикл.
5.3.2 Цикличность обратных ссылок из обновившейся вершины.
5.3.3 Отрицательность соответствующего цикла (без доказательства).

6. 1-k bfs
6.1 Решение. Очереди. Корректность.
6.2 Асимптотика O(m + nk).
6.3 Оптимизация по памяти в k очередей.
6.4 0-k bfs
6.5 0-1 bfs (в две очереди)
6.6 0-1 bfs (в дек)

День 04. Дерево Отрезков

1. Дерево отрезков
1.1 Общая идея
1.2 Способ хранения
1.3 Реализация

2. Доказательство на количество просмотренных вершин на уровне

3. Массовые операции
3.1 Проталкивание
3.2 Примеры

4. Спуск по дереву.

5. Сложные функции на отрезке
5.1 Самый длинные чёрный отрезок

День 05. Декартово дерево & sparse table

1. Sparse Table
1.1 Построение, зачем нужно, ответ на запрос.

2. Бинарное дерево поиска
2.1 Поиск, добавление втупую

3. Декартово дерево
3.1 Определение
3.2 Существование и единственность по <x, y> для различных x, y.
3.3 Построение за O(n)
3.4 Случайные приоритеты. Средняя высота O(log(n)) (доказательство факультативно)

4. Операции с ДД
4.1 merge
4.2 split
4.3 Удаление-добавление элемента через merge & split
4.4 (*) Удаление-добавление за 1 split/merge

День 06. Неявный ключ

1. Функции на поддеревьях
1.1 Размер поддерева
1.2 Спуск к k-ому элементу за O(log).

2. ДД + неявный ключ
2.1 In-order нумерация вершин
2.2 Как меняется split, merge

3 Групповые операции на ДД
3.1 Задача: вставка элемента, прибавление на отрезке, сумма на отрезке
3.2 Задача: вставка элемента, реверс подотрезка, сумма на отрезке. 

День 07. Геом-1

1. Точка, вектор
1.1 Операции над векторами, скалярное, векторное произведение
1.2 Поворот на угол
1.3 Взаимное расположение векторов с помощью произведений

2. Прямые, отрезки
2.1 Уравнение прямой(однородное, параметрическое)
2.2 Растояние от прямой до точки
2.3 Пересечение прямых
2.4 Растояние между отрезками

День 08. Геом-2

1. Многоугольники
1.1 Способ задания многоугольника
1.2 Площадь многоугольника
1.3 Выпуклая оболочка за nlogn
1.4 Точка в многоугольнике
1.5 Точка в выпуклом многоугольнике

2. Окружности
2.1 Пересечение окружности и прямой
2.2 Пересечение двух окружностей

День 09. SQRT

1. SQRT на массиве
1.1 Просто
1.2 +Массовые операции
1.3 +СД внутри

2. Split-Rebuild SQRT
2.1 Концепция и пример

3. Декомпозиция по запросам
3.1 Винни-Пух
3.2 Задача про set (insert(val), count(l..r))
3.3 DCP offline

4. SQRT на строках

5. MO
5.1 Обычное (+ доказательство n sqrt(n)).
5.2 Идея избавление от корня
5.3 3d-mo (без строгого доказательства)

День 10. DP

1. Общая концепция ДП
1.1 разбиение на подзадачи
1.2 взгляд на дп как на процесс
1.3 динамика вперёд, назад, ленивая

2. Задача про НОП (решение за n^2)

3. Задача про НВП
3.1 Простое решение за n^2
3.2 Оптимизация с ДО или ДД
3.3 Решение с помощью lower_bound (c доказательством)

4. Задача о рюкзаке
4.1 Решение за O(nW), O(w) памяти.

5. Дп по подотрезкам
5.1 Число подпалиндромов
5.2 Макс палиндром

6. ДП по цифрам
6.1 От l до r, сумма цифр с k.

День 11. DP-2

1. ДП по поддеревьям
1.1 Размер поддерева
1.2 Количество связных подграфов дерева
1.3 Максимальное независимое множество
1.4 Макс парсоч

2. ДП по подмножествам
2.1 Макс парсоч O(2^n) состояния, O(n 2^n) переходов
2.2 Гам путь в произвольном графе за O(2^n n^2)
2.3 Рюкзак - разбить предметы на мин число рюкзаков с capacity <= W.
2.3.1 Решения за O(4^n), O(3^n), O(n 2^n)

3. ДП по изломанному профилю

День 12. Строки

1. хеши
1.0 Основы
1.1 Сравнение строк на равенство
1.2 Сравнение строка на неравенство O(log)
1.3 Парадокс дней рождений.

2. fenwick (с доказательством)

3. Префикс функция
3.1 алгоритм & корректность: вложенность "бордеров", переход к меньшим
3.2 время работы

4. Z-функция
4.1 алгоритм
4.2 время работы

5. преф/Z функции:
5.1 период и псевдопериод
5.3 строка в строке

6. бор
6.1 Определение, способы хранения, на что они влияют.
6.2 Пример задачи