Всем привет!

Вчера состоялся финал ABBYY Cup 3.0! Хочется сказать большое спасибо всем-всем: кто решал контест, кто помогал его готовить, авторам задач и еще много кому! О том, как прошел День открытых дверей ABBYY, мы расскажем позже, а пока разборы:

Задача A

Утверждение: если прогулка начинается с дерева i и заканчивается в дереве j, то нужно выпилить все деревья до i, все деревья после j и все деревья с отрицательной эстетической привлекательностью между i и j. Для решения подзадачи A1 достаточно для каждой пары деревьев с одинаковой эстетической привлекательностью воспользоваться утверждением и выбрать максимум; ограничения позволяли сделать это хоть за O(n²), хоть за O(n³). Для решения подзадачи A2 требуется такое утверждение: сколько бы ни было деревьев с одинаковой эстетической привлекательностью, нам всегда выгодно рассматривать только пару из самого левого и самого правого таких деревьев. Тогда количество различных рассматриваемых пар сократится до O(n) (с O(n²)), дальше можно делать что угодно, например, считать частичные суммы или брать сумму на отрезке.

Задача B

Для решения подзадачи B1 требовалось проэмулировать поведение Брабобрея в точности так, как описано в условии. Для решения подзадачи B2 достаточно для каждого завершающего бобра хранить взведённый флаг-единичку. Назовём завершающим бобром такого бобра i, что справа от него нет бобра i + 1 (то есть в случае запроса, включающего бобров i и i + 1 придётся запускать Брабобрей ещё один раз). Тогда при обмене пары бобров i и j местами будет всего четыре кандидата, где состояние флага может измениться: i - 1, i, j - 1, j. Ответ на запрос — это просто количество завершающих бобров на отрезке, что уже является классической задачей.

Задача C

Для решения подзадачи C1 можно либо посчитать динамику, либо жадно вычитать наибольшую цифру — несложно доказывается, что всегда требуется вычитать именно наибольшую цифру. Для подзадачи C2 достаточно посчитать динамику для первого миллиона, разбить мысленно число на две группы цифр — старшие разряды и младшие — и выполнять не одно вычитание, а целую серию вычитаний, чтобы мгновенно минимизировать младшие разряды. Для решения подзадачи C3 необходимо уйти от желания хранить в параметрах динамики само число, а хранить лишь количество разрядов.

Задача D

Совершенно очевидно, что судьба бобрактора такова: либо мы пройдём по стрелкам и выберемся, либо уткнёмся в цикл. Во втором случае необходимо найти длину цикла l, но тогда нам нужен лишь остаток от деления времени на длину цикла. Таким образом, мы мысленно избавились от второго случая. Для решения подзадачи D1 достаточно проэмулировать поведение бобрактора, сохраняя на каждом шаге время последнего посещения текущей точки (чтобы определить длину цикла, когда мы на него наступим второй раз). Для решения подзадач D2 и D3 требовалось построить граф перемещений бобрактора, а затем обработать каждый из тестов мультитеста, причём в D2 граф можно построить в лоб, да и найти ответ на каждый тест — пройти по графу в лоб. В D3 предлагается использовать логарифмические структуры данных. В целом, идея решения лежит на поверхности; задача представляет интерес именно с технической точки зрения.

Задача E

Для решения подзадачи E1 необходимо прийти к следующему утверждению: если на ребре x → y есть пометки x и y, идущие подряд, то такое ребро может генерировать искомый путь. Назовём такое ребро инициирующим. Несложно понять, что, зафиксировав инициирующее ребро, дальнейший путь в обе стороны восстанавливается однозначно. Теперь надо понять, что достаточно рассматривать только инициирующие рёбра. Рассмотрим любой требуемый путь в графе. Он содержит p вершин и p - 1 рёбер. Но тогда по принципу Дирихле хотя бы одно ребро должно содержать как минимум две пометки. Пусть какое-то ребро x → y содержит пометки a b, (a, b) ≠ (x, y). Но тогда разрежем этот путь на два по ребру x → y и заметим, что тогда какой-то из двух подпутей уж точно содержит больше пометок, чем есть рёбер. Рассуждая подобным образом можно прийти к выводу, что найдётся хотя бы одно ребро x → y с пометками x и y. Если ни одного инициирующего ребра нет, то искомого пути не существует. Путь, сгенерированный инициирующим ребром — это кратчайший валидный путь для данного инициирующего ребра. К нему можно дописывать входящие и исходящие хвосты так, чтобы путь становился длиннее. Хвосты не должны содержать инициирующих рёбер, потому что инициирующие рёбра генерируют свои пути. Любой валидный путь — это путь из троек ("входящий хвост", "путь инициирующего ребра", "исходящий хвост"), соединённых между собой рёбрами без пометок. Для решения подзадачи E2 можно предподсчитать все хвосты и все сгенерированные инициирующими рёбрами пути, а затем динамикой посчитать количество путей фиксированной длины.