Analysis QR2 RCC 2015

Задача A. Турникеты в метро.

Идея: Дмитрий Филиппов.
Реализация: Дмитрий Филиппов.
Разбор: Виталий Аксёнов.

По условию задачи нужно найти момент времени, когда числа, отображаемые на турникете у двух мальчиков, будут отличаться в k раз. В первую очередь разберём случай k=1, в этом случае ответ — YES, если на обоих турникетах показывается 99 или если a = b. Иначе, несложно заметить, что правильный момент времени наступит не раньше, чем у какого-то мальчика количество поездок станет меньше 99. Перейдём сразу к первому такого моменту. У нас осталось всего не более 99 вариантов подходящих дней. Переберём и проверим каждый из них на то, что он удовлетворяет условию задачи.

Задача В. Игра.

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

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

В dp[i][j] будет хранить математическое ожидание длины пути, если мы начнем на i-м этаже в j-ой комнате и пойдём до последнего уровня. Тогда ответ на нашу задачу будет хранится в dp[1][1].

Будет решать задачу с последнего уровня до первого. Понятно, что dp[n + 1][x] = 0, где x от 1 до n + 1. Теперь зная ответ для (k + 1)-го уровня, посчитаем значение динамики для k.

Если a[k][j][0] < a[k][j][1], тогда dp[k][j] = dp[k + 1][j] + a[k][j][0]. Где a[k][j][0] — длина коридора с k-го уровня j-ой комнаты в j-ую комната на (k + 1)-ом уровне. А a[k][j][1] — длина коридора с k-го уровня j-ой комнаты в (j + 1)-ую комната на (k + 1)-ом уровне.
Если a[k][j][0] > a[k][j][1], тогда dp[k][j] = dp[k + 1][j + 1] + a[k][j][1].
Если a[k][j][0] = a[k][j][1], тогда dp[k][j] = (dp[k + 1][j] + dp[k + 1][j + 1]) / 2 + a[k][j][0]. Так как мы могли равно вероятно пойти как по первому коридору, так и по второму с равной вероятностью.

После подсчёта ответ на задачу будет храниться в dp[1][1].

Задача С. Палочки и Шарниры.

Идея: Георгий Корнеев.
Реализация: Григорий Шовкопляс.
Разбор: Григорий Шовкопляс.

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

Рассмотрим решение с помощью двоичного поиска по ответу. Очевидно, что если цепочка помещается в окружность, то она поместится и в окружность большего радиуса.

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

Задача D. Числа Фибоначчи.

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

По условию задачи нужно найти сумму k-ых степеней первых n чисел Фибоначчи по модулю 10⁹+23. Самое первое действие заключалось в разложении модуля на множители: 10⁹+23 = 3·11²·61·45161. Давайте посчитаем нужную сумму по каждому из этих модулей и восстановим по Китайской Теореме об Остатках ответ на задачу.

Для каждого модуля по отдельности задача решается следующим образом. Найдём период чисел Фибоначчи. Для наших модулей они получаются небольшими, и предпериод всегда равен 0. Посчитаем сумму k-ых степеней чисел Фибоначчи на данном периоде и ещё небольшом кусочке. Тогда ответ на задачу при фиксированном n будет равен сумме нескольких периодов и сумма на маленьком кусочке.

Получив ответ для каждой из меньших задач, восстанавливаем ответ для начальной задачи.

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

Задача E. Телепорты.

Идея: Илья Збань.
Реализация: Илья Збань.
Разбор: Илья Збань.

В задаче дано n точек-телепортов, от которых можно отразиться, и требуется проверить, можно ли добраться из стартовой точки до конечной.

Заметим, что два отражения подряд относительно точек i, j прибавят к координате текущей точки вектор f(i, j) = (2(x_j — x_i), 2(y_j — y_i)). Если мы знаем, что в ответе четное число отражений, то задачу можно свести к следующей: можно ли представить вектор (x_f — x_s, y_f — y_s) суммой векторов f(i, j). Случай с нечетным числом векторов в ответе сводится к задаче с четным числом, если первым действием отразить стартовую точку относительно любого телепорта (может показаться, что нужно перебрать все n вариантов первого хода, но на самом деле это не обязательно) и попытаться решить задачу с четным числом векторов в ответе.

Заметим, что не нужно использовать все n² векторов f(i, j): f(i, j) = f(1, j) — f(1, i). Итак, у нас в рассмотрении остался всего n-1 вектор. Утверждается, что целочисленную линейную оболочку целочисленных векторов можно представить как целочисленную линейную оболочку всего двух некоторых векторов, т.е. эта оболочка — некоторая сетка на плоскости.

Будем добавлять в рассмотренное множество векторы по одному и поддерживать два вектора, задающие линейную комбинацию всех уже добавленных. Один вектор будет иметь вид v₁ = (x₁, 0), где x₁ — минимально возможное положительное, а второй — v₂ = (x₂, y₂), где y₂ — минимально возможное положительное, и 0 ≤ x₂ < x₁.

Пока все добавленные векторы коллинеарны, используя алгоритм Евклида легко находить, какой единственный вектор может представить своей линейной комбинацией все остальные. Как только в рассмотренном множестве появляется хотя бы одна пара неколлинеарных векторов, векторы пересчитываются иначе. Пусть добавлен был вектор v₃.

Чтобы найти новый вектор v₁, надо посмотреть на GCD двух векторов: старого v₁, и вектора с минимальным x вида (x, 0), представимого линейной комбинацией векторов v₂ и v₃. Для этого нужно найти минимальное решение уравнения k₂ · y₂ + k₃ · y₃ = 0.

Чтобы найти новый вектор v₂, надо рассмотреть вектор вида k₂ · v₂ + k₃ · v₃. Нужно найти любое решение уравнения k₂ · y₂ + k₃ · y₃ = GCD(y₂, y₃), и прибавить несколько раз новый v₁, чтобы гарантировать минимальность по х-координате.

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