Серия блога
Летняя подготовка: плато
- #1
Тренировочная сессия 9: жадность по разрядам
Первая сессия «Плато»: планка поднимается до ~CF 1400–1500. Один приём в двух формах — собрать число по разрядам от старшего к младшему с проверкой достижимости остатка и подправить готовое число округлением вверх. Две задачи Codeforces с полным разбором: теория, доказательство корректности жадности, псевдокод, код на Python и C++, проверка на всех примерах, крайние случаи и типичные ошибки.
- #2
Тренировочная сессия 10: два указателя навстречу по отсортированному массиву
Вторая сессия «Плато». Один приём — два указателя навстречу по отсортированному массиву — в двух применениях: подсчёт пар с условием на сумму вместо двойного цикла и жадный проход, где левый указатель тратит заработанное правым. Разбираем, на какой ровно монотонности всё держится. Две задачи Codeforces 1400–1600 с полным разбором, кодом на Python и C++ и проверкой на всех примерах.
- #3
Тренировочная сессия 11: обход в глубину с состоянием вдоль пути
Третья сессия «Плато» — переход от массивов к деревьям. Один приём: обход в глубину, который тянет за собой накопленное вдоль пути состояние. Разбираем два его вида — счётчик подряд идущих вершин и максимум по всем предкам, — почему отсечение ветки целиком корректно и как не упасть по глубине рекурсии. Две задачи Codeforces 1500–1600 с кодом на Python и C++.
- #4
Тренировочная сессия 12: скользящее окно по отсортированному массиву
Четвёртая сессия «Плато». Один приём — скользящее окно по отсортированному массиву — в двух видах ограничения: на разброс значений и на стоимость подтягивания окна к правому краю. Разбираем, почему оптимальный набор оказывается непрерывным отрезком, почему граница окна не откатывается назад и чем окно отличается от встречных указателей. Две задачи Codeforces 1500–1600.
- #5
Тренировочная сессия 13: жадность на дереве
Пятая сессия «Плато». Один приём — жадность на дереве — в двух формах: свести сумму по выбранному множеству к независимым слагаемым и отсортировать, либо назначить каждой вершине крайнее допустимое значение, двигаясь по ограничениям от потомков. Разбираем обменный аргумент, проверку замкнутости набора и границу, за которой нужна уже динамика. Две задачи Codeforces 1600.
- #6
Тренировочная сессия 14: Z-функция — где строка совпадает сама с собой
Шестая сессия «Плато» — строки. Один приём: Z-функция. Что она означает, почему считается за линию, какие вопросы через неё выражаются одной строкой кода — от наибольшего перекрытия строки с самой собой до проверки «начало является концом и встречается в середине». Две задачи Codeforces 1600–1700 с полным разбором, кодом на Python и C++ и разбором крайних случаев.
- #7
Тренировочная сессия 15: динамика по префиксу с дополнительным состоянием
Седьмая сессия «Плато» — динамика по префиксу, где кроме позиции приходится помнить ещё одну величину. Две формы одного приёма: подсчётная, где состояние отвечает на вопрос «чем закончили», и оптимизирующая, где оно отвечает «сколько уже набрали». Разбираем, как выбирать состояние, как сворачивать память по слоям и где вместо динамики хватило бы жадности.
- #8
Тренировочная сессия 16: динамика по префиксам отсортированных данных
Восьмая сессия «Плато» — динамика по префиксам отсортированных данных. В одной задаче обменный аргумент доказывает, что из каждого списка берутся наибольшие элементы, в другой — что оптимальное сопоставление не пересекается. Оба раза именно доказательство превращает необозримый перебор в таблицу по префиксам. Разбираем, как такие аргументы выписывать и когда сортировка, наоборот, ломает задачу.
- #9
Тренировочная сессия 17: перекладка корня дерева
Девятая, финальная сессия «Плато» — перекладка корня. Первый проход считает ответ внутри поддерева, второй спускает вклад верхней части, и ответ получается для всех вершин сразу за линейное время. Разбираем три типовые формы перехода, условие обратимости вклада и почему порядок обходов важнее самой формулы. Две задачи Codeforces 1700–1800 с полным разбором, кодом на Python и C++.