Серия блога
Стратегия победы
- #1
Стратегия победы: DP — от очевидного шаблона к ёмкому состоянию
DP — это не одна техника, а семейство, в котором сложность растёт через расширение состояния. Три задачи (CF ~1200, ~1600, ~2000): максимум независимой суммы, рюкзак 0/1 и поиск минимального гамильтонова пути. На каждой ступени проговариваем, какой параметр добавляется в состояние, как меняется переход и почему сложность растёт именно так.
- #2
Стратегия победы: графы — от BFS к многоходовым обходам
BFS — это не одна задача, а три последовательные ступени. На CF ~1300 — простой обход из одной вершины. На ~1700 — multi-source BFS из набора вершин одновременно. На ~2100 — BFS на «расширенном» графе, где состояние = (вершина, дополнительный параметр). Три абстрактных канонических шаблона с псевдокодом, кодом и явным проговариванием, что усложняется между ступенями.
- #3
Стратегия победы: бинпоиск по ответу — траектория 1200 → 1500 → 2000
Три задачи нарастающей сложности на бинпоиск по ответу. Ступень 1 — Aggressive Cows: жадная проверка для расстановки k точек с максимальным минимумом расстояния. Ступень 2 — минимизация T при темпах t_i через сумму делений. Ступень 3 — максимизация медианы через k операций +1 с exchange argument. Эволюция проверки от элементарной до нетривиальной.
- #4
Стратегия победы: жадные — когда жадность ломается и как её спасти
Жадные на трёх уровнях сложности с явной логикой, что ломается между ступенями. Ступень 1 — exchange argument на CF ~1200. Ступень 2 — жадный с переносом остатка на CF ~1500 (next_cheaper через монотонный стек). Ступень 3 — жадный сломался, спасает DP с тем же порядком обхода на CF ~1900. На каждой ступени — код на Python и C++ и разбор того, что усложнилось в состоянии.
- #5
Стратегия победы: префиксные суммы — от 1D к 2D и подсчёту на подотрезках
Префиксные суммы на трёх уровнях: одномерный шаблон превращает диапазонный запрос из O(n) в O(1), двумерный обобщает через включения-исключения, prefix + hashmap решает подсчёт подотрезков с заданной суммой за O(n). На каждой ступени — код на Python и C++, переход как осознанная замена состояния, типичные ловушки и план тренировки.