Разбор задач тренировочного warmup-раунда Russian Code Cup 2015
В воскресенье прошел тренировочный warmup-раунд Russian Code Cup. Первое место занял Михаил «mmaxio» Майоров из Перми. Второе — Игорь «kraskevich» Краскевич из Москвы. Третье — Валентин «ValenKof» Кофман из Москвы. Поздравляем победителей!
Впереди квалификационные раунды чемпионата. Напоминаем, что первый квалификационный раунд состоится 28 марта в 18:00 мск, а регистрация на чемпионат проходит на сайте http://www.russiancodecup.ru/ до начала третьего квалификационного раунда.
Russian Code Cup — это возможность для русскоязычных программистов со всего мира проверить свои силы и продемонстрировать мастерство, решая оригинальные задачи различной сложности, а также заявить о себе экспертному IT-сообществу. Олимпиада проходит в три этапа: квалификационные раунды, отборочный тур и финал, — на каждом из которых участникам олимпиады предлагается от четырех до восьми разноплановых задач. Задания и техническую часть соревнования обеспечивают специалисты Mail.Ru Group и эксперты Университета ИТМО — соорганизатора Russian Code Cup.
А сейчас разберемся с решением задач warmup-раунда.
Задача A. Воздушные шарикиНайдем количество различных чисел в массиве. Если оно больше либо равно k, то мы можно набрать k различных цветов в ответе. Если оно меньше, чем k, то возьмем по одному шару каждого цвета, а недостающие шары возьмем произвольным образом. Найти все различные числа в массиве можно сортировкой.
Задача B. Контрольная закупка
В задаче нужно было промоделировать описанный в условии процесс. Продублируем коробки: скажем, у нас есть не одна коробка с двумя способами оплаты, а две с разными стоимостями, из которых можно купить только одну. Отсортируем по времени события: поступления денег и коробки. Причем, если время у ближайшего поступления и у коробки одинаковые, отдаем предпочтение поступлению. Для каждого события поступления денег просто прибавляем к текущей сумме поступившую сумму. Для каждого события появления коробки, которую мы еще не купили, проверяем, хватает ли денег, и если да, то покупаем коробку.
Задача C. Торжественный парад
Если k > n2 или количество простых до 107 меньше, чем k, то решения нет, в остальных случаях решение существует.
Воспользуемся фактом, что количество делителей у числа n= p1s1 × p2s2 ×… × pksk равно (s1+1) × (s2+1) ×… × (sk+1).
Сгенерируем такую матрицу, чтобы в каждой строке и каждом столбце наборы степеней простых чисел были равны, то есть чтобы числа в них имели вид p1s1 × p2s2 ×… × pksk где pi — какие-то простые числа, возможно, разные для каждой строки и столбца, а si — фиксированные для всех строк и столбцов числа.
Если k > n, то n2 — (k — n) ячеек матрицы заполним следующим образом: i-ю строку матрицы заполним i-м циклическим сдвигом первых n простых чисел, а остальные k — n ячеек матрицы заполним остальными k — n простыми числами. Таким образом, в каждой строке и каждом столбце будут стоять ровно n различных простых чисел, и количество делителей для них будет одинаковым.
Если же k ≤ n, то в a[i][j]-ю ячейку матрицы поставим (i + j) mod k-е простое число (при индексации с нуля). Можно убедиться, что такое заполнение дает требуемый результат.
Задача D. Миньоны развлекаются
Переформулируем условие следующим образом: в неориентированном графе требуется найти цикл, у которого сумма весов минимального и максимального ребра максимальна. Во-первых, заметим, что функция \emph{верно ли, что ответ на задачу ≥ x} — монотонная. Значит, по ней можно запустить двоичный поиск. Как проверить, что ответ на задачу ≥x?
Вычтем из всех ребер x/2. Теперь надо проверить существование цикла, у которого сумма минимального и максимального ребер больше 0. Возьмем минимальное ребро с неотрицательным весом, пусть его вес равен w1. Добавим в структуру данных \emph{система непересекающихся множеств} все ребра, вес которых не превышает -w1. После этого добавим ребро w1. Если при добавлении концы ребра лежали в одной компоненте связности, то мы нашли требуемый цикл, если нет — его пока нет.
После этого продолжим алгоритм — возьмем следующее по весу неотрицательное ребро с весом w2, добавим все ребра с весами -w2…-w1–1 и добавим само ребро w2. Если при добавлении концы ребра лежали в одной компоненте, то цикл найден, если нет — его пока нет. Продолжим выполнять алгоритм для всех неотрицательных ребер.
Задача E. Лотерея
Решим сначала задачу, когда все xi различны. Отсортируем запросы в порядке возрастания xi. В каждый момент времени мы хотим знать, какие элементы массива уже заняты каким-то числом. Изначально ни один элемент массива не занят.
Пускай у нас сейчас есть массив, в нем какие-то элементы заняты. Мы хотим обработать запрос, ответ на который равен xi. Запросы для всех xj таких, что xj < xi, уже обработаны. Посчитаем количество незанятых элементов на отрезке li..ri. Пусть оно равно cnt. Тогда скажем, что во все эти элементы мы поставим какое-то число и домножим ответ на xicnt — (xi-1)cnt — количество упорядоченных наборов из cnt чисел, хотя бы одно число в которых равно xi. Число большее, чем xi, в этих элементах мы поставить не можем (ответ на запрос в таком случае не будет равен xi). Поэтому никакие массивы мы не потеряли.
После того, как мы обработаем все запросы, в пустые элементы массива мы можем поставить любые числа. Следовательно, домножим ответ на kcnt.
Полное решение: будем решать задачу также, как в предыдущем случае. Теперь у нас xi могу быть одинаковыми. Решаем задачу для запросов, ответ на которые равен x. Уберем из рассмотрения все отрезки, которые содержат в себе другие. На оставшихся посчитаем динамику: dp[i] — количество способов расставить числа на префиксе длины i так, чтобы на конце стояло число x. Тогда нам надо перебрать, когда в прошлый раз встречалось число x, пусть это позиция j (в остальных клетках между j и i числа строго меньше x), но это надо сделать так, чтобы мы не пропустили отрезок. То есть чтобы не существовало такого отрезка (l, r), с ответом x, что j < l ≤ r < i. Если такой будет, то на нем не будет ни одного x.
Следовательно, dp[i] = sum (j=k…i-1: dp[j] (x-1)i — j — 1, где k — левая граница отрезка, правая граница которого находится до позиции i и его левый конец ближе всех к это позиции i. Такая динамика будет работать суммарно за O (nm).
Заметим, что значение k для позиции i может поменяться по сравнению с позицией i-1, только если в позиции i-1 был конец какого-то отрезка. Если же в позиции i-1 не было правой гранцицы отрезка, то dp[i] = dp[i-1]×(x-1) + dp[i-1] = dp[i-1] × x. Поэтому мы можем избавиться от множителя n в асимптотике, считая значение динамики между двумя соседними правыми границами, как xcnt, где cnt — количество мест, в которые можно что-то поставить.
Получившееся решение будет работать за O (m log n + n).
