Форум DL

Мой профиль

Все лекции Павла Маврина на youtube

ITMO Algorithms Course (A&DS). Semester 2.
Lecture 1. Segment Tree
Lecture 2. Segment Tree. Lazy Propogation
Lecture 3. Fenwick Tree. Sparse Table
Lecture 4. Двумерные задачи на дерево отрезков
Lecture 5. Binary Search Tree
Lecture 6. Декартово дерево, дерево по неявному ключу
Lecture 7. Splay Tree
Lecture 9. Binary Lifting

Семестр 4
Lecture 6. Кососимметрические потоки

[b]ITMO Algorithms Course (A&DS). Semester 1.
Lecture _1. Algoritms. Time c...
Lecture _2. Data Structures. Bin...
Lecture _3. Quick Sorting
Lecture _4. Lower Bounds for s...
Lecture _5. Binary Search
Lecture _6. Stacks. Ques. Am.
Lecture _7. Linked Lists
Lecture _8. Disjoint Sets
Lecture _9. Fibbonacci heap
Lecture 10. Dynamic Programming
Lecture 11. Dynamic Programming
Lecture 12. Knapsack Problem
Lecture 13. DP on subsets, DP on.
Lecture 14. Hash Tables

ITMO Algorithms Course (A&DS). Semester 2

Topics of the second semester:

Segment Trees and similar data structures
  Segment Tree
  Fenwick Tree
  Sparse Table
  2D Trees
Binary Search Trees
  AVL Tree
  Treap
  Splay Tree
Data Structures for Trees
  Binary Lifting
  LCA and LA problems
  Heavy-Light Decomposition
  Link-Cut Tree
  Centroid Decomposition
Plus something more

Мой профиль

Reference book for IOI

Мой профиль

A list of important concepts in Tree-based Problems

Trees are a subset of graph theory problems that use the features of a tree:

Acyclic
Exactly 1 path between every pair of nodes.

Important algorithms (hopefull) exhaustive list:

Preorder + Data strcutures
Dynamic Programming on tree
2K Decomposition of tree (and Lowest Common Ancestor)
Kruskal Reconstruction Tree (KRT) (IOI Werewolf trick)
Set Merging (with linear height merging)
O(N2) Distribution DP
"Re-rooting" tree DP (where you DP twice, once going down and once propagating from top)
Centroid Decomposition
Heavy-Light Decomposition
UFDS on tree (See: CEOI 2017 Streets)
(Edit: Thanks errorgorn ) Greedy for furthest node (See: RU Code Funny Salesman)

Мой профиль

EDU: Видео "Префиксные суммы и разностные массивы"
Все учебные видео Егора Горбачева

Мой профиль

Top 10 optimizations 2017- (collectors edition)

Мой профиль

GNU C++20

From: Лёша Ситников
Sent: Thursday, October 21, 2021 10:45 PM

https://codeforces.com/blog/entry/96040?#comment-851241
Вот тут человек описал нововведения, которые могут быть полезными в спортивном программировании

From: Антон Харрасов
Sent: Thursday, October 21, 2021 5:22 PM

https://codeforces.com/blog/entry/96040
https://codeforces.com/blog/entry/84249
https://ru.wikipedia.org/wiki/C%2B%2B20

я сам ещё далеко не читал, но во многих местах жизнь должна стать чуть проще

Мой профиль

Книга по спортивному программированию (от спортивных программистов)
Файл будет храниться до 21.07.2022

Копия на DL

Как минимум - посмотрите оглавление.
Что-то может сразу захотите почитать.
А про остальное будете знать, где найти в случае необходимости

Оглавление

Вступление
Предисловие
От издательства
Об авторах этой книги Список сокращений

Глава 1. Введение

1.1. Олимпиадное программирование
1.2. Как стать конкурентоспособным
1.2.1. Совет 1: печатайте быстрее!
1.2.2. Совет 2: быстро классифицируйте задачи
1.2.3. Совет 3: проводите анализ алгоритмов
1.2.4. Совет 4: совершенствуйте свои знания языков программирования
1.2.5. Совет 5: овладейте искусством тестирования кода
1.2.6. Совет 6: практикуйтесь и еще раз практикуйтесь!
1.2.7. Совет 7: организуйте командную работу (для ICPC)
1.3. Начинаем работу: простые задачи
1.3.1. Общий анализ олимпиадной задачи по программированию
1.3.2. Типичные процедуры ввода/вывода
1.3.3. Начинаем решать задачи
1.4. Задачи Ad Hoc
1.5. Решения упражнений, не помеченных звездочкой
1.6. Примечания к главе 1

Глава 2. Структуры данных и библиотеки

2.1. Общий обзор и мотивация
2.2. Линейные структуры данных – встроенные библиотеки
2.3. Нелинейные структуры данных – встроенные библиотеки
2.4. Структуры данных с реализациями библиотек, написанными авторами этой книги
2.4.1. Граф
2.4.2. Система непересекающихся множеств
2.4.3. Дерево отрезков
2.4.4. Дерево Фенвика
2.5. Решения упражнений, не помеченных звездочкой
2.6. Примечания к главе 2

Глава 3. Некоторые способы решения задач

3.1. Общий обзор и мотивация
3.2. Полный перебор
3.2.1. Итеративный полный перебор
3.2.2. Рекурсивный полный перебор (возвратная рекурсия)
3.2.3. Советы
3.3. «Разделяй и властвуй»
3.3.1. Интересное использование двоичного поиска
3.4. «Жадные» алгоритмы
3.4.1. Примеры
3.5. Динамическое программирование
3.5.1. Примеры DP
3.5.2. Классические примеры
3.5.3. Неклассические примеры
3.6. Решения упражнений, не помеченных звездочкой
3.7. Примечания к главе 3

Глава 4. Графы

4.1. Общий обзор и мотивация
4.2. Обход графа
4.2.1. Поиск в глубину (Depth First Search, DFS)
4.2.2. Поиск в ширину (Breadth First Search, BFS)
4.2.3. Поиск компонент связности (неориентированный граф)
4.2.4. Закрашивание – Маркировка/раскрашивание компонент связности
4.2.5. Топологическая сортировка (направленный ациклический граф)
4.2.6. Проверка двудольности графа
4.2.7. Проверка свойств ребер графа через остовное дерево DFS
4.2.8. Нахождение точек сочленения и мостов (неориентированный граф)
4.2.9. Нахождение компонент сильной связности (ориентированный граф)
4.3. Минимальное остовное дерево
4.3.1. Обзор
4.3.2. Алгоритм Краскала
4.3.3. Алгоритм Прима
4.3.4. Другие варианты применения
4.4. Нахождение кратчайших путей из заданной вершины во все остальные (Single – Source Shortest Paths, SSSP)
4.4.1. Обзор
4.4.2. SSSP на невзвешенном графе
4.4.3. SSSP на взвешенном графе
4.4.4. SSSP на графе, имеющем цикл с отрицательным весом
4.5. Кратчайшие пути между всеми вершинами
4.5.1. Обзор
4.5.2. Объяснение алгоритма DP Флойда–Уоршелла
4.5.3. Другие применения
4.6. Поток 253
4.6.1. Обзор
4.6.2. Метод Форда–Фалкерсона
4.6.3. Алгоритм Эдмондса–Карпа
4.6.4. Моделирование графа потока – часть I
4.6.5. Другие разновидности задач, использующих поток
4.6.6. Моделирование графа потока – часть II
4.7. Специальные графы
4.7.1. Направленный ациклический граф
4.7.2. Дерево
4.7.3. Эйлеров граф
4.7.4. Двудольный граф
4.8. Решения упражнений, не помеченных звездочкой
4.9. Примечания к главе 4

Глава 5. Математика

5.1. Общий обзор и мотивация
5.2. Задачи Ad Hoc и математика
5.3. Класс Java BigInteger
5.3.1. Основные функции
5.3.2. Дополнительные функции
5.4. Комбинаторика
5.4.1. Числа Фибоначчи
5.4.2. Биномиальные коэффициенты
5.4.3. Числа Каталана
5.5. Теория чисел
5.5.1. Простые числа
5.5.2. Наибольший общий делитель и наименьшее общее кратное
5.5.3. Факториал
5.5.4. Нахождение простых множителей с помощью оптимизированных операций пробных разложений на множители
5.5.5. Работа с простыми множителями
5.5.6. Функции, использующие простые множители
5.5.7. Модифицированное «решето»
5.5.8. Арифметические операции по модулю
5.5.9. Расширенный алгоритм Евклида решение линейного диофантова уравнения
5.6. Теория вероятностей
5.7. Поиск цикла
5.7.1. Решение(я), использующее(ие) эффективные структуры данных
5.7.2. Алгоритм поиска цикла, реализованный Флойдом
5.8. Теория игр
5.8.1. Дерево решений
5.8.2. Знание математики и ускорение решения
5.8.3. Игра Ним
5.9. Решения упражнений, не помеченных звездочкой
5.10. Примечания к главе 5

Глава 6. Обработка строк

6.1. Обзор и мотивация
6.2. Основные приемы и принципы обработки строк
6.3. Специализированные задачи обработки строк
6.4. Поиск совпадений в строках
6.4.1. Решения с использованием библиотечных функций
6.4.2. Алгоритм Кнута–Морриса–Пратта
6.4.3. Поиск совпадений в строках на двумерной сетке
6.5. Обработка строк с применением динамического программирования
6.5.1. Регулирование строк (редакционное расстояние)
6.5.2. Поиск наибольшей общей подпоследовательности
6.5.3. Неклассические задачи обработки строк с применением динамического программирования
6.6. Суффиксный бор, суффиксное дерево, суффиксный массив
6.6.1. Суффиксный бор и его приложения
6.6.2. Суффиксное дерево
6.6.3. Практические приложения суффиксного дерева
6.6.4. Суффиксный массив
6.6.5. Практические приложения суффиксного массива
6.7. Решения упражнений, не помеченных звездочкой
6.8. Примечания к главе 396

Глава 7. (Вычислительная) Геометрия

7.1. Обзор и мотивация
7.2. Основные геометрические объекты и библиотечные функции для них
7.2.1. Нульмерные объекты: точки
7.2.2. Одномерные объекты: прямые
7.2.3. Двумерные объекты: окружности
7.2.4. Двумерные объекты: треугольники
7.2.5. Двумерные объекты: четырехугольники
7.2.6. Замечания о трехмерных объектах
7.3. Алгоритмы для многоугольников с использованием библиотечных функций
7.3.1. Представление многоугольника
7.3.2. Периметр многоугольника
7.3.3. Площадь многоугольника
7.3.4. Проверка многоугольника на выпуклость
7.3.5. Проверка расположения точки внутри многоугольника
7.3.6. Разделение многоугольника с помощью прямой линии
7.3.7. Построение выпуклой оболочки множества точек
7.4. Решения упражнений, не помеченных звездочкой
7.5. Замечания к главе

Мой профиль

Глава 8. Более сложные темы

8.1. Обзор и мотивация
8.2. Более эффективные методы поиска
8.2.1. Метод поиска с возвратами с применением битовой маски
8.2.2. Поиск с возвратами с интенсивным отсечением
8.2.3. Поиск в пространстве состояний с применением поиска в ширину или алгоритма Дейкстры
8.2.4. Встреча в середине (двунаправленный поиск)
8.2.5. Поиск, основанный на имеющейся информации: A* и IDA*
8.3. Более эффективные методы динамического программирования
8.3.1. Динамическое программирование с использованием битовой маски
8.3.2. Некоторые общие параметры (динамического программирования)
8.3.3. Обработка отрицательных значений параметров с использованием метода смещения
8.3.4. Превышение лимита памяти? Рассмотрим использование сбалансированного бинарного дерева поиска как таблицы
запоминания состояний
8.3.5. Превышение лимита памяти/времени? Используйте более эффективное представление состояния
8.3.6. Превышение лимита памяти/времени? Отбросим один параметр, будем восстанавливать его по другим параметрам
8.4. Декомпозиция задачи
8.4.1. Два компонента: бинарный поиск ответа и прочие
8.4.2. Два компонента: использование статической задачи RSQ/RMQ
8.4.3. Два компонента: предварительная обработка графа
и динамическое программирование
8.4.4. Два компонента: использование графов
8.4.5. Два компонента: использование математики
8.4.6. Два компонента: полный поиск и геометрия
8.4.7. Два компонента: использование эффективной структуры данных
8.4.8. Три компонента
8.5. Решения упражнений, не помеченных звездочкой
8.6. Замечания к главе

Глава 9. Малораспространенные темы

Общий обзор и мотивация
9.1. Задача 2SAT
9.2. Задача о картинной галерее
9.3. Битоническая задача коммивояжера
9.4. Разбиение скобок на пары
9.5. Задача китайского почтальона
9.6. Задача о паре ближайших точек
9.7. Алгоритм Диница
9.8. Формулы или теоремы
9.9. Алгоритм последовательного исключения переменных, или метод Гаусса
9.10. Паросочетание в графах
9.11. Кратчайшее расстояние на сфере (ортодромия)
9.12. Алгоритм Хопкрофта–Карпа
9.13. Вершинно и реберно не пересекающиеся пути
9.14. Количество инверсий
9.15. Задача Иосифа Флавия
9.16. Ход коня
9.17. Алгоритм Косараджу
9.18. Наименьший общий предок
9.19. Создание магических квадратов (нечетной размерности)
9.20. Задача о порядке умножения матриц
9.21. Возведение матрицы в степень
9.22. Задача о независимом множестве максимального веса
9.23. Максимальный поток минимальной стоимости
9.24. Минимальное покрытие путями в ориентированном ациклическом графе
9.25. Блинная сортировка
9.26. Роалгоритм Полларда для разложения на множители целых чисел
9.27. Постфиксный калькулятор и преобразование выражений
9.28. Римские цифры
9.29. kя порядковая статистика
9.30. Алгоритм ускоренного поиска кратчайшего пути
9.31. Метод скользящего окна
9.32. Алгоритм сортировки с линейным временем работы
9.33. Структура данных «разреженная таблица»
9.34. Задача о ханойских башнях
9.35. Замечания к главе

Приложение А. uHunt
Приложение В. Благодарности
Список используемой литературы
Предметный указатель

Мой профиль

https://usaco.guide/
https://www.topcoder.com/thrive/search?tags[]=Competitive%20Programming%20Tutorials

Мой профиль

Collection of little techniques [Tutorial]

Мой профиль

link-cut tree с исходниками

Саша Лосев:

https://codeforces.com/contest/1681/problem/F - вот задача, которую я решил link-cut'ом. Идея очевиднейшая - немного преобразовать формулу и решить в лоб с помощью этой структуры
Либо решить ее другой техникой - Dynamic Connectivity Problem. Свежий туториал от от Антона Керножицкого(одного из авторов этой респы) по ней: https://codeforces.com/blog/entry/104443
https://usaco.guide/adv/offline-del?lang=cpp - реализация СНМ с откатами и примерами задач

Спасибо Саше Лосеву

Мой профиль

Ultimate Topic List

Мой профиль

https://usaco.guide/general/intro-cp?lang=cpp

Мой профиль

https://ru.algorithmica.org/

Мой профиль

https://www.topcoder.com/thrive/search?tags[]=Competitive%20Programming%20Tutorials'