Разбор задач 2-го квалификационного раунда Russian Code Cup 2015
В субботу 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 лучших участников из каждого квалификационного раунда.
Все желающие участвовать в чемпионате еще могут успеть зарегистрироваться на сайте до начала третьего квалификационного раунда.
Идея: Дмитрий ФилипповРеализация: Дмитрий ФилипповРазбор: Виталий АксёновПо условию задачи, нужно найти момент времени, когда числа, отображаемые на турникете у двух мальчиков, будут отличаться в 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 градусов, и она вышла за пределы окружности), значит, уместить цепочку в эту окружность нельзя, иначе — на окружности найдется точка, на которую можно положить следующий шарнир, а значит, эта палочка поместится. Теперь проверяем, что длина оставшихся палочек меньше диаметра окружности, что равносильно тому, что мы можем разложить все оставшиеся шарниры на окружность, и цепочка поместится в окружность.
Идея: Илья ЗбаньРеализация: Виталий АксёновРазбор: Виталий АксёновПо условию задачи, нужно найти сумму k-ых степеней первых n чисел Фибоначчи по модулю 109+23. Самое первое действие заключалось в разложении модуля на множители: 109+23 = 3·112·61·45161. Давайте посчитаем нужную сумму по каждому из этих модулей и восстановим ответ на задачу по Китайской теореме об остатках.
Для каждого модуля по отдельности задача решается следующим образом. Найдём период чисел Фибоначчи. Для наших модулей они получаются небольшими, и предпериод всегда равен 0. Посчитаем сумму k-ых степеней чисел Фибоначчи на данном периоде и ещё небольшом кусочке. Тогда ответ на задачу при фиксированном n будет равен сумме нескольких периодов и сумме на маленьком кусочке.
Получив ответ для каждой из меньших задач, восстанавливаем ответ для начальной задачи. К сожалению, на данном этапе задача не заканчивалась. Нужно придумать любую оптимизацию для того, чтобы программа прошла по времени. Можно было применить следующие: избавиться от двойного взятия по модулю при быстром возведении в степень, предварительно предподсчитав числа в степенях степени двойки, либо возводить не в степень k, а воспользоваться теоремой Эйлера и возводить в степень по модулю φ.
Идея: Илья ЗбаньРеализация: Илья ЗбаньРазбор: Илья ЗбаньВ задаче дано n точек-телепортов, от которых можно отразиться, и требуется проверить, можно ли добраться из стартовой точки до конечной. Заметим, что два отражения подряд относительно точек i, j прибавят к координате текущей точки вектор f (i, j) = (2(xj — xi), 2(yj — yi)). Если мы знаем, что в ответе четное число отражений, то задачу можно свести к следующей: можно ли представить вектор (xf — xs, yf — ys) суммой векторов f (i, j). Случай с нечетным числом векторов в ответе сводится к задаче с четным числом, если первым действием отразить стартовую точку относительно любого телепорта (может показаться, что нужно перебрать все n вариантов первого хода, но на самом деле это необязательно) и попытаться решить задачу с четным числом векторов в ответе.
Заметим, что не нужно использовать все n2 векторов f (i, j): f (i, j) = f (1, j) — f (1, i). Итак, у нас в рассмотрении остался всего n-1 вектор. Утверждается, что целочисленную линейную оболочку целочисленных векторов можно представить как целочисленную линейную оболочку всего двух некоторых векторов, т.е. эта оболочка — некоторая сетка на плоскости.
Будем добавлять в рассмотренное множество векторы по одному и поддерживать два вектора, задающих линейную комбинацию всех уже добавленных. Один вектор будет иметь вид v1 = (x1, 0), где x1 — минимально возможное положительное, а второй — v2 = (x2, y2), где y2 — минимально возможное положительное, и 0 ≤ x2 < x1.
Пока все добавленные векторы коллинеарны, используя алгоритм Евклида, легко находить, какой единственный вектор может представить своей линейной комбинацией все остальные. Как только в рассмотренном множестве появляется хотя бы одна пара неколлинеарных векторов, векторы пересчитываются иначе. Пусть добавлен был вектор v3.
Чтобы найти новый вектор v1, надо посмотреть на GCD двух векторов: старого v1 и вектора с минимальным x вида (x, 0), представимого линейной комбинацией векторов v2 и v3. Для этого нужно найти минимальное решение уравнения k2 · y2 + k3 · y3 = 0. Чтобы найти новый вектор v2, надо рассмотреть вектор вида k2 · v2 + k3 · v3. Нужно найти любое решение уравнения k2 · y2 + k3 · y3 = GCD (y2, y3) и прибавить несколько раз новый v1, чтобы гарантировать минимальность по х-координате. Зная два вектора, задающих сетку, легко проверить, что данный вектор представим в виде их целочисленной линейной комбинации: нужно всего лишь проверить, что его коэффициенты разложения по этим двум векторам являются целыми числами.
