Разбор задач тренировочного warmup-раунда Russian Code Cup 2015

В воскресенье прошел тренировочный warmup-раунд Russian Code Cup. Первое место занял Михаил «mmaxio» Майоров из Перми. Второе — Игорь «kraskevich» Краскевич из Москвы. Третье — Валентин «ValenKof» Кофман из Москвы. Поздравляем победителей!

Впереди квалификационные раунды чемпионата. Напоминаем, что первый квалификационный раунд состоится 28 марта в 18:00 мск, а регистрация на чемпионат проходит на сайте http://ift.tt/1m1FZ6B до начала третьего квалификационного раунда.

Russian Code Cup — это возможность для русскоязычных программистов со всего мира проверить свои силы и продемонстрировать мастерство, решая оригинальные задачи различной сложности, а также заявить о себе экспертному IT-сообществу. Олимпиада проходит в три этапа: квалификационные раунды, отборочный тур и финал, — на каждом из которых участникам олимпиады предлагается от четырех до восьми разноплановых задач. Задания и техническую часть соревнования обеспечивают специалисты Mail.Ru Group и эксперты Университета ИТМО — соорганизатора Russian Code Cup.

А сейчас разберемся с решением задач warmup-раунда.

Задача A. Воздушные шарики



Найдем количество различных чисел в массиве. Если оно больше либо равно k, то мы можно набрать k различных цветов в ответе. Если оно меньше, чем k, то возьмем по одному шару каждого цвета, а недостающие шары возьмем произвольным образом. Найти все различные числа в массиве можно сортировкой.

Задача B. Контрольная закупка

В задаче нужно было промоделировать описанный в условии процесс. Продублируем коробки: скажем, у нас есть не одна коробка с двумя способами оплаты, а две с разными стоимостями, из которых можно купить только одну. Отсортируем по времени события: поступления денег и коробки. Причем, если время у ближайшего поступления и у коробки одинаковые, отдаем предпочтение поступлению. Для каждого события поступления денег просто прибавляем к текущей сумме поступившую сумму. Для каждого события появления коробки, которую мы еще не купили, проверяем, хватает ли денег, и если да, то покупаем коробку.

Задача C. Торжественный парад

Если k > n₂ или количество простых до 10⁷ меньше, чем k, то решения нет, в остальных случаях решение существует.

Воспользуемся фактом, что количество делителей у числа n= p1_s1 × p2_s2 ×… × pk_sk равно (s₁+1) × (s₂+1) ×… × (s_k+1).

Сгенерируем такую матрицу, чтобы в каждой строке и каждом столбце наборы степеней простых чисел были равны, то есть чтобы числа в них имели вид p1_s1 × p2_s2 ×… × pksk где p_i — какие-то простые числа, возможно, разные для каждой строки и столбца, а s_i — фиксированные для всех строк и столбцов числа.

Если k > n, то n₂ — (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. Возьмем минимальное ребро с неотрицательным весом, пусть его вес равен w₁ . Добавим в структуру данных \emph{система непересекающихся множеств} все ребра, вес которых не превышает -w₁ . После этого добавим ребро w₁ . Если при добавлении концы ребра лежали в одной компоненте связности, то мы нашли требуемый цикл, если нет — его пока нет.

После этого продолжим алгоритм — возьмем следующее по весу неотрицательное ребро с весом w₂ , добавим все ребра с весами -w_2..-w₁-1 и добавим само ребро w₂ . Если при добавлении концы ребра лежали в одной компоненте, то цикл найден, если нет — его пока нет. Продолжим выполнять алгоритм для всех неотрицательных ребер.

Задача E. Лотерея

Решим сначала задачу, когда все x_i различны. Отсортируем запросы в порядке возрастания x_i . В каждый момент времени мы хотим знать, какие элементы массива уже заняты каким-то числом. Изначально ни один элемент массива не занят.

Пускай у нас сейчас есть массив, в нем какие-то элементы заняты. Мы хотим обработать запрос, ответ на который равен x_i . Запросы для всех x_j таких, что x_j < x_i , уже обработаны. Посчитаем количество незанятых элементов на отрезке l_i..r_i . Пусть оно равно cnt. Тогда скажем, что во все эти элементы мы поставим какое-то число и домножим ответ на x_icnt — (x_i-1)_cnt — количество упорядоченных наборов из cnt чисел, хотя бы одно число в которых равно x_i . Число большее, чем x_i , в этих элементах мы поставить не можем (ответ на запрос в таком случае не будет равен x_i ). Поэтому никакие массивы мы не потеряли.

После того, как мы обработаем все запросы, в пустые элементы массива мы можем поставить любые числа. Следовательно, домножим ответ на k_cnt .

Полное решение: будем решать задачу также, как в предыдущем случае. Теперь у нас x_i могу быть одинаковыми. Решаем задачу для запросов, ответ на которые равен 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 в асимптотике, считая значение динамики между двумя соседними правыми границами, как x_cnt , где cnt — количество мест, в которые можно что-то поставить.

Получившееся решение будет работать за O(m log n + n).

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.