Всем привет!

Мы рады представить вашему вниманию разбор задач первого квалификационного раунда Russian Code Cup и заодно напомнить, что тем, кто не смог пройти квалификацию с первого раза, стоит принять участие во втором квалификационном раунде, который состоится 25 апреля в 12-00 по московскому времени.

Задача A. Магические карточки.

Идея: Виталий Аксёнов.
Реализация: Григорий Шовкопляс.
Разбор: Григорий Шовкопляс.

В задаче требуется проверить, верно ли, что Гриша в любом случае выиграет раунд, независимо от выбранных карточек.

Рассмотрим случай, когда у Гриши будут выбраны l минимальных карточек, а у Димы l максимальных. Очевидно, что если в этом случае Гриша выиграет, то он выиграет в любом другом, так как если заменить среди выбранных любую карточку на другую из набора данного игрока, то сумма у Димы не увеличится, а у Гриши не уменьшится.

Таким образом, чтобы решить задачу, нужно просто отсортировать карточки Гриши по возрастанию, а Димы по убыванию. После чего найти суммы первых l чисел в обоих наборах и сравнить их. Если сумма Гриши больше, то он выиграет любой раунд, иначе – нет.

Задача B. Домашнее задание.

Идея: Виталий Аксенов.
Реализация:.Дмитрий Филиппов
Разбор: Дмитрий Филиппов.

В задаче дано три числа x, y, z, записанных в десятичной системе счисления, надо проверить, верно ли, что x_k · y_k = z_k выполнено для бесконечного количества чисел k (через x_k обозначено значение числа x, если считать, что оно записано в k-ичной системе счисления).

Предположим, что таких k существует бесконечно много. Тогда равенство должно быть выполнено для сколь угодно больших k. Возьмем такую систему счисления, в которой при перемножении чисел x и y не будет переноса ни в одном разряде. Если в каком-либо разряде получилось число, больше либо равное 10, то равенство не будет выполнено для данного k, а также для всех систем счисления с большим основанием, так как в них переноса тоже не будет. Значит, чтобы равенство было верно для бесконечного количества чисел k, как минимум, при перемножении без переноса не должно быть разрядов с числами больше 9. Если это выполнено, остается только проверить, что получившееся произведение совпадает с числом z, и если да, то ответ на задачу — «Infinity», иначе — «Finite».

Задача C. Конгресс юных любителей.

Идея: Виталий Аксёнов.
Реализация: Виталий Аксёнов.
Разбор: Виталий Аксёнов.

Данная задача является задачей динамического программирования. Давайте посчитаем следующий массив: d[сколько мест с начала рассадили][какое количество из них философы][количество пар философ-математик сидящие вместе][типы людей на двух последних обработанных местах] — количество способов рассадить математиков и философов, опираясь только на их типы и условия задачи. Данный массив пересчитывается последовательно при добавлении нового места. То есть добавляем нового человека, перебираем какое количество философов сидит до него, перебираем его тип, проверяем, что условия про окружение и тип места выполняются (для этого мы и храним типы людей на двух предыдущих местах), возможно у нас появляется пара философ-математик, сидящие на соседних местах.

Пока мы не использовали, что люди из разных стран. Заметим, что если мы зафиксировали назначение типов, нам для подсчёта по странам нужно только знать, что в позициях философ-математик сидят люди не из одной страны. Также нужно отметить, что количество назначений стран зависит только от количества таких пар в назначении типов. Несложно по массиву d получить массив c, который по количеству пар возвращает количество соответствующих назначений типов.

Пусть p_n,k — количество перестановок из n элементов, таких что нет неподвижных точек среди первых k позиций. Тогда несложно убедиться, что ответ будет равен n! Σ_{i = 1}ⁿ p_n,i · c_i.

Осталось посчитать p. Воспользуемся идеей для подсчёта перестановок без неподвижных точек, например описанной на wikipedia, и получим реккурентное выражение p_n,k = (n-1) p_n-1,k-1 + (k-1) p_n-2,k-2, а p_n,0 = n! и p_n,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. Занимательная криптография.

Идея: Виталий Аксёнов.
Реализация: Илья Збань.
Разбор: Илья Збань.

В задаче нужно посчитать число строк, которые имеют данный хеш.

Наивное решение использует идею динамического программирования dp_i,j — количество строк длины i, имеющих хеш j. Переходы можно делать за Σ, и решение получается за n·m·Σ.

Это решение можно ускорить до m² · log n, если использовать технику двоичных подъемов: dp_i,j  – число строк длины 2ⁱ, имеющих хеш j. dp_i,j = Σ(x=0..m-1) dp_{i-1,x·p^2i-1 % m} · dp_i-1,j-x. Используя значения этой динамики, можно посмотреть разложение n по степеням двойки, и получить ответ на задачу.

Последнее ускорение заключается в том, что в формуле перехода предыдущей динамики можно увидеть не что иное, как произведение двух многочленов. Если использовать для этого быстрое преобразование Фурье, получаем асимптотику m · log m · log n. Это и будет полным решением.