Skip to content

Олимпиадное программирование — заметки

Список статей

Олимпиадное программирование¶

Тут будут написаны статьи, что вы увидите в ближайшем будущем.

🟢 Часть I — Базовые техники¶

1. Введение¶

[ ] Языки программирования в олимпиадах — В разработке
[ ] Ввод и вывод данных (I/O) — В разработке
[ ] Работа с числами и типами данных — В разработке
[ ] Математическая база для олимпиадника — В разработке
[ ] Соревнования и ресурсы — В разработке

2. Оценка сложности алгоритмов¶

[ ] Правила подсчёта сложности — В разработке
[ ] Классы сложности (O-нотация) — В разработке
[ ] Как оценивать эффективность решений — В разработке
[ ] Максимальная сумма подмассива (алгоритм Кадане) — В разработке

3. Сортировки и бинарный поиск¶

[ ] Теория сортировок — В разработке
[ ] Сортировки в C++ — В разработке
[ ] Бинарный поиск — В разработке

4. Базовые структуры данных¶

[ ] Динамические массивы (vector) — В разработке
[ ] Множества (set, multiset) — В разработке
[ ] Словари (map, unordered_map) — В разработке
[ ] Итераторы и диапазоны — В разработке
[ ] Другие структуры STL — В разработке

5. Полный перебор¶

[ ] Генерация подмножеств — В разработке
[ ] Генерация перестановок — В разработке
[ ] Backtracking — В разработке
[ ] Оптимизация перебора (pruning) — В разработке
[ ] Meet in the Middle — В разработке

6. Жадные алгоритмы¶

[ ] Монетная задача — В разработке
[ ] Задачи на расписания — В разработке
[ ] Минимизация сумм — В разработке
[ ] Сжатие данных (Huffman) — В разработке

7. Динамическое программирование¶

[ ] Монетная задача (DP) — В разработке
[ ] Наибольшая возрастающая подпоследовательность (LIS) — В разработке
[ ] Пути в сетке — В разработке
[ ] Задача о рюкзаке — В разработке
[ ] Расстояние Левенштейна — В разработке
[ ] Подсчёт разбиений и покрытий — В разработке

8. Амортизированный анализ¶

[ ] Метод двух указателей — В разработке
[ ] Ближайший меньший элемент — В разработке
[ ] Скользящее окно — В разработке

9. Запросы на отрезках¶

[ ] Статические запросы — В разработке
[ ] Fenwick Tree (Binary Indexed Tree) — В разработке
[ ] Segment Tree — В разработке
[ ] Продвинутые техники — В разработке

10. Битовые операции¶

[ ] Представление чисел в битах — В разработке
[ ] Битовые операции — В разработке
[ ] Маски подмножеств — В разработке
[ ] DP по битмаске — В разработке

🔵 Часть II — Алгоритмы на графах¶

11. Основы графов¶

[ ] Термины теории графов — В разработке
[ ] Представление графа (списки смежности, матрица) — В разработке
[ ] Ориентированные и неориентированные графы — В разработке
[ ] Взвешенные графы — В разработке
[ ] Разреженные и плотные графы — В разработке

12. Обход графа¶

[ ] DFS (поиск в глубину) — В разработке
[ ] BFS (поиск в ширину) — В разработке
[ ] Поиск компонент связности — В разработке
[ ] Проверка двудольности — В разработке
[ ] Поиск циклов — В разработке
[ ] Восстановление пути — В разработке

13. Кратчайшие пути¶

[ ] Алгоритм Беллмана–Форда — В разработке
[ ] Алгоритм Дейкстры — В разработке
[ ] Floyd–Warshall — В разработке
[ ] Поиск кратчайших путей в DAG — В разработке
[ ] Обнаружение отрицательных циклов — В разработке

14. Алгоритмы на деревьях¶

[ ] Обход дерева — В разработке
[ ] Диаметр дерева — В разработке
[ ] Все максимальные пути — В разработке
[ ] Бинарные деревья — В разработке
[ ] Поддеревья и подсчёты — В разработке

15. Остовные деревья¶

[ ] Алгоритм Крускала — В разработке
[ ] Структура Union-Find (DSU) — В разработке
[ ] Алгоритм Прима — В разработке
[ ] Минимальный и максимальный остов — В разработке

16. Ориентированные графы¶

[ ] Топологическая сортировка — В разработке
[ ] DP на DAG — В разработке
[ ] Поиск циклов в ориентированном графе — В разработке
[ ] Функциональные графы — В разработке

17. Сильная связность¶

[ ] Алгоритм Косараджу — В разработке
[ ] Алгоритм Тарьяна — В разработке
[ ] Задача 2-SAT — В разработке

18. Запросы на деревьях¶

[ ] Двоичное поднятие (Binary Lifting) — В разработке
[ ] LCA (наименьший общий предок) — В разработке
[ ] Euler Tour Technique — В разработке
[ ] Офлайн-алгоритмы на деревьях — В разработке

19. Пути и циклы¶

[ ] Эйлеровы пути и циклы — В разработке
[ ] Гамильтоновы пути — В разработке
[ ] Последовательности де Брёйна — В разработке
[ ] Тур коня — В разработке

20. Потоки и разрезы¶

[ ] Алгоритм Форда–Фалкерсона — В разработке
[ ] Edmonds–Karp — В разработке
[ ] Максимальное паросочетание — В разработке
[ ] Минимальный разрез — В разработке
[ ] Покрытия путями — В разработке

🟣 Часть III — Продвинутые темы¶

21. Теория чисел¶

[ ] Простые числа и решето Эратосфена — В разработке
[ ] Разложение на множители — В разработке
[ ] Модульная арифметика — В разработке
[ ] Быстрое возведение в степень — В разработке
[ ] Обратный элемент по модулю — В разработке
[ ] Китайская теорема об остатках — В разработке
[ ] Диофантовы уравнения — В разработке

22. Комбинаторика¶

[ ] Биномиальные коэффициенты — В разработке
[ ] Числа Каталана — В разработке
[ ] Принцип включений-исключений — В разработке
[ ] Лемма Бёрнсайда — В разработке
[ ] Формула Кэли — В разработке

23. Матрицы¶

[ ] Операции над матрицами — В разработке
[ ] Быстрое возведение матрицы в степень — В разработке
[ ] Линейные рекуррентности — В разработке
[ ] Связь графов и матриц — В разработке

24. Теория вероятностей¶

[ ] Основы вычисления вероятностей — В разработке
[ ] Случайные величины — В разработке
[ ] Математическое ожидание — В разработке
[ ] Марковские цепи — В разработке
[ ] Рандомизированные алгоритмы — В разработке

25. Теория игр¶

[ ] Игровые состояния — В разработке
[ ] Игра Ним — В разработке
[ ] Теорема Шпрага–Гранди — В разработке
[ ] Игры на графах — В разработке

26. Строковые алгоритмы¶

[ ] Термины и основы — В разработке
[ ] Trie — В разработке
[ ] Префикс-функция (KMP) — В разработке
[ ] Z-функция — В разработке
[ ] Хеширование строк — В разработке
[ ] Суффиксные массивы — В разработке

27. √-алгоритмы¶

[ ] Декомпозиция по блокам — В разработке
[ ] Алгоритм Мо — В разработке
[ ] Комбинирование техник — В разработке

28. Деревья отрезков (углубление)¶

[ ] Lazy propagation — В разработке
[ ] Динамические деревья — В разработке
[ ] Двумерные деревья — В разработке

29. Геометрия¶

[ ] Комплексные числа — В разработке
[ ] Точки и прямые — В разработке
[ ] Площадь многоугольника — В разработке
[ ] Расстояния и пересечения — В разработке
[ ] Выпуклая оболочка — В разработке

30. Sweep Line¶

[ ] Точки пересечения — В разработке
[ ] Ближайшая пара точек — В разработке
[ ] Задача о выпуклой оболочке — В разработке