Серия блога
Алгоритмические основы
- #1
Динамическое программирование: базовые шаблоны линейного и двумерного DP
Динамическое программирование — не про «магические формулы», а про дисциплину: описать состояние, записать переход, инициализировать базу. На двух задачах — «лестница» (1D DP) и «максимум суммы по пути в сетке» (2D DP) — разбираем шаблон, сигналы в условии и ловушки порядка обхода и переполнения.
- #2
Префиксные суммы: от 1D к 2D и подсчёту на прямоугольниках
Префиксные суммы превращают повторяющиеся диапазонные запросы из O(n) в O(1) — после линейной препроцессинга. Шаблон 1D, переход к 2D через формулу включений-исключений, классика подсчёта подотрезков с заданной суммой через prefix + hashmap. Три задачи нарастающей сложности, типичные ловушки и переход к более тяжёлым структурам, когда массив начинает изменяться.
- #3
Бинпоиск по ответу: когда применять и как выбирать инвариант
Бинпоиск по ответу превращает поиск числа в серию проверок: на каждом шаге проверяем кандидата за O(n) и сужаем диапазон вдвое. Главная сложность — не код, а выбор инварианта и доказательство монотонности. Две задачи-иллюстрации (распил досок и минимаксная разрезка массива), шаблон с двумя формами цикла, типичные ловушки границ и связь с жадными алгоритмами.
- #4
Жадные алгоритмы и exchange argument: как доказать оптимальность
Жадный алгоритм строит решение шаг за шагом, на каждом шаге выбирая локально лучшее. Метод доказательства корректности — exchange argument: показать, что любое отличающееся решение можно «обменять» на жадное, не ухудшив стоимость. Шаблон выбора (отсортировать по правильному ключу), две классические задачи-иллюстрации с разной структурой жадного, типичные ошибки и грань между жадным и DP.
- #5
Графы: BFS, DFS и базовые задачи поиска и связности
Графы — раздел, через который проходит половина задач выше CF 1300. Компактный шаблон представления списками смежности, BFS и DFS с кодом на Python и C++, разница между ними, поиск компонент через DSU и через обход. Три задачи (число островов, двудольность, число пар) и типичные ловушки: переполнение стека рекурсии, забытый `visited[start]`.
- #6
Two pointers и скользящее окно: шаблон и его варианты
Two pointers и sliding window — два близких шаблона с разными предпосылками. Two pointers работает на отсортированных данных и двигает указатели независимо. Sliding window поддерживает окно [l, r] на исходном массиве, расширяет и сжимает его при сохранении инварианта. Три задачи-иллюстрации (CF 1300, 1500, 1700) с кодом на Python и C++ и разбор типичных ловушек.
- #7
Рекурсия и перебор с отсечениями: шаблоны и переход к DP
Рекурсия и backtracking — базовая техника для задач, где нужно перебрать структурно сложное множество (подмножества, перестановки, разбиения). Четыре уровня: чистая рекурсия по дереву решений, перебор с отсечениями, мемоизация, перевод в итеративный DP. Две задачи-иллюстрации (subset-sum и подсчёт способов разменять сумму монетами), сигналы в условии и типичные ошибки.