- PVSM.RU - https://www.pvsm.ru -
В субботу 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, нужно зарегистрироваться на сайте [1] (регистрация будет открыта до начала третьего квалификационного раунда).
Для участников чемпионатов и интересующихся доступна наша группа ВКонтакте [2], где вы сможете найти информацию о создании искусственного интеллекта, web-дизайне, спортивном программировании, разработке интерфейсов, маркетинге и создании IT-проектов. Материалы группы включают мнения экспертов отрасли, полезную литературу, мастер-классы, обучающие видео, лучшие тематические конференции, а также все самые интересные события IT-сферы. Подписчики группы первыми узнают все важные новости о соревнованиях Mail.Ru Group и других российских и международных IT-чемпионатах.
А теперь разберем задачи первого квалификационного раунда.
Задача A. Магические карточки [3]
Идея: Виталий Аксёнов
Реализация: Григорий Шовкопляс
Разбор: Григорий Шовкопляс
В задаче требуется проверить, верно ли, что Гриша в любом случае выиграет раунд, независимо от выбранных карточек. Рассмотрим случай, когда у Гриши будут выбраны l минимальных карточек, а у Димы l максимальных. Очевидно, что если в этом случае Гриша выиграет, то он выиграет в любом другом, так как если заменить среди выбранных любую карточку на другую из набора данного игрока, то сумма у Димы не увеличится, а у Гриши не уменьшится. Таким образом, чтобы решить задачу, нужно просто отсортировать карточки Гриши по возрастанию, а Димы по убыванию. После чего найти суммы первых l чисел в обоих наборах и сравнить их. Если сумма Гриши больше, то он выиграет любой раунд, иначе — нет.
Задача B. Домашнее задание [4]
Идея: Виталий Аксенов
Реализация: Дмитрий Филиппов
Разбор: Дмитрий Филиппов
В задаче дано три числа x, y, z, записанных в десятичной системе счисления. Надо проверить, верно ли, что xk · yk = zk выполнено для бесконечного количества чисел k (через xk обозначено значение числа x, если считать, что оно записано в k-ичной системе счисления). Предположим, что таких k существует бесконечно много. Тогда равенство должно быть выполнено для сколь угодно больших k. Возьмем такую систему счисления, в которой при перемножении чисел x и y не будет переноса ни в одном разряде. Если в каком-либо разряде получилось число, больше либо равное 10, то равенство не будет выполнено для данного k, а также для всех систем счисления с большим основанием, так как в них переноса тоже не будет. Значит, чтобы равенство было верно для бесконечного количества чисел k, как минимум, при перемножении без переноса не должно быть разрядов с числами больше 9. Если это выполнено, то остается только проверить, что получившееся произведение совпадает с числом z, и если да, то ответ на задачу — «Infinity», иначе — «Finite».
Задача C. Конгресс юных любителей [5]
Идея: Виталий Аксёнов
Реализация: Виталий Аксёнов
Разбор: Виталий Аксёнов
Данная задача является задачей динамического программирования. Давайте посчитаем следующий массив: d[сколько мест с начала рассадили][какое количество из них философы][количество пар философ-математик, сидящих вместе][типы людей на двух последних обработанных местах] — количество способов рассадить математиков и философов, опираясь только на их типы и условия задачи. Данный массив пересчитывается последовательно при добавлении нового места. То есть добавляем нового человека, перебираем, какое количество философов сидит до него, перебираем его тип, проверяем, что условия про окружение и тип места выполняются (для этого мы и храним типы людей на двух предыдущих местах), возможно, у нас появляется пара философ-математик, сидящие на соседних местах.
Пока мы не использовали, что люди из разных стран. Заметим, что если мы зафиксировали назначение типов, нам для подсчёта по странам нужно только знать, что в позициях философ-математик сидят люди не из одной страны. Также нужно отметить, что количество назначений стран зависит только от количества таких пар в назначении типов. Несложно по массиву d получить массив c, который по количеству пар возвращает количество соответствующих назначений типов.
Пусть pn,k — количество перестановок из n элементов, таких, что нет неподвижных точек среди первых k позиций. Тогда несложно убедиться, что ответ будет равен n! Σi = 1npn,i · ci. Осталось посчитать p. Воспользуемся идеей для подсчёта перестановок без неподвижных точек, например, описанной на wikipedia [6], и получим реккурентное выражение pn,k =(n-1) pn-1,k-1 + (k-1) pn-2,k-2, а pn,0 = n! и pn,1 = n! — (n — 1)!..
Задача D. Расшифровка [7]
Идея: Дмитрий Филлипов
Реализация: Николай Ведерников
Разбор: Николай Ведерников
Для начала научимся решать задачу без модификаций. Для этого воспользуемся идеей динамического программирования. В 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 позиции. Как построить такое дерево?
Ответ на всем отрезке будет лежать в корне дерева отрезков. Таким образом, когда мы модифицируем одну цифру, мы обновляем значение в листе, а затем обновляем значения, поднимаясь вверх. Так как глубина дерева отрезков есть O(log (n)), где n — длина строки, то итоговое время работы O(m log (n)), где m — общее число запросов.
Задача E. Занимательная криптография [8]
Идея: Виталий Аксёнов
Реализация: Илья Збань
Разбор: Илья Збань
В задаче нужно посчитать число строк, которые имеют данный хеш. Наивное решение использует идею динамического программирования 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. Это и будет полным решением.
Автор: Andrey_Kravchenko
Источник [9]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/87487
Ссылки в тексте:
[1] сайте: http://russiancodecup.ru/
[2] группа ВКонтакте: https://vk.com/cupmrg
[3] Магические карточки: http://www.russiancodecup.ru/championship/round/35/problem/A/
[4] Домашнее задание: http://www.russiancodecup.ru/championship/round/35/problem/B/
[5] Конгресс юных любителей: http://www.russiancodecup.ru/championship/round/35/problem/C/
[6] wikipedia: https://ru.wikipedia.org/wiki/%C1%E5%F1%EF%EE%F0%FF%E4%EE%EA_%28%EF%E5%F0%E5%F1%F2%E0%ED%EE%E2%EA%E0%29
[7] Расшифровка: http://www.russiancodecup.ru/championship/round/35/problem/D/
[8] Занимательная криптография: http://www.russiancodecup.ru/championship/round/35/problem/E/
[9] Источник: http://habrahabr.ru/post/254363/
Нажмите здесь для печати.