Tinkoff Generation

Алгоритмы. Параллель A. План занятий первого полугодия

7 сентября 2019. Математика 1.

  1. Алгоритм Евклида.

  2. Бинарный алгоритм Евклида.

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

  4. Утверждение о том, что алгоритм Евклида для \(n\) чисел, не превосходящих \(C\), работает за \(O(n + log C)\).

  5. Утверждение о том, что НОД, уменьшаясь, уменьшается хотя бы в \(2\) раза.

    Задача поиска количества подотрезков массива с НОД = \(x\) для всех актуальных значений \(x\).

  6. Обратный по модулю. Критерий существования.

  7. Применение расширенного алгоритма Евклида для поиска обратного по произвольному модулю.

  8. Малая теорема Ферма.

  9. Применение малой теоремы Ферма к поиску обратного по простому модулю.

  10. Мультипликативные функции и их свойства.

  11. Функция Эйлера и теорема Эйлера.

  12. Вычисление функции Эйлера за \(O(\sqrt n)\).

  13. Нижняя и верхняя оценка на частичные суммы гармонического ряда.

  14. Решето Эратосфена за \(O(n)\).

  15. Применение решета Эратосфена для подсчета мультипликативных функций для всех натуральных чисел, не превосходящих \(n\), за \(O(n)\).

  16. Применение решета Эратосфена для факторизации чисел за \(O(\log n)\) с предпосчетом за \(O(n)\).

  17. Предподсчет всех обратных по простому модулю к числам, не превосходящим \(n\), за \(O(n)\). Применение к предпосчету обратных факториалов.

  18. Быстрое вычисление биномиальных коэффициентов с предпосчетом за \(O(n)\).

  19. Количество делителей – субполиномиальная функция, практическая оценка \(O(n^{1/3})\).

  20. Применение принципа включений-исключений в теории чисел.

  21. Задача дискретного логарифмирования и ее решение за \(O(\sqrt n)\) методом meet-in-the-middle.

  22. Китайская теорема об остатках.

  23. Утверждение о том, что \(a \geq b \Longrightarrow a \text{ mod } b \leq a / 2\). Следствие — в результате взятий по модулю мы не можем уменьшить число больше \(O(\log C)\) раз.

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

  25. Алгоритм Полларда-Ро.

14 сентября 2019. Структуры данных 1.

  1. Дерево отрезков: поиск подотрезка с максимальной суммой.

  2. Сканлайн. Средне.

    Задача о нахождении суммы в прямоугольнике.

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

    Задача о поиске площади объединения прямоугольников.

    Задача о поиске количества различных на отрезке.

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

  4. Merge-sort tree.

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

  6. Частичное каскадирование для \(k\) списков (одновременный бинпоиск для всех списков за \(O(log n + k)\).

  7. Параллельные бинпоиски.

  8. Сжатое (неявное, динамическое) дерево отрезков.

  9. Дерево отрезков: реализация снизу.

  10. JDriver segment tree.

  11. Spliting and merging segment trees.

  12. Sparse Table.

  13. Sparse Table: построение за \(O(n \log \log n)\); построение за \(O(n \log \cdot n)\) и ответ на запрос за \(O(\log \cdot n)\).

  14. Disjoint Sparse Table.

  15. Дерево Фенвика.

  16. Многомерное дерево Фенвика.

  17. ДО + Фенвики.

  18. Фенвики + Фенвики (“”сжатые“”).

21 сентября 2019. Оптимизации ДП.

  1. Использование вспомогательной динамики для пересчета значения в вершине.

    Задача о редукции дерева: удалить из дерева минимальное количество ребер так, чтобы одна из компонент была размера ровно k.

    [Смотрите пост http://codeforces.com/blog/entry/6703 с доказательствами времени работы.]

  2. Рюкзак за \(O(S \sqrt S)\) (два способа), \(O(nS / w)\), \(O(S \sqrt S / w)\).

  3. Оптимизация разделяй-и-властвуй.

  4. Оптимизация Кнута.

  5. Convex hull trick.

  6. Convex hull trick в дереве отрезков.

  7. Дерево Li Chao.

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

  9. \(\text{MOD}^2\)-оптимизация.

  10. Хранение только достижимых состояний.

  11. Менять местами значение дп и параметр(dp[a][b] = c \(\rightarrow\) dp[a][c] = b).

  12. Функция ДП  — пара.

28 сентября 2019. Корневые.

  1. Нахождение количества треугольников в графе за \(O(E \sqrt E)\).

  2. Корневая для задачи dynamic records.

  3. Корневая в задачах на строки: разбиение строк на короткие и длинные.

  4. Корневая на графах: тяжелые и легкие вершины.

  5. Решение задачи о рюкзаке за \(O(S \sqrt{S})\)

  6. Алгоритм Мо.

  7. Алгоритм Мо на дереве (эйлеровом обходе).

  8. Алгоритм Мо + корневая как структура для Мо.

  9. 3D Мо.

  10. Мо онлайн.

  11. Split-rebuild и split-merge в корневой.

  12. Корневая декомпозиция по запросам.

5 октября 2019. Математика 2.

  1. Матрицы. Алгоритм Гаусса.

  2. Ускорение ДП возведением матриц в степень.

  3. Оптимизации возведения матриц в степень: \(\text{MOD}^2\), транспонирование.

  4. Ускорение вычисления ДП для разных степеней предпосчетом матриц перехода для степеней двойки.

  5. Определение вероятности. Подсчет простых вероятностей.

  6. Условные вероятности.

  7. Матожидание. Его линейность.

12 октября 2019. Битовые оптимизации.

  1. Динамика по изломанному профилю. Задача о количестве замощений доминошками.

  2. Решение задачи суммы в подмножестве за \(O(2 ^ n)\).

  3. Поиск гамильтонова пути за \(O(2 ^ n \cdot n ^ 2)\).

  4. Нахождение старшего ненулевого бита для всех чисел, меньших \(2 ^ n\), за \(O(2 ^ n)\).

  5. Нахождение младшего ненулевого бита для всех чисел, меньших \(2^n\), за \(O(2 ^ n)\).

  6. Оценка \(2^{n - 1} \cdot n\) на суммарное количество ненулевых битов для всех чисел, меньших \(2 ^ n\).

  7. Перебор всех подмасок данной маски.

  8. Оценка \(3^n\) на суммарное количество подмасок для всех масок, меньших \(2^n\).

  9. Замечание о том, что vector<bool> применяет битовое сжатие. Размышления о том, что это может как негативно, так и положительно влиять на скорость выполнения программ.

  10. bitset и его простейшие применения. Рассказ o _Find_first и _Find_next.

  11. Транзитивное замыкание Флойдом за \(O(n^3 / w)\).

  12. Нахождение количество ненулевых битов в числе: предподсчет + деление на части, __builtin_popcount, __builtin_popcountll, #pragma GCC optimize(“”popcnt“”) vs. precalc.

  13. Применение многомерных префиксных сумм для решения задачи суммы по подмаскам за \(O(2 ^ n \cdot n)\).

  14. Поиск гамильтонова пути за \(O(2 ^ n \cdot n \cdot \lceil n / w \rceil)\) (\(= O(2 ^ n \cdot n)\) для актуальных значений \(n\)).

  15. Поиск максимальной клики за \(O(2 ^{(n / 2)})\) методом meet-in-the-middle.

  16. Метод четырех русских. Применение для умножения битовых матриц. Применение для нахождения НВП.

  17. Битовые свертки: and, or.

  18. Битовые свертки: xor

  19. Meet-in-the-middle

19 октября 2019. Работа с компьютером и C++.

Это занятие будет перед МКОШПом, чтобы не утомлять вас новыми темами. Прямо на занятии мы дадим контемст на тестирование.

  1. ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cout.tie(nullptr);

  2. cppreference

  3. scanf printf setprecision для отформатированного вывода

  4. Работа с файлами:

    freopen

    ifstream, ofstream

    Бонус: sstream

  5. __gcd (а в C++17 — gcd, lcm)

    min_element, max_element, nth_element

    merge, sort, stable_sort

    fill, copy, (C: memset, memcpy)

    reverse, rotate

    unique

    lower_bound, upper_bound, binary_search

    next_permutation, prev_permutation

    partial_sum

  6. Лямбда-функции.

  7. Компараторы-функторы.

  8. range-based for

    Structured binding declaration

  9. #pragma

  10. define ifdef

  11. priority_queue vs. set

  12. initializer_list

  13. swap, его время работы на стандартных контейнерах (O(1))

  14. mt19937, mt19937_64

    random_device (не работает под MinGW?)

    shuffle

  15. templates, template specialization

  16. Классы, наследование, виртуальные функции

  17. Написание стресс-тестов с помощью python

    Написание стресс-тестов с помощью bash

    Написание простых генераторов

  18. -fsanitize=address,undefined,bounds -g

    valgrind

    gdb

  19. Makefile

26 октября 2019. Структуры данных 2.

  1. Очередь на двух стеках.

  2. Минимум на окне: два стека или дек

  3. Минимум оффлайн: идея с деком + СНМ

  4. Алгоритм Фараха-Колтона и Бендера (RMQ \(\pm 1\)). RMQ \(\rightarrow\) LCA.

  5. LCA \(\rightarrow\) RMQ \(\pm 1\). Поиск LCA с помощью Sparse Table.

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

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

  8. Персистентный СНМ.

  9. Персистентное ДД.

  10. Персистентная очередь за \(O(1)\).

    Другие применения деамортизации: деамортизация вектора.

  11. Утверждение о том, что персистентность не работает с амортизацией.

    (Но если персистентность “”линейна“”, то есть дерево зависимостей – цепочка, то все не так плохо.)

  12. Сканлайн + персистентность.

    Задача о поиске \(k\)-й порядковой статистики на отрезке за \(O(\log n)\) на запрос.

2 ноября 2019. Строки 1.

  1. Хеш-таблицы. Открытая и закрытая адресации.

  2. Хеши.

  3. Хеши мультимножеств.

  4. Проверка корневых деревьев на изоморфизм.

  5. Парадокс дней рождения.

  6. Префикс-функция.

  7. Z-функция.

  8. Поиск тандемных повторов

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

  10. Бор. Способы хранения: map, unordered_map (один большой), массив, вектор.

  11. Сжатый бор. Оценка на глубину \(O(\sqrt S)\).

  12. Ахо-Корасик.

  13. Суффиксный массив за \(O(n \log n)\).

  14. Подсчет LCP за \(O(n)\) в суфмасе.

09 ноября 2019. Структуры данных 3.

  1. Структуры данных с откатами.

  2. Двоичные подъемы:

  3. Аналогия с бинпоиском.

  4. Задача LA.

  5. Задача LCA.

  6. Эйлеров обход дерева.

  7. Сжатые деревья.

  8. Heavy-light decomposition. Объединение HLD и эйлерова обхода.

  9. Кеширование префиксов в HLD.

  10. Продвинутые применения эйлерова обхода.

  11. Ladder decomposition и \(k\)-th ancestor. Построение за \(O(n \log n)\), ответ на запрос за \(O(1)\).

  12. Ladder decomposition и \(k\)-t ancestor. Построение за \(O(n)\), ответ на запрос за \(O(1)\).

  13. Centroid decomposition.

  14. Разделяй-и-властвуй по запросам. Dynamic connectivity problem за \(O(n \log^2 n)\).

  15. Dynamic connectivity problem за \(O(n \log n)\).

  16. Оптимизация меньшее к большему (вариация – отрезай меньшее).

  17. Переливания в дереве за \(O(h)\) \(\Longrightarrow\) \(O(n)\).

  18. Обходим маленькие поддеревья дважды.

16 ноября 2019. Игры.

  1. Выигрышные, проигрышные состояния.

  2. Теория Шпрага-Гранди.

  3. Теория Смита (игры с ничейными состояниями)

  4. Ретро-анализ.

  5. Альфа-бета отсечение.

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

23 ноября 2019. Графы 1.

  1. DFS: конденсация.

  2. 2-SAT.

  3. Дейкстра: базовая и на сете (prioriry_queue!).

  4. Форд-Беллман на очереди.

  5. Алгоритм Джонсона.

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

  7. Детекция циклов отрицательного веса.

  8. Поиск минимального средневзвешенного цикла.

  9. Эйлеровы пути и циклы.

  10. Паросочетания. Алгоритм Куна.

  11. Минимальное вершинное покрытие и максимальное независимое множество в двудольных графах.

  12. Разбиение DAG на минимальное количество путей.

  13. Теорема Дилуорса.

30 ноября 2019. Блиц.

  1. Перебор связных клеточных фигур с помощью очереди.

  2. Оптимизации для задачи коммивояжера.

07 декабря 2019. Резерв.

В это время будет ВКОШП. Скорее всего мы расскажем что-то интересное, не относящееся к олимпиадкам.

14 декабря 2019. Зачет.

21 декабря 2019. Развлекательный контест.