company_banner

Разбор задач 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 лучших участников из каждого квалификационного раунда.

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

    Задача 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 чисел Фибоначчи по модулю 109+23. Самое первое действие заключалось в разложении модуля на множители: 109+23 = 3·112·61·45161. Давайте посчитаем нужную сумму по каждому из этих модулей и восстановим ответ на задачу по Китайской теореме об остатках.

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

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

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


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

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

    Mail.Ru Group

    1017,00

    Строим Интернет

    Поделиться публикацией
    Комментарии 11
      +1
      А можно подробностей по задаче про палочки и шарниры? Видимо, я какой-то момент в условии упускаю. Ведь сказано, что «ребра ломаной могут пересекаться и накладываться».

      Зачем вообще рассматривать тогда суммарные длины и почему не взять max(2l0, li)? Где l0 — первая палочка, li — все остальные.
        0
        1 3
        ответ 4
          0
          Не 4, а 2. Но почему нельзя взять max(a0,ak/2,(-a0-a1-...-ak-1+ak)) (максимум считается по всем k > 0)? Где сломается эта формула?
            0
            А, вот в первом комментарии в этой ветке дан показательный пример. Понял свою ошибку, спасибо.

            Последний элемент в формуле немного не понял. При ребрах 1, 3, 10, 1 что там получится? Я -13 насчитываю.
              +1
              Ну и что, что -13. Тоже число, но оно максимумом быть не может. Там перебираются все k от 1 до n:
              max(1,3/2,10/2,1/2,2,6,-13)=6
                0
                Похоже на правду. На сайте RCC доступны используемые для проверки решений тесты. Можно через них прогонять.

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

                Хотя проблем со скоростью разработки топовые участники не испытывают ни на чем. Пока ты читаешь условие одной задачи, они успевают решить две-три.
                  0
                  вот тут можно даже онлайн проверить: codeforces.ru/gym/100673

                  а вообще последнее решение похоже на правду
                    0
                    Действительно, все прекрасно с этим решением.
                    image
          +1
          Не понял задачи совершенно аналогичным способом. Кстати max(2l0, li) / 2, мы радиус ищем
            0
            Чтобы ответ был Li/2, нужно, чтобы самая длинная палочка Li начиналась с точки на окружности (только тогда она сможет пройти по диаметру). Но если L0+L1+...+L{i-1}<Li/2, то начало Li неизбежно будет где-то внутри окружности, и её второй конец будет не ближе, чем Li-(L0+L1+...+L{i-1}) от центра.
          +1
          А мне вот интересно, как связаны спортивное программирование и методы post/get на PHP? :)

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое