Russian Code Cup 2013: разбираем задачи финала

23 сентября 2012 года состоялся финал чемпионата по программированию Russian Code Cup 2013.

Первое место занял Петр Митричев (кстати, чемпион RCC 2011). Второй приз взял Геннадий Короткевич, третье — Дмитрий Джулгаков.

Сегодня мы публикуем подробный разбор шести задач, которые были предложены финалистам RCC (спойлер: одна из них так и осталась нерешенной). В программе — сортировка невиданной быстроты, борьба с капибарным гриппом, путешествия роботов и многое другое.

Задача А. Терпение

Идея: Артем Васильев
Реализация: Артем Васильев
Разбор: Артем Васильев

Условие:
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

Хулиганы Петя и Вася сидят на невыносимо скучном уроке. Для того чтобы как-то развлечься, они решили поиграть с терпением учителя. Уровень недовольства учителя ребятами выражается целым числом x. Петя и Вася по очереди совершают различные мелкие и крупные шалости, Петя совершает шалость первым. После мелкой шалости уровень недовольства учителя увеличивается на 1, после крупной шалости — увеличивается в 2 раза. Тот ученик, после шалости которого недовольство учителя становится больше чем n, получает выговор от учителя и приходит после уроков с родителями к директору. Естественно, ни Вася, ни Петя такому исходу не рады, и поэтому каждый из них действует оптимально, чтобы избежать этого.

Ребята играют в эту игру каждый день. С каждым днем начальное недовольство учителя растет: в первый день оно равнялось 1, во второй день — 2, и так далее. В i-й день изначальное недовольство учителя учениками равно i. Всего в году ровно n учебных дней, то есть в последний день учебы недовольство учителя равно n и любая шалость учеников мгновенно выводит его из себя.

Отличнику Коле тоже очень скучно на уроке, ведь он уже знает все, что рассказывает учитель. Коля заметил странную игру Пети и Васи и легко выяснил, кто пойдет за родителями в каждый учебный день. Однажды Коля подметил, что Вася пошел за родителями ровно в k-й раз. Определите, в какой по счету учебный день это произошло?

Например, пусть n = 4. В первый день начальное недовольство учителя равно 1. Какую бы шалость ни совершил Петя, недовольство учителя станет равно 2. После этого Вася совершает крупную шалость, и недовольство учителя становится равно 4. Теперь, какую бы шалость ни совершил Петя, он получит выговор и пойдет за родителями. Во второй учебный день начальное недовольство учителя равно 2. Теперь Петя совершает крупную шалость и вынуждает Васю получить выговор. В третий учебный день Петя добивается того же эффекта, совершив мелкую шалость. В последний же — четвертый — учебный день Петя получит выговор, поскольку он должен совершить шалость первым. Таким образом, если Коля видит, что Вася пошел за родителями в первый раз, можно сделать вывод, что сейчас второй учебный день, а если Вася пошел за родителями во второй раз, то сейчас третий учебный день.

Формат входных данных
Первая строка содержит целое число T (1 ≤ T ≤ 105) — количество тестов. Каждая из следующих T строк содержат описание очередного теста: 2 целых числа n и k (1 ≤ n, k ≤ 1018).

Формат выходных данных
Для каждого теста выведите единственное число: a — день, в который Вася пошел за родителями в k-й раз, либо −1, если такой ситуации произойти не может. Выводите каждое из чисел в отдельной строке.

Разбор:
В условии была описана игра для двух участников. Состояние игры описывалось одним числом x, и игроки по очереди могли сделать один из двух ходов: заменить x на x+1 либо на 2x. Тот игрок, который первым написал число большее, чем n, проиграл. Следовало найти k по возрастанию числа x, такое, чтобы первый игрок имел выигрышную стратегию, если начальное число равнялось x.

Поскольку ограничения на n были достаточно большие, надо было понять структуру чисел, являющихся выигрышными позициями для игрока, который начинает из такого состояния. Мы покажем, что это множество представляется в виде объединения O(log n) отрезков подряд идущих чисел, в каждом из которых либо каждое число, либо каждое второе число — это выигрышная позиция для первого игрока.

Будем строить это множество рекурсивно. Пусть процедура F(n) возвращает множество всех таких отрезков, и при этом выполняется инвариант: игрок, сделавший ход в число большее, чем n, проигрывает.

Рассмотрим два случая. Пусть n — нечетное. Тогда любое четное число от 2 до n-1 — это выигрышная позиция, а любое нечетное — проигрышная. Покажем, что первый игрок всегда может сделать так, что он ходит из четной позиции, а его противник — из нечетной. Действительно, если первый игрок переводит x в число x+1, то второй игрок может перевести x+1 только в четное число. Осталось лишь заметить, что число n нечетное, и поэтому первый игрок всегда имеет ход, который не приводит к его поражению. Продолжая по индукции, получаем, что если первый игрок начинает с четного числа, то у него есть выигрышная стратегия. В случае, когда первый игрок начинает с нечетного числа, второй игрок использует ту же стратегию и выигрывает.

Теперь пусть n четное. Все нечетные позиции, которые больше n/2, выигрышны, поскольку удвоение такого числа сразу приводит к поражению; в таком случае выигрышность позиции определяется четностью числа оставшихся ходов. Заметим также, что позиция n/2 выигрышна, поскольку из n/2 можно получить n, и другой игрок обязательно превышает n своим следующим ходом.

Рассмотрим такое число l, которое будет больше, чем n/2; при этом позиция l является проигрышной. В зависимости от четности числа n/2 l равно либо n/2 + 1, либо n/2 + 2. Теперь рассмотрим все числа от l/2 до n/2 включительно. Все эти позиции будут выигрышными, поскольку если удвоить любое из этих чисел, получится число, большее n/2 и четное, а такая позиция проигрышна. Получили два отрезка, на первом из которых выигрышна каждая позиция, а на втором — каждая вторая.

Заметим, что остальные отрезки можно получить, вызвав F(l/2 — 1). Разбором случаев можно показать, что l/2 — 1 всегда равно n/4, округленному вниз. Убедимся в том, что требуемое свойство выполняется. Пусть x ≤ l/2 — 1. Тогда 2x ≤ l — 2 ≤ n/2, то есть все позиции, которые больше l/2 — 1, и в которые возможен ход из позиции, не превышающей l/2 – 1, являются выигрышными, и потому такой ход приведет к проигрышу.

При каждом рекурсивном вызове n уменьшается как минимум в 4 раза, поэтому программа работает за O(log n). После этого решить изначальную задачу становится просто. Так как все эти отрезки не пересекаются, можно пройтись по ним в возрастающем порядке и определять, попадает ли ответ в текущий отрезок. Если текущее k больше количества чисел на данном отрезке, то вычтем это количество из k и перейдем к следующему отрезку. Иначе мы можем получить k нужное нам число на этом отрезке и вывести его. Если такого отрезка не нашлось, следует вывести -1.

Задача B. Белоснежка и n гномов

Идея: Виталий Аксёнов
Реализация: Виталий Аксёнов, Николай Ведерников
Разбор: Николай Ведерников

Построим ориентированный граф из n вершин. Из вершины i будет выходить одно ребро в вершину ai. Если в этом графе существует цикл, то вершины, которые входят в него, будут входить и в набор, который требуется по условию задачи, так как сумма номеров вершин начал рёбер на цикле будет равна сумме номеров концов.

Пусть цикла в этом графе не существует. Тогда выберем любую вершину. Так как в графе цикла нет, то это ребро не ведет в неё саму. Переходим по ребру и оказываемся в другой вершине, из неё ребро не ведёт ни в первую, ни в саму себя, иначе бы цикл существовал. Действуя аналогично, мы окажемся в последней непосещённой вершине. Куда бы ни вело ребро из неё, мы получим цикл. Мы видим противоречие, следовательно, цикл есть всегда; отсюда вытекает, что всегда существует нужный нам набор.

Чтобы найти цикл, можно действовать согласно алгоритму, описанному выше: идти по ребрам, пока не окажемся в вершине, которую уже посетили. Это значит, что эта вершина на цикле. Из неё легко найти нужный нам цикл.

Задача C. Быстрая-пребыстрая сортировка

Идея: Николай Ведерников
Реализация: Андрей Комаров
Разбор: Андрей Комаров

Условие:
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

Вам, должно быть, известен алгоритм быстрой сортировки. Рассмотрим некоторую его вариацию, сортирующую массив без повторяющихся элементов.

function qqsort(A: array of int): array of int        if isSorted(A):            return A        middle = pick(A)        aLess = elements of A less then middle        aGreater = elements of A greater then middle        return qqsort(aLess) + [middle] + qqsort(aGreater) 

Для сортировки массива делается следующее: сначала проверяется, является ли он уже отсортированным. Если является, дальнейшие действия не требуются. В ином случае выбирается некоторый элемент массива, остальные разбиваются на те, которые меньше его и те, которые больше, после чего запускается сортировка для этих новых массивов. В новых массивах элементы оказываются в том же порядке, в котором они шли в исходном массиве.

Функция isSorted(a) проверяет, не отсортирован ли уже переданный ей аргументом массив. Функция pick возвращает некоторый элемент из массива, который ей передается в качестве аргумента. Она может вернуть любой из элементов массива.

Известно, что от того, насколько правильно выбран разделяющий элемент, существенно зависит быстродействие сортировки. Соответственно, в зависимости от возвращаемых функцией pick значений может меняться число действий, которые выполняются во время работы алгоритма. В качестве критерия минимизации будем использовать количество вызовов функции pick.

Задан массив из n различных целых чисел от 1 до n. Определите, какого минимального числа вызовов функции pick можно добиться при его сортировке, если при каждом вызове pick разрешается выбрать возвращаемое значение.

Например, если требуется отсортировать массив A = [1, 2, 6, 7, 5, 3, 4, 8, 9], то, если первый вызов функции pick вернет число 5, массив aLess будет равен [1, 2, 3, 4], а массив aGreater — [6, 7, 8, 9]. Соответственно, рекурсивные вызовы qqsort сразу выйдут, поскольку в них вызовы isSorted вернут true и массив будет отсортирован. Это оптимально, в этом случае функция pick вызывалась лишь 1 раз.

Формат входных данных
В первой строке задано количество тестов t. Далее в 2t строках заданы сами тесты. В первой строке описания теста задано положительное число n — размер массива. Во второй строке задан сам массив ai (1 ≤ ai ≤ n, если i ≠ j, то ai ≠ aj). Суммарный размер массивов во всех тестах не превышает 106.

Формат выходных данных
Для каждого теста выведите единственное число — минимальное число вызовов функции pick, которое может быть сделано при его сортировке с помощью функции qqsort.

Разбор:
В задаче была дана некоторая модификация алгоритма быстрой сортировки и требовалось для заданной перестановки найти наименьшее необходимое для её сортировки количество вызовов функции pick.

Обозначим за left(a, x) то, что в коде из условия называлось smaller — элементы массива a, строго меньшие x. Аналогично введём right(a, x) — элементы, бо́льшие x. Докажем несколько утверждений про left и right.

Если x ∈ a и a — множество идущих подряд натуральных чисел, то left(a, x) и right(a, x) — тоже множества идущих подряд чисел. Это верно, так как если a — множество целых чисел от L до R, то left(a, x) — множество целых чисел от L до x-1, а right(a, x) — множество целых чисел от x+1 до R.

Посмотрим на заданный массив a. Обозначим за w[i] позицию элемента i в a: w[a[i]] = i. Разобьём массив на цепочки увеличивающихся на 1 чисел так, чтобы элементы внутри одной цепочки в массиве шли подряд: добавим 1 в первую цепочку, далее, если w[1] < w[2], то добавим в неё 2, и т.д.

Например, chains([1, 2, 6, 7, 5, 3, 4, 8, 9]) = [ [1, 2, 3, 4], [5], [6, 7, 8, 9] ]. Посмотрим, что произойдёт с этими цепочками после разбиения по x. Разобьём на цепочки left(a, x) и right(a, x). Изучим left. right рассматривается аналогично. Рассмотрим взаимное расположение цепочки [c..d] ∈ chains(a) и x.

• x > d. В этом случае [c..d] ∈ chains(left(a, x))
• c < x. В этом случае [c..d] ∉ chains(left(a, x)). А также ни один элемент из [c..d] не представлен ни в одной цепочке из chains(left(a, x))
• x = d, x ≠ c. Здесь [c..d-1] ∈ chains(left(a, x))
• x = c, x ≠ d. Аналогично второму случаю, [c..d] ∉ chains(left(a, x))
• Наконец, последний случай: x = c = d. В этом случае ничто из цепочки [c..d] (которая, на самом деле, [c]) не попадает ни в chains(left(a, x)), ни в chains(right(a, x))

Посмотрев на эти случаи, можно заметить следующее: если два элемента когда-то были в одной цепочке, то они никогда не окажутся в разных цепочках одного сортируемого массива. Однако они могут оказаться в разных цепочках, но в рамках сортировки разных массивов. Например, a = [5, 2, 3, 4, 1], chains(a) = [ [1], [2, 3, 4], [5] ], x = 3, left(a, 3) = [2, 1], chains(left(a, 3)) = [ [1], [2] ], right(a, 3) = [5, 4],chains(right(a, 3)) = [ [4], [5] ]. Видно, что числа 2 и 4, бывшие сначала в одной цепочке [2, 3, 4], разошлись по разным, но при этом и сортируемые массивы разные ([2, 1] и [5, 4]).

Из этого можно сделать первое важное наблюдение: брать в качестве разделяющего элемент, не являющийся крайним в цепочке, не имеет смысла. Если взять вместо взятого из середины элемента какой-нибудь из крайних, ответ будет не хуже (так как элементы одной цепочки не могут стать элементами разных).

Опишем неформально то, чего хочется добиться. Имеем массив a. Построим по нему chains(a). В полученном наборе в качестве разделителя выгодно выбирать только концы цепочек. Для того чтобы получить отсортированный массив, необходимо устранить все зазоры между цепочками. Если изначально были цепочки [c..d] и [d+1..e], а в качестве разделяющего был выбран элемент d, то зазор (d..d+1) перестаёт нас волновать, так как все элементы левее него попали в один массив, а все, что правее — в другой. Таким образом устранился один зазор, а всего их надо устранить #chains(a) — 1, где # обозначает размер.

Пусть была не первая и не последняя цепочка длины 1: [c..d-1], [d], [d+1..e]. Возьмём d в качестве разделяющего элемента. Тогда, так как он крайний слева для цепочки [d], устранится зазор (d-1..d). Так как он же и крайний справа для этой же цепочки, устранится также и зазор (d..d+1). Таким образом, выбор единственного элемента некрайней цепочки в качестве разделяющего устранит сразу два зазора.

Пускай есть какой-то оптимальный ответ, и в нём фигурировали разделяющие элементы d1, d2, …, dk. Каждый из них устранял сколько-то зазоров. Сделаем следующее: выберем в качестве первого разделяющего элемента min {d1, …, dk}. Массив разобьётся на отсортированный левый и ещё не отсортированный правый куски. Выберем среди di второй минимум и сделаем его разделяющим элементом для правого куска. Будем повторять, пока di не кончатся. Несложно убедиться, что при такой стратегии выбора разделяющих элементов каждый устранит то же количество зазоров, что и во взятом ранее оптимальном выборе. Таким образом можно решать задачу с помощью динамического программирования, считая минимально необходимое число действий для того, чтобы объединить несколько первых цепочек в одну. Ответом будет минимальное число действий, необходимых для объединения всех цепочек в одну.

Задача D. Робот

Идея: Борис Минаев
Реализация: Борис Минаев
Разбор: Борис Минаев

Условие:
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

Боря участвует в соревновании по программированию роботов. В начальный момент времени робот расположен в левой верхней клетке прямоугольного поля размером n × m клеток. Цель робота — как можно быстрее попасть в правую нижнюю клетку. За один ход робот сначала перемещается из текущей в соседнюю с ней по стороне клетку поля.

Каждая клетка покрашена в один из двух цветов: черный или белый. Известно, что левая верхняя и правая нижняя клетки поля покрашены в черный цвет. После каждого хода робота, если он стоит на клетке белого цвета, происходит следующее: равновероятно случайно выбирается одна из белых клеток поля, и робот переставляется на нее. В частности, может быть выбрана та клетка, на которой и так стоит робот — в этом случае он остается на ней.

Боря хочет выиграть соревнование, для этого ему нужно разработать оптимальную стратегию для робота. Ему известна схема поля, где для каждой клетки отмечено, черная она или белая. Теперь он пытается выяснить математическое ожидание числа ходов, которое потребуется роботу для достижения финиша при использовании оптимальной стратегии. Боря хочет знать ответ абсолютно точно, поэтому он пытается получить его в виде несократимой дроби. Помогите ему выяснить искомое математическое ожидание.

Формат входных данных
Первая строка содержит целое число t — количество полей. Каждое поле описывается следующим образом. В первой строке записано два целых числа n и m — высота и ширина поля в клетках (1 ≤ n, m ≤ 103). В следующих n строках содержится по m символов. Если символ равен B, то соответствующая клетка черная, а если W, то белая.
Суммарное количество клеток во всех полях не превышает 106.

Формат выходных данных
Для каждого поля в отдельной строке выведите математическое ожидание числа ходов, необходимых, чтобы добраться из левой верхней клетки в правую нижнюю при оптимальной стратегии. Ответ необходимо вывести в виде несократимой дроби.

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

Разберемся подробнее, как устроена оптимальная стратегия выбора пути. Для каждой клетки поля можно посчитать матожидание количества ходов, необходимых для того, чтобы попасть в правую нижнюю клетку. При этом ответ будет соответствовать расстоянию, которое записано в левой верхней клетке. Как же вычислить эти значения? Рассмотрим конкретную клетку и все соседние с ней. Если соседняя клетка покрашена в черный цвет, то ответ для клетки будет как минимум (1 + значение, которое записано в соседней клетке). Если же у клетки есть белый сосед, то ответ для нее равен как минимум (1 + среднее арифметическое ответов для всех белых клеток).

Понятно, что если робот два раза попадает в одну и ту же клетку, то существует оптимальная стратегия, в которой следующий ход в обоих случаях одинаковый. Если это не так, то на каком-то из ходов робот поступил неправильно и пошел в клетку с большим матожиданием количества ходов до конца, а значит, стратегию можно улучшить. Есть два принципиально разных действия, которые может сделать робот, находясь в некоторой клетке. Он может пойти сразу в правый нижний угол по черным клеткам (если такой путь существует), а может пойти в некоторую белую клетку. Очевидно, что среди всех белых клеток в которые можно пойти следует выбрать ближайшую.

Посчитаем для каждой клетки расстояние до правой нижней по черным клеткам и расстояние до ближайшей белой. Заметим, что для любой белой клетки расстояние до ближайшей белой не больше двух. Теперь разобьем все белые клетки на два множества — те, из которых робот сразу должен идти в правую нижнюю клетку, и те, из которых робот должен идти в соседнюю белую. Когда такое разбиение произведено, ответ вычислить несложно. Записав рекуррентное соотношение для среднего ответа для всех белых клеток, найдем его. Это будет некоторая дробь со знаменателем не больше количества белых клеток. Теперь ответ это min(расстояние по черным клеткам до правой нижней, расстояние до ближайшей белой + средний ответ для всех белых).

Осталось научиться находить правильное разбиение белых клеток на множества. Отсортируем все белые клетки по критерию (расстояние до правой нижней по черным — расстояние до ближайшей белой). Утверждается, что оптимальное разбиение следующее — из всех клеток некоторого префикса отсортированного массива необходимо идти сразу в правую нижнюю клетку, а из остальных — в ближайшую белую. Этот факт несложно доказывается методом от противного (пусть оптимальное разбиение имеет другой вид; рассмотрим средний ответ для белых клеток, увидим, что некоторые клетки можно переместить из одного множества в другое, не ухудшив ответ, но приведя разбиение к нужному виду).

В итоге решение сводится к следующему. Посчитаем расстояния, которые обсуждались ранее, для всех клеток. Отсортируем белые клетки. Переберем разбиение на множества, каждый раз пересчитывая средний ответ для белых клеток за O(1). Ответ на задачу — минимум из расстояния по черным клеткам и расстояния до ближайшей белой клетки + средний ответ для белых клеток. Если сортировать белые клетки подсчетом, то общая сложность решения будет O(общее количество клеток).

Задача E. Вакцинация

Идея: Виталий Аксенов
Реализация: Борис Минаев
Разбор: Борис Минаев

Условие:
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

Министерство здравоохранения Байтландии провело масштабное исследование заболеваемости капибарным гриппом среди жителей страны. Учёные выяснили, что иммунитет человека против гриппа характеризуется целым неотрицательным числом. Каждый год 4 января в результате вспышки на Солнце иммунитет каждого человека уменьшается на k. При этом он не может стать отрицательным. Если исходный иммунитет был меньше k, то иммунитет становится равен 0.

В некоторые годы 2 января в Байтландии проводилась вакцинация всех жителей от гриппа. В результате вакцинации иммунитет каждого человека увеличивался на некоторую величину. В результате каждой вакцинации увеличение иммунитета одинаково для всех жителей, хотя, возможно, эта величина различна для разных вакцинаций.

Чтобы лучше изучить болезнь, ученые решили собрать больше статистики. Помогите им вычислить иммунитет некоторых людей в некоторые годы их жизни.

Про каждого человека известен год, в который он родился, год, в который необходимо узнать его иммунитет, а также его иммунитет при рождении. Будем считать, что все жители Байтландии родились 1 января соответствующего года, а узнать иммунитет требуется на 3 января.

Формат входных данных
Первая строка содержит целое число t — количество тестов.

Каждый тест задается следующим образом. В первой строке записано три целых числа n, m и k — количество вакцинаций, количество запросов и величина, на которую уменьшается иммунитет 4 января каждого года в результате солнечной вспышки (1 ≤ n, m ≤ 105, 1 ≤ k ≤ 109). Далее содержится описание вакцинаций: в следующих n строках содержится по два числа — год, в который была проведена вакцинация, а также величина, на которую при этом увеличился иммунитет каждого человека. Гарантируется, что годы приведены в строго возрастающем порядке.

В следующих m строках содержится запросы: по три целых числа, обозначающие год рождения человека, год, в который необходимо узнать его иммунитет, а также начальный иммунитет человека.

Все числа в тестах неотрицательные и не превышают 109. Гарантируется, что год, в который необходимо узнать иммунитет человека, не меньше чем год его рождения. Суммарное количество вакцинаций во всех тестах не превышает 200 000. Аналогично суммарное количество людей не превышает 200 000.

Формат выходных данных
Для каждого запроса в отдельной строке выведите иммунитет человека в соответствующий год.

Разбор:
В данной задаче были заданы правила, по которым изменяется некоторая величина. Необходимо было найти значения величины при разных начальных условиях. Сами изменения происходили следующим образом. Каждую единицу времени величина уменьшалась на некоторое число. Если величина становилась отрицательной, то она приравнивалась к нулю. В некоторые моменты времени к этой величине прибавляли какие-то значения.

Каждый запрос характеризовался тройкой чисел — начало и конец промежутка наблюдения, а также начальное значение величины. Рассмотрим функцию ответа на запрос, зависящую от третьего параметра. Утверждается, что она всегда имеет следующий вид: до некоторого значения ответ является константой, а если величина больше этого значения на x, то ответом будет эта константа + x. Это несложно доказать по индукции по количеству «добавлений», которые есть на отрезке. База индукции — на отрезке значения только уменьшаются каждую единицу времени на константу. Справедливость утверждения очевидна. Пусть мы рассмотрели первые k добавлений, а теперь добавляем еще одно, которое происходит позже уже имеющихся. Необходимо разобрать два случая — когда минимальное значение, с которым мы можем прийти к последнему «добавлению», равно нулю, и когда оно больше нуля. В обоих случаях конечная функция имеет такой же вид.

Зная факт, который описан выше, правильное решение придумать не сложно. Построим дерево отрезков на всех «добавлениях». В вершинах дерева будем хранить в каком-нибудь виде функцию ответа для промежутка. Чтобы соединить два промежутка, необходимо аккуратно рассмотреть два случая, о которых говорилось выше. Для обработки очередного запроса возьмем из дерева отрезков соответствующий промежуток, учтем, что концы промежутка могут не совпадать точно с концами запроса, вычислим значение функции. Общая сложность решения получается O(n + m•log(n)), где n — количество «добавлений», а m — количество запросов.

Задача F. Расписание перелетов

Идея: Виталий Аксенов
Реализация: Павел Кротков
Разбор: Павел Кротков

Условие:
Ограничение по времени: 4 секунды
Ограничение по памяти: 256 мегабайт

Новое расписание рейсов компании BytelandAvia преподнесло сюрприз всем путешественникам, исследующим достопримечательности Байтландии. Как утверждают представители этой компании, с новым расписанием рейсов любой турист сможет быстро и просто определить минимальное количество часов, которое он потратит на перелет из одного города в другой.

В Байтландии n городов, и авиакомпания обслуживает m регулярных рейсов, позволяющих добраться — возможно, с несколькими пересадками — из любого байтландского города в любой другой. Рейс номер i соединяет города с номерами ai и bi и выполняется ровно один раз в сутки, состоящие в Байтландии из p часов. Время полета i-го рейса составляет li часов, а вылетает он в тот момент, когда с начала очередных суток прошло si часов. При этом все рейсы являются двусторонними, то есть самолет из города ai в город bi и самолет из города bi в город ai вылетают и прилетают одновременно. Известно также, что самолеты летают строго по расписанию, что позволяет путешественнику, прилетевшему в город в некоторый момент времени, успеть на самолет, вылетающий из этого же города в тот же самый момент.

При этом расписание рейсов Байтландии удовлетворяет следующему условию. Рассмотрим неориентированный граф, где вершинами являются города; они соединены ребром, если между городами есть прямой рейс. Тогда в этом графе каждая вершина принадлежит не более чем одному простому циклу, такие графы называются вершинными кактусами.

Вам необходимо определить минимальное количество часов, которое уйдет у путешественника, пришедшего в начале очередных суток в аэропорт города x, на перелет в город y. Данную задачу требуется решить для нескольких различных путешественников.

Формат входных данных
Первая строка содержит количество тестов t. Далее следуют описания тестов.

В первой строке описания каждого теста даны целые числа n, m и p (1 ≤ n ≤ 104, 1 ≤ m, 1 ≤ p ≤ 109) — количество городов в стране, количество авиарейсов и продолжительность суток.

Следующие m строк содержат описания рейсов. Описание каждого рейса состоит из четырех целых чисел a, b, l и s (1 ≤ a, b ≤ n, a ≠ b, 1 ≤ l ≤ 109, 0 ≤ s < p) — города, соединенные этим рейсом, его продолжительность и время вылета. Гарантируется, что никакая пара городов не соединена двумя и более рейсами.

Следующая строка содержит одно целое число c (1 ≤ c ≤ 105) — количество путешественников, для которых необходимо найти минимальную продолжительность их пути. Следующие c строк содержат по два целых числа x и y (1 ≤ x, y ≤ n) — числа, необходимые для генерации номеров городов, которые интересуют очередного путешественника. Очередной путешественник собирается проехать из города (x + ans — 1) mod n + 1 в город ( y + ans — 1) mod n + 1, где ans — ответ для предыдущего путешественника в этом тесте, если он существует, или же 0 в обратном случае.

Гарантируется, что суммарное количество городов во всех тестах не превышает 104, а суммарное количество путешественников — 105.

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

Разбор:
Данная задача задумывалась как самая технически сложная задача финала. К сожалению, полное и подробное описание ее решения окажется очень громоздким, поэтому мы приведем основные идеи, ведущие к решению задачи, опустив детали конкретной реализации.

Заметим, что описанный в условии граф является вершинным кактусом, и это означает, что любая вершина в этом графе лежит не более чем на одном цикле. Научимся решать сначала более простой случай, в котором данный граф является деревом, после чего несколько усложним наш алгоритм и решим всю задачу.

Подвесим дерево за любую вершину. Рассмотрим все пути, идущие в этом дереве строго сверху вниз, число ребер в которых равно некоторой степени двойки. Для каждого такого пути посчитаем две величины:

• продолжительности пути из верхней вершины в нижнюю при условии, что на ожидание самолета в верхней вершине тратится 0 часов (пассажир прибыл ровно к вылету самолета)
• продолжительности пути из нижней вершины в верхнюю при условии, что на ожидание самолета в нижней вершине тратится 0 часов

Заметим, что при посчитанных величинах для путей из 2k ребер величины для путей длины 2k + 1 считаются за O(1) каждая, так как каждый путь из 2k + 1 ребер разбивается на два пути из 2k ребер каждый, длину которых в часах мы уже выяснили, а объединить их можно, использовав несложную формулу подсчета длительности ожидания в городе, стоящем посередине пути.

Любой путь между двумя вершинами в дереве можно разбить не более чем на два пути, идущих из наименьшего общего предка этих вершин в каждую из них, а каждый из этих путей, в свою очередь, разбивается на O(logn) путей, продолжительности которых в часах мы уже предпосчитали. Таким образом, мы научились обрабатывать запросы, поступающие в дерево.

Посмотрим теперь, как необходимо модифицировать решение, чтобы оно решало оригинальную задачу. Во-первых, заметим, что из-за подвешивания циклов понятие предка в дереве несколько стирается, вследствие чего стирается понятие пути, идущего снизу вверх. Решим эту проблему следующим образом: для любой вершины, находящейся на цикле, ее предком в дереве будет вершина, за которую соответствующий цикл подвешен. Предок же той вершины, за которую весь цикл подвешен, определяется из очевидных соображений.

Но теперь, как несложно заметить, величины, которые мы считали для дерева, несколько утратили свой смысл: из вершины, лежащей на цикле, в вершину, за которую цикл подвешен, существуют два возможных пути, и однозначно определить более выгодный путь заранее невозможно. Поэтому новый набор величин, которые мы считаем для нового дерева, можно сформулировать так:

• продолжительности пути из верхней вершины в нижнюю при условии, что на ожидание самолета в верхней вершине тратится 0 часов (пассажир прибыл ровно к вылету самолета) и в случае, если верхняя вершина лежит на цикле, цикл будет обходиться против часовой стрелки
• продолжительности пути из верхней вершины в нижнюю при условии, что на ожидание самолета в верхней вершине тратится 0 часов и в случае, если верхняя вершина лежит на цикле, цикл будет обходиться по часовой стрелке
• продолжительности пути из нижней вершины в верхнюю при условии, что на ожидание самолета в нижней вершине тратится 0 часов и в случае, если нижняя вершина лежит на цикле, цикл будет обходиться против часовой стрелки
• продолжительности пути из нижней вершины в верхнюю при условии, что на ожидание самолета в нижней вершине тратится 0 часов и в случае, если нижняя вершина лежит на цикле, цикл будет обходиться по часовой стрелке

Между делом заметим, что для путей, концы которых не лежат на циклах, некоторые величины будут совпадать.
Предпосчитав описанные выше значения, мы можем приступать к решению задачи. Заметим, что путь между двумя вершинами разбивается на два пути (возможно, пустых) снизу вверх и сверху вниз, между ними же, возможно, придется пройти по циклу, выбрав направление его обхода.
В качестве последнего уточнения заметим, что считать длину прохода по циклу от вершины к вершине в ту или иную сторону нам поможет точно такой же трюк — подсчет продолжительности прохода по путям, состоящим из числа ребер, равного некоторой степени двойки.

Все трое победителей RCC 2013 справились с первыми пятью задачами. Задача А оказалась, пожалуй, даже более крепким орешком, чем мы предполагали — с ней не справился ни один из 50 финалистов.

Для того чтобы выйти в финал, нужно было пройти одну из трех квалификаций (разборы задач с первой, второй и третьей уже публиковались на Хабре) и отборочный раунд.