В субботу 25 апреля прошел второй квалификационный раунд Russian Code Cup 2015. 3516 программистов решали задачи в течение двух часов, из них хотя бы одно правильное решение прислали 458 участников.

Первым за 4 минуты и 9 секунд решил задачу A (Турникеты в метро) Машарабов Александр (map). Задачу B (Игра) за 8:48 решил Дубленных Денис (Stigius), задачу C (Палочки и шарниры) за 18:08 решил Нигматуллин Нияз (niyaz.nigmatullin). Задачу D (Числа Фибоначчи) за 1 час 5 минут и 21 секунду решил Лунев Антон (Anton_Lunyov). А последнюю задачу E (Телепорты) за 1 час 44 минуты и 55 секунд решил Кунявский Павел (PavelKunyavskiy), который занял 1 место в рейтинге по итогам раунда. Последняя успешная попытка совершена Альбертом Саакяном за 4 секунды до конца соревнования. Все пять задач сдал только Павел Куявский.

Всего участники отправили на проверку 4287 решений, на С++ их было 3145, на Java — 613. Отметим, что из 2166 решений, сданных на GNU C++, 1218 решений использует С++ 11 стандарта, а остальные все еще не применяют новые возможности языка. Правильных решений на этот раз всего 913, из них на С++ — 726, на Java — 141.

По итогам раунда было квалифицировано 200 участников, которые сразятся за звание финалиста в отборочном туре 14 июня. Те, кому в субботу не улыбнулась удача и кто по тем или иным причинам не смогли принять участие в раунде, смогут попробовать свои силы в третьем квалификационном раунде 31 мая в 13:00. В отборочный тур, назначенный на 13:00 14 июня, пройдут 200 лучших участников из каждого квалификационного раунда.

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

Задача 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₁, чтобы гарантировать минимальность по х-координате. Зная два вектора, задающих сетку, легко проверить, что данный вектор представим в виде их целочисленной линейной комбинации: нужно всего лишь проверить, что его коэффициенты разложения по этим двум векторам являются целыми числами.