Блог CodePal
Разборы задач, наблюдения об алгоритмическом программировании, апдейты продукта.
Шаблон prefix + hashmap через классическую трансформацию: вычитаем 1 из каждого элемента, и условие «сумма равна длине» становится «сумма подотрезка равна 0». Сумма равна нулю эквивалентна равенству префиксов P[l-1] = P[r], ответ — число пар индексов с одинаковым префиксом. Разбор всех трёх примеров условия, код на Python и C++, крайние случаи.
Разбор задачи показывает идею, но не делает её доступной в полевых условиях. Между «я понял» и «я могу воспроизвести через неделю» — несколько дней целенаправленной практики. Гайд предлагает структуру: пересборка с нуля без подсмотра, цикл на 3 дня с однотипными задачами, 7-дневный план с интервальным повторением. Типичные ошибки самоподготовки и роль AI-партнёра на этапе закрепления.
Линейный DP с тремя состояниями: для каждого дня держим тройку «дней отдыха при условии, что закончили отдыхом / соревнованием / залом». Тип дня задаёт допустимые переходы; запрет двух одинаковых активностей подряд — структуру связей. Сложность O(n), память O(1) после rolling. Код на Python и C++, разбор всех трёх примеров условия и крайние случаи.
Префиксные суммы на трёх уровнях: одномерный шаблон превращает диапазонный запрос из O(n) в O(1), двумерный обобщает через включения-исключения, prefix + hashmap решает подсчёт подотрезков с заданной суммой за O(n). На каждой ступени — код на Python и C++, переход как осознанная замена состояния, типичные ловушки и план тренировки.
Задача регионального ICPC, где «нестандартное состояние» — это пара (остаток по модулю d, накопленная сумма цифр), а переход — приписывание цифры 0–9 к строящемуся числу. BFS даёт наименьшую длину; перебор цифр в порядке 0..9 даёт лексикографически минимальный ответ. В статье — разбор всех примеров, код на Python и C++ с восстановлением пути, крайние случаи.
Рекурсия и backtracking — базовая техника для задач, где нужно перебрать структурно сложное множество (подмножества, перестановки, разбиения). Четыре уровня: чистая рекурсия по дереву решений, перебор с отсечениями, мемоизация, перевод в итеративный DP. Две задачи-иллюстрации (subset-sum и подсчёт способов разменять сумму монетами), сигналы в условии и типичные ошибки.
Two pointers и sliding window — два близких шаблона с разными предпосылками. Two pointers работает на отсортированных данных и двигает указатели независимо. Sliding window поддерживает окно [l, r] на исходном массиве, расширяет и сжимает его при сохранении инварианта. Три задачи-иллюстрации (CF 1300, 1500, 1700) с кодом на Python и C++ и разбор типичных ловушек.
Отладка — отдельный навык, без которого алгоритмическое мышление не превращается в зачтённые задачи. Подход в четыре шага: воспроизвести ошибку на минимальном входе, бисекция бага через принты, stress test против простого решения, чек-лист крайних случаев. Отдельная секция — самодисциплина на контесте: когда переключаться на следующую задачу и когда переписывать с нуля.
Дан массив весов запросов и длина окна k; для каждой позиции найти максимум в окне последних k и сложить все максимумы по модулю 10^9 + 7. Прямой подход за O(n·k) не проходит, лекарство — монотонный дек: убывающая последовательность индексов, голова = индекс максимума, амортизированно O(n). В статье — трассировка примера, код на Python и C++, крайние случаи и типичные ошибки.
Канонический линейный DP с переходом на 1, 2 и 3 шага назад: dp[i] = минимум из «обслужили i одного», «i и i-1 парой», «i, i-1, i-2 тройкой». Сложность O(n), память O(n) или O(1) при rolling-варианте. В статье — пересказ условия, рабочий код на Python и C++, обоснование корректности через принцип оптимальности, разбор типичных ошибок (off-by-one, забытая база).
Жадные на трёх уровнях сложности с явной логикой, что ломается между ступенями. Ступень 1 — exchange argument на CF ~1200. Ступень 2 — жадный с переносом остатка на CF ~1500 (next_cheaper через монотонный стек). Ступень 3 — жадный сломался, спасает DP с тем же порядком обхода на CF ~1900. На каждой ступени — код на Python и C++ и разбор того, что усложнилось в состоянии.
Шаблон: отсортировать массив и пройтись двумя указателями так, чтобы для каждого левого индекса найти максимальный правый, при котором разница значений ≤ k. Далее — комбинаторика: фиксируем минимум, остальные m-1 выбираем из «правого окна» как C(окно, m-1). Сложность O(n log n). В статье — рабочий код на Python и C++ с факториалами по модулю и разбор примеров.
Графы — раздел, через который проходит половина задач выше CF 1300. Компактный шаблон представления списками смежности, BFS и DFS с кодом на Python и C++, разница между ними, поиск компонент через DSU и через обход. Три задачи (число островов, двудольность, число пар) и типичные ловушки: переполнение стека рекурсии, забытый `visited[start]`.
Карта роста рейтинга на Codeforces: пять полос (800–1000, 1100–1300, 1400–1600, 1700–1900, 2000+), ключевые темы каждой, признаки готовности к переходу, типичные тупики. На каждой полосе — 3–5 техник, которые держат прогресс. Подход к самопроверке, как замечать застой, как чередовать практику и теорию.
Жадный алгоритм строит решение шаг за шагом, на каждом шаге выбирая локально лучшее. Метод доказательства корректности — exchange argument: показать, что любое отличающееся решение можно «обменять» на жадное, не ухудшив стоимость. Шаблон выбора (отсортировать по правильному ключу), две классические задачи-иллюстрации с разной структурой жадного, типичные ошибки и грань между жадным и DP.
Распределение n задач между k работниками с минимизацией максимальной нагрузки — NP-трудная задача. При малых n решается backtracking-ом с тремя отсечениями: сортировка по убыванию (большие первыми), branch-and-bound по текущему лучшему, симметрия по одинаковым нагрузкам. Разбор: идея, трассировка, код на Python и C++, типичные ошибки.
Три задачи нарастающей сложности на бинпоиск по ответу. Ступень 1 — Aggressive Cows: жадная проверка для расстановки k точек с максимальным минимумом расстояния. Ступень 2 — минимизация T при темпах t_i через сумму делений. Ступень 3 — максимизация медианы через k операций +1 с exchange argument. Эволюция проверки от элементарной до нетривиальной.
BFS на прямоугольной сетке n×m с препятствиями: от старта строим расстояния по уровням, очередь обходит клетки в порядке возрастания дистанции, и первая распакованная финишная клетка имеет минимальное число шагов. Сложность O(n·m). Идея, псевдокод, код на Python и C++, типичные ошибки и крайние случаи (старт=финиш, нет пути, стартовая клетка-стена).
Bitmask DP по подмножеству использованных элементов: dp[mask] — число перестановок mask в первые |mask| позиций так, чтобы все частичные суммы были «хорошими». Сумма по маске считается за O(2^n) через рекуррент по младшему биту. Сложность O(n · 2^n), память O(2^n). Идея, ход руками на n=4, код на Python и C++, крайние случаи и типичные ошибки реализации.
Бинпоиск по ответу превращает поиск числа в серию проверок: на каждом шаге проверяем кандидата за O(n) и сужаем диапазон вдвое. Главная сложность — не код, а выбор инварианта и доказательство монотонности. Две задачи-иллюстрации (распил досок и минимаксная разрезка массива), шаблон с двумя формами цикла, типичные ловушки границ и связь с жадными алгоритмами.
Codeforces — самая большая регулярная среда мировых контестов; acmp.ru — русскоязычный архив с возрастающей сложностью; Яндекс Контест — инфраструктура с архивом контестов от Яндекс Кубка. У каждой платформы своя сильная сторона. Сравнительная таблица, рекомендации по входу с нуля, план переключения между ними по мере роста, упоминание ICPC и Иннополис Open как следующих ступеней.
Игра двух игроков на массиве конфет: Alice ест слева, Bob справа, на каждом ходу нужно набрать минимальный набор с весом строго больше, чем съел соперник в предыдущем ходу. Чистая реализация на двух указателях за O(n) — без вложенных if'ов и спецслучаев «массив кончился». Разбор задачи «Alice, Bob and Candies» с CF: идея, псевдокод, код на Python и C++, проверка на всех 7 примерах, крайние случаи.
BFS — это не одна задача, а три последовательные ступени. На CF ~1300 — простой обход из одной вершины. На ~1700 — multi-source BFS из набора вершин одновременно. На ~2100 — BFS на «расширенном» графе, где состояние = (вершина, дополнительный параметр). Три абстрактных канонических шаблона с псевдокодом, кодом и явным проговариванием, что усложняется между ступенями.
Классическая 2D-задача: найти прямоугольную подматрицу с максимальной суммой в матрице с возможными отрицательными элементами. Решение — Kadane 2D: перебираем пары строк, сжимаем матрицу в массив сумм по столбцам, применяем 1D-Kadane за O(M). Итог — O(N²·M). Разбор задачи с acmp: код на Python и C++, проверка на примерах, крайние случаи.
Классический tree DP: проходим DFS по корневому дереву, для каждой вершины храним массив «сколько подвершин на расстоянии d». При сшивании поддеревьев свёртка двух массивов даёт пары длиной ровно k, проходящие через текущую вершину как точку поворота. Сложность O(n·k). Код на Python и C++, проверка на обоих примерах условия и обзор крайних случаев.
Префиксные суммы превращают повторяющиеся диапазонные запросы из O(n) в O(1) — после линейной препроцессинга. Шаблон 1D, переход к 2D через формулу включений-исключений, классика подсчёта подотрезков с заданной суммой через prefix + hashmap. Три задачи нарастающей сложности, типичные ловушки и переход к более тяжёлым структурам, когда массив начинает изменяться.
DP — это не одна техника, а семейство, в котором сложность растёт через расширение состояния. Три задачи (CF ~1200, ~1600, ~2000): максимум независимой суммы, рюкзак 0/1 и поиск минимального гамильтонова пути. На каждой ступени проговариваем, какой параметр добавляется в состояние, как меняется переход и почему сложность растёт именно так.
Если граф большой, а вопросов о маршруте много — стоит сделать одно BFS и потом отвечать на каждый вопрос за O(1). Разбор задачи «Navigation System»: BFS по обратному графу из t даёт расстояние любой вершины до t, после чего проход по выбранному маршруту проверяет каждый шаг через сравнение dist[u] − 1 vs dist[w] и подсчёт альтернативных оптимумов.
Динамическое программирование — не про «магические формулы», а про дисциплину: описать состояние, записать переход, инициализировать базу. На двух задачах — «лестница» (1D DP) и «максимум суммы по пути в сетке» (2D DP) — разбираем шаблон, сигналы в условии и ловушки порядка обхода и переполнения.
Когда корни уравнения гарантированно целые и лежат в небольшом окне, цикл с прямой подстановкой — самое естественное решение. Разбор задачи «Кубическое уравнение»: алгоритм за O(N), где N = 201, рабочий код на Python и C++, разбор ловушки переполнения int при A·x³ и проверка на всех трёх примерах.
Задача сводится к бинпоиску по количеству дней d: проверяем, можно ли написать m страниц за d дней. Монотонность доказывается напрямую, жадная проверка за O(n) — сортировка по убыванию плюс раскладка по дням. Разбор включает псевдокод, код на Python и C++, проверку на всех 5 примерах, случай с ответом −1, крайние случаи и типичные ошибки.
Полный гайд по чтению алгоритмического условия: что именно проверять в формулировке, ограничениях, формате ввода/вывода и примерах. Приёмы разметки текста, типичные ловушки (забытое ограничение, смещение индексов, пропущенные крайние случаи) и как по таблице «ограничение → допустимая сложность» быстро выбрать класс алгоритма ещё до написания кода.
Задача сводится к DP по вершине и моменту времени с запретом находиться в той же вершине или идти по ребру навстречу врагу. Ключевая лемма — если ответ существует, он не превосходит 2N+1. Даются модель задачи, простой код для частичных баллов O(N·M) и идея полного решения O(N·M).
Пара позиций (a_i, b_i) — ребро графа между значениями. Операция свапа — выбор ориентации ребра. Задача сводится к ориентации всех рёбер так, чтобы максимизировать число вершин с входящим ребром плюс число вершин с исходящим. Разобрано простое решение 2^n для n ≤ 18 и идея O(n) для полного балла через разложение графа на циклы и пути.
Ключевое наблюдение: проигравшая карта возвращается наверх руки, поэтому в каждом раунде играет указатель на верхнюю карту каждого из игроков. Симуляция за O(n) на одну конфигурацию руки, перебор пар карт для свапа даёт решение на частичные баллы. Полное решение за O(n log n) — отдельный выход на префиксные минимумы и бинарный поиск.
Задача сводится к выбору лучшего первого взрыва: после него все остальные слитки собираются гарантированно. Ответ равен суммарному золоту минус минимальная потеря внутренности квадрата взрыва. Префиксные суммы дают O(m·n) решение.
Конструктивная задача на замощение крыши одинаковыми листами без поворотов. Ключевое наблюдение: корректное замощение обязательно идёт либо по строкам, либо по столбцам. Проверка выражается двумя условиями делимости, решение за O(1) на крышу.
Жадный алгоритм с exchange argument: когда выгодно готовить то, что меньше остужает. Формула количества порций за O(1), разбор крайних случаев, рабочий код на Python и C++, проверка на всех примерах условия.