← Вернуться в блог

Серия блога

Летняя подготовка: пик

6 статей

  1. #1

    Тренировочная сессия 18: кратчайшие пути алгоритмом Дейкстры

    Первая сессия «Пика»: коридор поднимается до ~CF 1900–2400. Один приём — алгоритм Дейкстры — в трёх обстановках: прямой поиск пути с восстановлением маршрута, вершины-состояния и второй запуск поверх первого, когда в задаче две несовместимые метрики. Разбираем, почему нужны неотрицательные веса и чем заменить алгоритм, если это условие нарушено. Две задачи Codeforces 1900.

  2. #2

    Тренировочная сессия 19: минимум как точка деления отрезка

    Вторая сессия «Пика» — одно наблюдение в двух реализациях. Минимум разрезает отрезок на независимые части, а каждый элемент владеет тем куском, где он наименьший. Первая задача пользуется этим рекурсивно, вторая — считает границы владения монотонным стеком за линию и суммирует вклады. Разбираем, откуда берётся асимметрия сравнений при равных значениях и почему без неё ответ уезжает вдвое.

  3. #3

    Тренировочная сессия 20: бинарный поиск по ответу с проверкой через битовые маски

    Третья сессия «Пика» — бинарный поиск по ответу, где вся работа делается внутри проверки. Разбираем две роли битовых масок: маска как сжатие объекта, когда различных объектов оказывается не больше 256, и маска как состояние перебора, заменяющая 40320 порядков на 256 подмножеств. Плюс приём «перенести компоненту состояния в значение динамики». Две задачи Codeforces 2000–2200.

  4. #4

    Тренировочная сессия 21: двоичные подъёмы — LCA и максимум на пути

    Четвёртая сессия «Пика» — единственная в цикле, где приёма честно два: во второй задаче остов Краскалом и максимум на пути через двоичные подъёмы нужны вместе, одно без другого её не решает. Разбираем таблицу подъёмов как заготовку, систему непересекающихся множеств как подчинённый инструмент и формулу пересчёта остова с обязательным ребром.

  5. #5

    Тренировочная сессия 22: слияние от меньшего к большему

    Предпоследняя сессия цикла — слияние от меньшего к большему. Элемент переезжает только в структуру как минимум вдвое большего размера, значит переездов у него не больше логарифма: оценка ведётся от элемента, а не от формы дерева. Разбираем три условия применимости приёма, офлайн-обработку запросов и границу, за которой нужна уже центроидная декомпозиция. Две задачи Codeforces 2300–2400.

  6. #6

    Тренировочная сессия 23: экзамен — три задачи возрастающей сложности без разбора по шагам

    Экзаменационная сессия. Разбора по шагам перед решением нет: сначала три условия возрастающей сложности и правила контеста, потом — полные разборы всех трёх. В теории вместо алгоритма два контестных приёма: как читать ограничения задачи, чтобы понять нужную сложность, и как устроить стресс-тест, который ловит ошибку до отправки. Код на Python и C++, псевдокод, крайние случаи, типичные ошибки.