Разбор задач первого квалификационного раунда Russian Code Cup 2015
В субботу 28 марта прошел первый квалификационный раунд Russian Code Cup 2015. 3093 программиста решали задачи в течение двух часов, из них хотя бы одно правильное решение прислали 1012 участников. Верное решение для всех пяти задач сдали двое: Геннадий Короткевич и Петр Митричев. Всего участники отправили на проверку 4069 решений, 2517 на С++, 705 на Java, 425 на Python, 318 на C#. Правильных решений — 1745, из них на С++ прислано 1099, на Java — 339.
Первым за рекордные 2 минуты и 2 секунды решил задачу A (Магические карточки) победитель RCC 2014 года — Геннадий Короткевич (tourist). Он же первым решил задачи B (Домашнее задание) за 6:50 и C (Конгресс юных любителей) за 25:43. Задачу D (Расшифровка) за 51 минуту и 42 секунды решил победитель RCC 2013 года Петр Митричев (Petr). А последнюю задачу E (Занимательная криптография) за 1 час 2 минуты и 52 секунды решил участник из Японии (anta). Последняя успешная попытка совершена Михаилом Тихомировым за 6 секунд до конца соревнования. Самая простая задача A, самая сложная задача — E, задачу E сдало всего 13 человек.По итогам раунда было квалифицировано 202 участника, которые сразятся за звание финалиста в отборочном туре 14 июня. Те, кому в субботу не улыбнулась удача и кто по тем или иным причинам не смогли принять участие в раунде, смогут попробовать свои силы во втором отборочном туре 25 апреля в 12:00, а при необходимости и в третьем — 31 мая в 13:00. В отборочный тур, назначенный на 13:00 14 июня, пройдут 200 лучших участников из каждого квалификационного раунда. Для того чтобы принять участие в Russian Code Cup, нужно зарегистрироваться на сайте (регистрация будет открыта до начала третьего квалификационного раунда).
Для участников чемпионатов и интересующихся доступна наша группа ВКонтакте, где вы сможете найти информацию о создании искусственного интеллекта, web-дизайне, спортивном программировании, разработке интерфейсов, маркетинге и создании IT-проектов. Материалы группы включают мнения экспертов отрасли, полезную литературу, мастер-классы, обучающие видео, лучшие тематические конференции, а также все самые интересные события IT-сферы. Подписчики группы первыми узнают все важные новости о соревнованиях Mail.Ru Group и других российских и международных IT-чемпионатах.
А теперь разберем задачи первого квалификационного раунда.
Задача A. Магические карточки
Идея: Виталий АксёновРеализация: Григорий ШовкоплясРазбор: Григорий Шовкопляс
В задаче требуется проверить, верно ли, что Гриша в любом случае выиграет раунд, независимо от выбранных карточек. Рассмотрим случай, когда у Гриши будут выбраны l минимальных карточек, а у Димы l максимальных. Очевидно, что если в этом случае Гриша выиграет, то он выиграет в любом другом, так как если заменить среди выбранных любую карточку на другую из набора данного игрока, то сумма у Димы не увеличится, а у Гриши не уменьшится. Таким образом, чтобы решить задачу, нужно просто отсортировать карточки Гриши по возрастанию, а Димы по убыванию. После чего найти суммы первых l чисел в обоих наборах и сравнить их. Если сумма Гриши больше, то он выиграет любой раунд, иначе — нет.
Задача B. Домашнее задание
Идея: Виталий АксеновРеализация: Дмитрий ФилипповРазбор: Дмитрий Филиппов
В задаче дано три числа x, y, z, записанных в десятичной системе счисления. Надо проверить, верно ли, что xk · yk = zk выполнено для бесконечного количества чисел k (через xk обозначено значение числа x, если считать, что оно записано в k-ичной системе счисления). Предположим, что таких k существует бесконечно много. Тогда равенство должно быть выполнено для сколь угодно больших k. Возьмем такую систему счисления, в которой при перемножении чисел x и y не будет переноса ни в одном разряде. Если в каком-либо разряде получилось число, больше либо равное 10, то равенство не будет выполнено для данного k, а также для всех систем счисления с большим основанием, так как в них переноса тоже не будет. Значит, чтобы равенство было верно для бесконечного количества чисел k, как минимум, при перемножении без переноса не должно быть разрядов с числами больше 9. Если это выполнено, то остается только проверить, что получившееся произведение совпадает с числом z, и если да, то ответ на задачу — «Infinity», иначе — «Finite».
Задача C. Конгресс юных любителей
Идея: Виталий АксёновРеализация: Виталий АксёновРазбор: Виталий Аксёнов
Данная задача является задачей динамического программирования. Давайте посчитаем следующий массив: d[сколько мест с начала рассадили][какое количество из них философы][количество пар философ-математик, сидящих вместе][типы людей на двух последних обработанных местах] — количество способов рассадить математиков и философов, опираясь только на их типы и условия задачи. Данный массив пересчитывается последовательно при добавлении нового места. То есть добавляем нового человека, перебираем, какое количество философов сидит до него, перебираем его тип, проверяем, что условия про окружение и тип места выполняются (для этого мы и храним типы людей на двух предыдущих местах), возможно, у нас появляется пара философ-математик, сидящие на соседних местах.
Пока мы не использовали, что люди из разных стран. Заметим, что если мы зафиксировали назначение типов, нам для подсчёта по странам нужно только знать, что в позициях философ-математик сидят люди не из одной страны. Также нужно отметить, что количество назначений стран зависит только от количества таких пар в назначении типов. Несложно по массиву d получить массив c, который по количеству пар возвращает количество соответствующих назначений типов.
Пусть pn, k — количество перестановок из n элементов, таких, что нет неподвижных точек среди первых k позиций. Тогда несложно убедиться, что ответ будет равен n! Σi = 1npn, i · ci. Осталось посчитать p. Воспользуемся идеей для подсчёта перестановок без неподвижных точек, например, описанной на wikipedia, и получим реккурентное выражение pn, k =(n-1) pn-1, k-1 + (k-1) pn-2, k-2, а pn,0 = n! и pn,1 = n! — (n — 1)!…
Задача D. Расшифровка
Идея: Дмитрий ФиллиповРеализация: Николай ВедерниковРазбор: Николай Ведерников
Для начала научимся решать задачу без модификаций. Для этого воспользуемся идеей динамического программирования. В dp[i] будет храниться количество способов получить префикс длины i. Тогда переберем следующую исходную цифру x, если зашифрованная цифра соответствует строке с позиции i+1, тогда увеличиваем значение dp[i+ len (x)] на dp[i], где len (x) — длина зашифрованной цифры x.
Теперь будем решать задачу с изменениями. Заметим, что при заданных ограничениях на коэффициенты трехчлена одна цифра может превратиться в число, состоящее не более чем из трех цифр. Тогда для решения данной задачи воспользуемся деревом отрезков. В вершине, которая отвечает за отрезок от l до r, будем хранить 9 значений количества способов получить подстроку c l + 0…2 позиции дo r − 0…2 позиции. Как построить такое дерево?
Если отрезок с l по r небольшой, то посчитаем значения с помощью динамического программирования. Если отрезок большой, то разобьем его на два и посчитаем соответствующие значения для них рекурсивно. Теперь осталось научиться считать значение в узле, если мы знаем значения в детях. Во-первых, когда правый и левый подотрезок соприкасаются, то это значение на их объединении равно произведению значений на них. Если же между ними есть расстояние (то есть от правого подотрезка берется значение без одного или двух символов слева, а от левого подотрезка берем значение без одного или двух символов справа), то ответ будет равен количеству способов получить одно число между ними умножить на значение на правом подотрезке и на значение на левом подотрезке. Ответ на всем отрезке будет лежать в корне дерева отрезков. Таким образом, когда мы модифицируем одну цифру, мы обновляем значение в листе, а затем обновляем значения, поднимаясь вверх. Так как глубина дерева отрезков есть O (log (n)), где n — длина строки, то итоговое время работы O (m log (n)), где m — общее число запросов.Задача E. Занимательная криптография
Идея: Виталий АксёновРеализация: Илья ЗбаньРазбор: Илья Збань
В задаче нужно посчитать число строк, которые имеют данный хеш. Наивное решение использует идею динамического программирования dpi, j — количество строк длины i, имеющих хеш j. Переходы можно делать за Σ, и решение получается за n·m·Σ. Это решение можно ускорить до m2 · log n, если использовать технику двоичных подъемов: dpi, j — число строк длины 2i, имеющих хеш j. dpi, j = Σ (x=0…m-1) dpi-1, x·p2i-1% m · dpi-1, j-x. Используя значения этой динамики, можно посмотреть разложение n по степеням двойки, и получить ответ на задачу. Последнее ускорение заключается в том, что в формуле перехода предыдущей динамики можно увидеть не что иное, как произведение двух многочленов. Если использовать для этого быстрое преобразование Фурье, получаем асимптотику m · log m · log n. Это и будет полным решением.
