Tinkoff Generation

Параллель A 2020. Программа первого полугодия

26 сентября 2020. Математика 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 октября 2020. Структуры данных 1.

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

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

  3. Merge-sort tree.

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

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

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

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

  8. Segment tree beats.

  9. Sparse Table.

  10. Disjoint Sparse Table.

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

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

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

  14. Фенвики + Фенвики (""сжатые"").

10 октября 2020. Корневые.

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

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

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

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

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

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

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

  8. 3D Мо.

  9. Мо онлайн.

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

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

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

17 октября 2020. Оптимизации ДП.

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

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

  3. Convex hull trick.

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

  5. Дерево Li Chao.

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

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

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

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

24 октября 2020. Структуры данных 2.

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

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

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

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

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

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

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

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

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

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

  11. *2-3 Дерево

  12. *Частичная персистентность с линейной памятью

31 октября 2020. Работа с компьютером и 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. priority_queue vs. set

  11. mt19937, mt19937_64

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

    shuffle

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

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

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

    valgrind

    gdb

  14. AVX

  15. pb_ds, gp_hash_table

7 ноября 2020. Потоки 1.

  1. Основные определения

  2. Теорема Форда-Фалкерсона и соответствующий алгоритм.

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

  4. Масштабирование для Форда-Фалкерсона и Эдмондса-Карпа.

  5. Декомпозиция потока за \(O(E^2)\) и за \(O(VE)\).

  6. LR-потоки.

  7. Поиск блокирующего потока за \(O(E^2)\), \(O(VE)\), *\(O(V^2)\)

  8. Алгоритм Диница за \(O(V^2E)\), *\(O(V^3)\).

  9. Масштабирование для Диница.

  10. Оценки Карзанова для Диница

  11. Поиск величины максимального потока в планарном графе.

  12. Стоимостные потоки.

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

  14. *Дейкстра с потенциалами.

14 ноября 2020. Быстрое преобразование Фурье.

  1. Комплексные числа

  2. Прямое преобразование Фурье

  3. Обратное преобразование Фурье

  4. Доказательство корректности обратного преобразования Фурье

  5. Применения Фурье для произведения многочленов. Поиск вхождений строки в другую со <<звёздочками>>

  6. *Деление двух чисел за \(O(n \log^2 n)\)

  7. *Быстрое нахождение корня

21 ноября 2020. Геометрия.

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

  2. Пересечение прямых.

  3. Пересечение прямой и окружности.

  4. Пересечение двух окружностей.

  5. Поиск касательных к окружности.

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

  7. Алгоритм Джарвиса.

  8. Алгоритм Грэхема.

  9. Алгоритм Эндрю.

  10. Алгоритм Чана.

  11. Поиск пары пересекающихся отрезков за \(O(n \log n)\).

  12. Локализация точки в выпуклом многоугольнике за \(O(\log n)\) на запрос.

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

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

  15. Локализация точки в невыпуклом многоугольнике за \(O(\log n)\) на запрос.

  16. Поиск двух ближайших точек в 2D за \(O(n \log n)\) и рандомизированно за \(O(n)\)

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

  18. Вращающийся scanline. Запросы количества точек в полуплоскости. \(O(n^2 + q \log n)\).

  19. Сумма Минковского и ее применения.

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

  21. Проверка на непустоту пересечения полуплоскостей за \(O(n)\).

  22. Поиск минимальной покрывающей окружности за \(O(n)\).

28 ноября 2020. Структуры данных 3.

  1. Задача LA.

  2. Задача LCA.

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

  4. Euler tour tree

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

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

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

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

  9. Centroid decomposition.

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

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

5 декабря 2020. Битовые оптимизации.

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

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

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

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

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

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

  7. Флойд \(O(n^3/w)\), bfs за \(O(n^2 / w)\)

  8. Перемножение битовых матриц за \(O(n^3/w)\)

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

  10. решения задачи суммы по подмаскам за \(O(2 ^ n * n)\).

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

  12. Meet-in-the-middle

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

  14. Меморизация в задаче о клике с доказательством времени работы \(O(2^{n / 2})\)

  15. Предподсчёт ответа для маленьких задач

  16. iterative deepening (Увеличиваем максимальную длину пути в дереве перебора на 1)

  17. Битовые and и or свёртки за \(O(n \log n)\), сведение к задаче суммы по подмаскам

  18. Преобразование Адамара за \(O(n \log n)\)

  19. Битовая xor свёртка за \(O(n \log n)\)

12 декабря 2020. Строки 1.

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

  2. Хеши.

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

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

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

  6. Проверка графов на изоморфизм

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

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

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

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

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

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

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

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

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

19 декабря 2020. Зачёт

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