Всем привет!

10 сентября 2017 года, в 13:00 по московскому времени состоится финал Russian Code Cup 2017! Раунд продлится 3 часа. 55 участников финального раунда сразятся за призы, и мы все с нетерпением ждем возможности поболеть за них на сайте http://russiancodecup.ru.

Ну а для всех остальных участников мы подготовили сюрприз: если вы хотите попробовать свои силы в решении задач, приходите на codeforces.com после финала, в 16:35 по московскому времени состоится раунд по задачам RCC 2017, открытый для всех желающих.

Несколько уточнений:

• Раунд пройдет по правилам ACM;
• Раунд будет нерейтинговым;
• Сложность задач будет близка к Div 1 раунду;
• Мы просим участников финала после окончания официального соревнования воздержаться от публикации и обсуждения задач до окончания раунда-трансляции, и, разумеется, в нем не участвовать;
• Производительность инвокеров сайта RCC и CF различная, "у меня прошло/не прошло решение на CF, а на RCC было по-другому" не может быть поводом для апелляции.

UPD Официальное соревнование завершено, поздравляем победителей! Всем остальным удачи на раунде.

UPD2 Разбор задач

Всем привет!

Во время проведения отборочного тура RCC произошла техническая накладка, из-за которой в течение примерно 5 минут, с 5 по 10 минуту соревнования, все отправленные решения по задаче A, которые выводили корректно отформатированный вывод, принимались проверяющей системой как правильные.

Когда мы обнаружили проблему, было поздно перетестировать эти решения, поскольку прошло уже довольно много времени. Тем не менее, мы понимаем, что эта накладка создала неравные условия для участников и могла привести к тому, что состав финалистов и состав получателей фирменных футболок чемпионата мог измениться.

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

1) Увеличить число финалистов до 55. Это частично компенсирует тот факт, что некоторые участники могли несправедливо получить меньшее штрафное время и вытеснить из финалистов других участников.

2) Увеличить число получателей футболок до 205. Таким образом все, сдавшие хотя бы 3 задачи, получают фирменную футболку чемпионата.

Жюри и техническая группа Russian Code Cup приносят всем извинения за накладку. Мы предпримем все возможные усилия, чтобы в будущем подобного не произошло.

Желаем удачи всем финалистам на финальном раунде, который состоится в сентябре 2017 года!

A. Маленькие числа

Для начала разложим числа a и b на простые.

Теперь заметим, что если какое-то простое число p входит в произведение ab в степени выше первой, то мы можем либо сразу поделить оба числа на число p, либо если же одно из чисел не делится на p, то перенесём в него множитель p из другого числа, после чего поделим на p.

Очевидно, что чётность вхождения простых чисел в произведение ab не меняется во всех операциях. Тогда давайте оставим все простые в первой степени. Остались числа p₁, p₂, ..., p_n. Давайте назовём произведение всех этих простых чисел d, d ≤ ab. Утверждается, что этих простых не может быть больше 14. Если 1 ≤ a, b ≤ 10⁹, то произведение ab ≤ 10¹⁸, а произведение первых 15 простых чисел превышает 10¹⁸) Теперь заметим, что конечный ответ — пара чисел (x, y) таких, что xy = d. Из этого следует, что второй элемент пары определяется однозначно по первому. Переберём всевозможные делители d за число x за O(2ⁿ), и выберем наилучшую пару.

B. Новая клавиатура

Используем для решения метод динамического программирования. Состояние — d[i][j][k], где i — флаг, обозначающий тип предыдущего действия (0, если это было переключение раскладки, и 1, если это был набор символа), j — номер текущей раскладки, и k — количество набранных символов. Значение — минимальное время, необходимое, чтобы достичь этого состояния.

Переберем k. Для фиксированного k переберем j от 1 до n два раза. Обновим d[0][j % n + 1][k] = min(d[0][j % n + 1][k], min(d[0][j][k] + b, d[1][j][k] + a)). Перебрать j от 1 до n два раза нужно потому, что после набора k-го символа может быть включена раскладка с номером большим, чем раскладка, в которой будет набран следующий символ, и будет необходимо произвести переключение раскладок по циклу до нужной. После этого переберем j еще раз и обновим значения для k + 1. Если в j-й раскладке есть k-й символ сообщения, d[1][j][k + 1] = min(d[0][j][k], d[1][j][k]) + c.

В конце ответ равняется min(d[1][j][m]), где m = length(s), по всем j от 1 до n.

C. Складывание фигуры

Заметим, что возможных линий сгиба ровно 4: две по горизонтали и две по вертикали, так как фигура должна полностью лежать с одной из сторон сгиба, а также касаться его.

Возьмем любую из клеток сложенной фигуры с минимальной координатой по оси OX — клетку (x_i, y_i). За линию сгиба возьмем вертикальную прямую x = x_i, касающуюся этой клетки. Теперь слева нужно восстановить k - n клеток первоначальной фигуры, чтобы после складывания левой части вдоль линии сгиба на правую получилась данная во входных данных сложенная фигура. Так как k - n ≤ n (иначе после сгиба получилось бы больше n клеток), достаточно выделить из сложенной фигуры k - n клеток, образующих связную фигуру, содержащую клетку (x_i, y_i). Это можно сделать простым обходом в глубину.

D. Остроугольные треугольники

Для подсчета числа остроугольных треугольников достаточно из общего числа треугольников вычесть количество прямоугольных и тупоугольных треугольников. Будем считать три точки на одной прямой вырожденным тупоугольным треугольником.

Общее количество треугольников, которые можно построить с вершинами в заданных точках равно C_n³.

Заметим факт: количество прямоугольных и тупоугольных треугольников равно количеству прямых и тупых углов с вершинами в заданных точках.

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

Время работы решения: O(n²log(n)).

E. Объединение массивов

Приведем два решения этой задачи — за O(k²·log(k)) и O(k²).

Решение за O(k²·log(k)):

Разобьем решение задачи на три пункта:

• 1) Для каждого массива X (A или B) и каждой длины 1 ≤ length ≤ |X| найдем minSubsequence_X[length] — лексикографически минимальную подпоследовательность X длины length;
• 2) Переберем длину подпоследовательности в первом массиве — 1 ≤ t ≤ min(k - 1, |A|). Если 1 ≤ k - t ≤ |B|, возьмем minSubsequence_A[t] и minSubsequence_B[k - t], их надо объединить;
• 3) Объединим две подпоследовательности в одну, получив тем самым лексикографически минимальную подпоследовательность длины k, обновим ответ.

1) Чтобы найти minSubsequence_X[length] для каждого length, выполним следующие пункты:

• Посчитаем next[i][c], в котором будет храниться следующее после i вхождение символа c в X;
• Посчитаем firstSymbol[length][i] — первый символ лексикографически минимальной подпоследовательности массива X[i..|X| - 1] длиной length. Для этого заметим следующее:
  • Если j₁ = next[i][1] существует, то firstSymbol[1][i], firstSymbol[2][i], ... firstSymbol[|X| - j₁][i] начинаются с 1;
  • Если j₂ = next[i][2] существует, то firstSymbol[|X| - j₁ + 1][i], ..., firstSymbol[|X| - j₂][i] начинаются с 2;
  • ...
  • Если j_|alphabet| = next[i][|alphabet| существует, то firstSymbol[max(|X| - j₁, |X| - j₂, ..., |X| - j_{|alphabet| - 1}) + 1][i], ..., firstSymbol[|X| - j_|alphabet|][i] начинаются с |alphabet|.
  где alphabet — максимальное возможное число в массиве X.
• Посчитав firstSymbol[length][i], можно восстановить лексикографически минимальную подпоследовательность X для каждой длины итеративно по одной букве.

Этот пункт работает за O(|X|²).

3) Найдя две лексикографически минимальные подпоследовательности S_A и S_B, их надо объединить в одну лексикографически минимальную длиной k. Будем двигаться по подпоследовательностям двумя указателями p₁ и p₂. Если S_Ap1 ≠ S_Bp2, то двигаем указатель, стоящий на меньшем числе. Если S_Ap1 = S_Bp2, двоичным поиском найдем наибольший общий префикс S_A[p₁..|S_A|] и S_B[p₂..|S_B|] и сравним следующие числа. Для сравнения подотрезков S_A и S_B можно использовать хеши.

Этот пункт работает за O((|S_A| + |S_B|)·log(max(|S_A|, |S_B|))) = O(k·log(k)).

Итого, суммируя все три пунта, получаем асимптотику O(|A|² + |B|² + k²·log(k)) = O(k²·log(k)).

Решение за O(k²):

Будем называть массив A нулевым, а массив B — первым. Будем строить ответ по одному элементу. Также будем поддерживать вспомогательное значение dp[i][j], где i — номер массива (0 или 1), а j — индекс в этом массиве. dp[i][j] равно минимальному индексу в массиве 1 - i, с которого можно продолжать строить ответ, если в массиве i мы остановимся на индексе j.

На t-й из k итераций построения ответа будем находить минимальный элемент, такой, что, добавив его в ответ, последовательность можно закончить, то есть что оставшихся элементов хотя бы k - t - 1. Также нужно учесть, что подпоследовательности обоих массивов, из которых строится ответ, должны быть обе непустые.

После добавления найденного элемента v в ответ, за O(|A| + |B|) обновим значения dp. Для обновления будем пользоваться посчитанным в предыдущем решении массивом next.

F. Два поддерева

По условию, в k-поддереве обязательно есть вершины на глубине k. Временно отменим это требование.

Рассмотрим все k-поддеревья для некоторого k. Их можно разбить на классы эквивалентности. Каждой вершине поставим в соответствие c_k[v] — метку класса эквивалентности, которому принадлежит её k-поддерево.

При k = 0 все c₀[v] равны, так как 0-поддерево любой вершины — это она сама.

При k = 1 c₁[v] равно количеству детей вершины.

Научимся по массивам c_k[v] и c_m[v] строить массив c_k + m[v]. Для начала, поставим в соответствие каждой вершине v массив arr_k + m[v], который будет однозначно задавать класс эквивалентности её k + m-поддерева. Пусть u₁, ..., u_s — потомки вершины v на расстоянии k в порядке обхода dfs. Тогда поставим в соответствие вершине v массив arr_k + m[v] = c_k[v], c_m[u₁], ..., c_m[u_s]. То есть, k + m-поддерево вершины задаётся k-поддеревом вершины и m-поддеревьями нижней части k-поддерева. Ниже приведена иллюстрация для k = 3 и m = 1.

Чтобы получить для каждой вершины список её потомков на расстоянии k, запустим поиск в глубину от корня. Будем поддерживать в стеке путь до корня и каждую вершину класть в массив для её предка на расстоянии k.

Чтобы преобразовать массивы arr_k + m[v] в числа c_k + m[v], можно захешировать их, использовать бор или unordered_map из массива в номер. Время работы будет O(n), поскольку каждая веришна встречается в списках arr только один раз.

Имея массив c_k[v], можно легко проверить, что существует два одинаковых k-поддерева. Для этого нужно найти две вершины с одинаковым c_k, при этом нужно рассматривать только вершины, у которых есть потомки на расстоянии k от неё (это то требование, которое мы отменили в начале).

Чтобы найти максимальное k, посчитаем c₁[v], c₂[v], ..., c_2^t[v] (2^t — максимальная степень двойки, не превосходящая n). После этого используем аналог двоичных подъемов по k: начнём с k = 0 и по очереди попытаемся прибавить к нему 2^t, 2^t - 1, ..., 2⁰.

Время работы решения: O(nlog(n)).

На старт, внимание, марш!

Настало время определить 50 участников, которые сразятся в финале Russian Code Cup в сентябре. Приглашаем тех, кто прошел квалификацию, принять участие в отборочном раунде в воскресенье, 14 мая 2017 года, в 13-00 по московскому времени. Раунд продлится 2 часа. Ждем всех на russiancodecup.ru, всем удачи!

A. Электронные таблицы

Вычтем из k единицу, перейдя к нумерации столбцов с 0.

Выясним сначала, сколько символов входит в название столбца. Для этого будем последовательно отнимать от k степени числа 26, пока очередная степень не окажется больше оставшегося числа k'.

Теперь для получения имени столбца достаточно перевести k' в 26-ричную систему счисления с цифрами A–Z и дополнить ведущими нулями (точнее символами A) до необходимого числа символов. Это можно сделать стандартными методами языка программирования (правда при этом получатся цифры 0–9, A–P, их надо будет заменить), либо самостоятельно реализовав алгоритм перевода в систему счисления с заданным основанием.

Небольшое замечание: за день до тура один из тестеров указал, что задача B с раунда CF Beta 1 очень похожа на эту задачу. После некоторого обсуждения, учитывая, что раунд 1 на CF был очень давно, наша задача существенно проще, а хорошо подготовленной, достаточно простой замены у нас не было, мы решили оставить эту задачу в раунде.

B. Смертный бой

Посчитаем количество единиц здоровья, которое i-й персонаж до своей гибели может снять боссу в одиночку: p_i = a_i·⌈ h_i / A⌉. После этого отсортируем персонажей по невозрастанию p_i и будем посылать их к боссу по одному в этом порядке, пока он не будет убит.

C. Слегка палиндромные числа

Научимся считать количество слегка палиндромных чисел среди первых n натуральных чисел. Чтобы получить количество таких чисел на отрезке с l по r, нужно посчитать их количество среди первых r и l - 1 натуральных чисел и вычесть одно из другого.

Все числа от 1 до 9 слегка палиндромные, поэтому если n ≤ 9, то ответ равен n. В противном случае прибавим к ответу 9 и посчитаем количество слегка палиндромных чисел на отрезке с 10 по n. Рассмотрим десятку чисел от 10k до 10k + 9, где k ≠ 0. Среди них ровно одно слегка палиндромное, так как последняя цифра должна равняться первой цифре k. Таким образом, есть по одному слегка палиндромному числу на отрезках от 10 до 19, от 20 до 29, и так далее.

Пусть n = 10k + d, где 0 ≤ d ≤ 9. Тогда на отрезке от 10 до n находятся k слегка палиндромных чисел, если d не меньше первой цифры k (а она равна первой цифре n), и k - 1, если меньше.

D. Дерево и многочлены

Сформулируем ключевые идеи решения.

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

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

Однако мы не можем выполнять запросы в явном виде, рассматривая все вершины, фигурирующие в запросе, и прибавляя к хранящимся в них многочленах многочлен из запроса — такое решение будет работать за O(n²·k) и не укладывается в ограничения по времени. Поэтому воспользуемся идеей отложенных операций.

В запросах первого типа нужно добавить многочлен q(x) в каждую вершину поддерева v. Для этого просто оставим пометки, что это надо сделать: будем хранить в вершине v многочлен push1[v], при выполнении запроса первого типа прибавим многочлен q к многочлену push1[v].

Аналогично для запросов второго типа будем использовать многочлен push2[v], который для каждой вершины будет хранить сумму многочленов из запросов второго типа к этой вершине.

Пускай теперь sum1[u]  — сумма всех многочленов, которые нужно было учесть в вершине u в запросах первого типа.

Для вычисления sum1[u] выполним поиск в глубину от корня дерева, который будет поддерживать многочлен cur и прибавлять к многочлену cur значение push1[v] при посещении новой вершины v и вычитать его обратно при выходе из неё. Соответственно, находясь в вершине u присваиваем sum1[u] = cur.

Аналогично, обозначим как sum2[u]  — сумма всех многочленов, которые нужно было учесть в вершине u в запросах второго типа.

Для вычисления sum2[u] также поспользуемся обходом в глубину. Значение sum2[u] равно сумме значений sum2[v] для детей u и значения push2[u].

Получив многочлены sum1[u] и sum2[u] в каждой вершине, вычислим их значение от величины d[u] и сложим, результат и будет ответом.

Время работы решения — O(nk).

E. Красивый отчёт

Перед решением основной задачи решим следующую, пока слабо связанную с исходной, задачу: на вход даётся последовательность элементов (a₁, a₂, ..., a_n) и нужно посчитать число различных элементов в этой последовательности. Особенностью этой задачи будет то, что:

1. элементы можно считывать только последовательно и только один раз: после считывания элемента a_i последует считывание a_i + 1, вернуться к a_i будет нельзя;
2. вы не можете использовать больше O(1) дополнительной памяти.

Чтобы подойти к решению этой подзадачи, вспомним, что математическое ожидание минимума из m равномерно распределённых на отрезке [0;1] случайных величин равно 1 / (m + 1). Например, если вы возьмёте четыре случайных числа из отрезка [0;1], то минимальное из этих чисел в среднем будет равно 0, 2.

Возьмём хеш-функцию h: A → [0;1], отображающую элементы a_i в числа на отрезке [0;1]. Посчитаем значение M = min {h(a₁), h(a₂), ..., h(a_n)}. В качестве ответа на задачу вернём 1 / M - 1. Проблемой этого решения является то, что нам может «не повезти» и, например, h(a_i) окажется очень маленьким, что окажет существенное влияние на ответ. Чтобы сгладить эту проблему, повторим описанный процесс несколько раз для различных хеш-функций h₁, h₂, ..., h_k для некоторого фиксированного k и усредним полученные результаты.

Вернёмся к нашей задаче поиска числа достижимых вершин. Рассмотрим сначала случай ацикличного графа. Ациклический граф отличается от графа с циклами, в том числе, тем, что у него существует топологическая сортировка: такой порядок следования вершин, при котором рёбра графа идут только от вершин, стоящих в порядке позже к вершинам, стоящим в порядке раньше. Существование топологической сортировки позволит для графа, в котором в каждой вершине записано случайное число из отрезка [0;1] посчитать, какое минимальное число достижимо из каждой вершины. Это можно сделать с помощью динамического программирования: рассматривание вершин в порядке топологической сортировки позволит посчитать значение для текущей вершины на основе уже посчитанных достижимых из неё. Посчитав минимальное достижимое число M_i из каждой вершины, можно указать в качестве ответа для данной вершины 1 / M_i - 1. Описанное требуется повторить несколько раз и усреднить результаты.

Однако, в данной задаче в графе могут быть циклы. Чтобы решить эту проблему, построим конденсацию графа. В полученном ацикличном графе в каждой вершине находится, на самом деле, несколько вершин начального графа. Для всех этих вершин ответ будет один и тот же. Отличие в подсчёте ответа будет заключаться в том, что в вершину пишется не случайное число из [0;1], а минимум из w_i случайных чисел из [0;1], где w_i — число вершин начального графа, содержащихся в i-й вершине сконденсированного.

Более подробно с методом решения этой и некоторых других подобных задач любопытный читатель может ознакомиться в статье "Size-Estimation Framework with Applications to Transitive Closure and Reachability", доступной по адресу http://cohenwang.com/edith/Papers/tcest.pdf.

Всем привет!

Пока более 400 участников уже готовятся сразиться в отборочном раунде Russian Code Cup 2017, тех, кто пока не квалифицировался, мы приглашаем принять участие в третьем квалификационном раунде, который состоится в субботу, 29 апреля, в 14-00. Лучшие 200 участников смогут также принять участие в отборочном раунде и побороться за выход в финал Russian Code Cup 2017.

Всем удачи и до встречи на russiancodecup.ru!

A. Очень важные гости

Есть два способа решить эту задачу.

Первый заключается в том, чтобы рассаживать гостей по диагоналям, начиная от позиции (1, 1). Требуется некоторая аккуратность в реализации, чтобы верно учесть случаи n < m и m < n.

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

B. Наименьшее общее кратное

Пусть p / q нацело делится на a / b и c / d, при этом все дроби несократимые. Тогда целыми числами являются (p / q): (a / b) = (p·b) / (q·a) и (p / q): (c / d) = (p·d) / (q·c).

p·b делится на q·a. Поскольку b и a взаимно просты, p делится на a. p и q тоже взаимно просты, поэтому b делится на q. Аналогично, p делится на с и d делится на q.

Таким образом, p делится lcm(a, c), q делит gcd(b, d). Дробь lcm(a, c) / gcd(b, d) является наименьшей подходящей дробью, и она делится на a / b и c / d. Таким образом, ответ равен lcm(a, c) / gcd(b, d).

C. Портим порядок

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

Для начала допустим, что мы уже сгенерировали какую-то перестановку и хотим узнать, сколько обменов совершит сортировка выбором. Для этого будем рассматривать перестановку как набор циклов. Рассмотрим цикл, в котором содержится минимальное число, которое стоит не на своём месте. Длина этого цикла больше чем 1. Нетрудно заметить, что при одном обмене длина соответствующего цикла уменьшается на один и появляется новый цикл длины 1. Теперь заметим, что цикл длины L уменьшит свою длину ровно L - 1 раз в процессе сортировки, из чего следует, что суммарно длины циклов уменьшатся ровно на n - c, где c — количество циклов.

Таким образом нам нужно дополнить массив до перестановки таким образом, чтобы количество циклов получилось минимальным. Для этого рассмотрим перестановку как ориентированный граф, где если a[i] = j, то в графе есть ребро из вершины i в вершину j. Граф разбился на циклы и цепочки. Все циклы, которые есть в этом графе, сохранятся и после добавления недостающих элементов, а все имеющиеся цепочки (вершину, не имеющую ни входящих, ни исходящих ребер, будем считать цепочкой длины 0) можно объединить в один большой цикл. Пройдемся по всем имеющимся цепочкам и будем добавлять ребро из конца одной цепочки в начало другой. Когда все цепочки соединены в одну, добавим ребро из её конца в начало, и она станет циклом.

D. Красно-черное дерево

Заметив тонкий намек в первом предложении условия, легко доказать (или проверить в любой книге по структурам данных), что в любом красно-черном дереве с n вершинами, на пути от корня до листьев O(logn) черных вершин. Воспользуемся этим фактом в решении.

Назовем почти красно-черным дерево, в котором выполняются все свойства красно-черного дерева, но корень дерева покрашен в красный цвет.

С помощью динамического программирования посчитаем для каждого поддерева количество способов покрасить вершины в нем так, чтобы поддерево было красно-черным, и количество черных вершин на пути от корня до листьев равнялось h, или чтобы дерево было почти красно-черным, и количество черных вершин на пути от корня до листьев равнялось h.

Сохраним это количество способов в массиве d[v][h][t], где v — номер вершины, являющейся корнем поддерева, h — количество черных вершин на пути от корня до листьев, а t обозначает тип покраски, при t равном 0, там хранится количество покрасок, чтобы поддерево стало красно-черным, а при t равном 1, чтобы поддерево стало почти красно-черным.

Тогда d[v][h][0] равняется произведению по всем u, являющимся детьми v, значений (d[u][h - 1][0] + d[u][h - 1][1]). А d[v][h][1] равняется произведению по всем u, являющимся детьми v, значений d[u][h][0].

Ответ на задачу будет равен сумме по всем d[1][h][0].

Теперь заметим, что h для всех допустимых раскрасок поддеревьев ограничено некоторой величиной C = O(log(n)), и при всех h > C, количество покрасок гарантированно будет равняться нулю.

Значит, необходимо всего O(nlog(n)) состояний, из каждого из которых идет O(1) переходов. Следовательно решение будет работать за O(nlog(n)).

E. Изучение массива

Поскольку ограничения на n и q совпадают, будем использовать в n вместо max(n, q). Сделаем несколько наблюдений.

Первое наблюдение: ответ на запрос — максимальная длина отрезка [L, R], такого, что pref_L - 1 = pref_R, где pref_i = a₁ + a₂ + ... + a_i — префиксная сумма массива a (pref₀ = 0). Далее будем считать, что мы работаем с массивом pref₀, pref₁, ..., pref_n, и по запросу [l, r] требуется найти максимальный по длине подотрезок [L, R] отрезка [l - 1, r], такой, что pref_L = pref_R.

Второе наблюдение: pref_i — довольно маленькие ( - n ≤ pref_i ≤ n).

Будем решать задачу оффлайн. Воспользуемся методом, во многом похожим на алгоритм Мо. Разобьем все запросы на группы, где в i-й группе содержатся запросы [l_i, r_i], такие, что i·K ≤ l_i < (i + 1)·K (K — константа, приблизительно равная sqrt(n)). В каждой группе отсортируем запросы по правой границе. Теперь решим задачу отдельно для каждой группы запросов.

Рассмотрим i-ю группу [L_i, R_i]. Будем идти подряд по запросам слева направо (то есть по неубыванию правой границы). Также будем поддерживать два массива mostLeft[p] и mostRight[p] — текущее самое левое вхождение префиксной суммы p, которое также левее R_i и текущее самое правое вхождение префиксной суммы p. Поддерживая эти два массива, также несложно поддерживать ответ на отрезке [R_i + 1, r], где r — правая граница текущего запроса. Для ответа на запрос [l, r] посчитаем за O(K) ответ на [l, min(r, R)], используя информацию из массива mostRight и сравним это значение с текущим ответом на отрезке [R + 1, r].

Итого, на запросы каждый группы в сумме мы тратим O(K·c_i + n) времени, где c_i — количество запросов в группе. Так как групп всего O(n / K), получаем суммарное время работы O(sum_{i = 1... n / K}(K·c_i + n)) = O(K·sum(c_i) + n² / K). При K = sqrt(n) получаем время работы O(n·sqrt(n))

Всем привет!

Лучшие 200 участников первой квалификации уже в отборочном раунде, а остальные могут попытать свои силы во втором квалификацоинном раунде. Он состоится в это воскресенье, 16 апреля в 12-00 по Московскому времени . Лучшие 200 участников попадут в отборочный раунд, а остальные смогут попытать свои силы еще один раз, в третьем квалификационном раунде.

Желаем всем удачи на раунде и ждем на http://russiancodecup.ru!

A. Марсианский волейбол

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

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

Итоговый ответ max(k, min(x, y) + 2) - max(x, y).

B. Раскраска стены

Чтобы решить данную задачу, поймем сколько минимум цветов нужно, чтобы условия выполнялись. Для этого найдем самый длинный непрерывный отрезок плиток по вертикали или по горизонтали. Пусть длина этого отрезка равна L.

Затем представим квадрат L × L, где первая строка это последовательность чисел от 1 до L, а каждая следующая получается циклическим сдвигом предыдущей на один вправо. Такими квадратами замостим наш исходный прямоугольник, откинув лишнее и не забыв про лампы. Например, если L = 4, замощение будет начинаться так:

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

Если у Маши цветов меньше чем L, то ответа не существует.

C. Магический артефакт

Обозначим как c_i выигрыш во времени, который Максим получает от артефакта на i-м уровне: c_i = a_i - b_i.

Пусть уровни проходятся в порядке 1, 2, ..., n. Если артефакт был найден на i-м уровне, то время прохождения равно сумме значений b_j плюс c₁ + ... + c_i. Тогда математическое ожидание времени прохождения равно:

b₁ + ... + b_n + p₁·c₁ + p₂·(c₁ + c₂) + ... + p_n·(c₁ + ... + c_n).

b₁ + ... + b_n не зависит от порядка уровней, поэтому будем стремиться уменьшить оставшуюся часть суммы. Если раскрыть скобки, можно заметить, что она равна сумме c_i·p_k по всем парам i, k, таким что i ≤ k.

Посмотрим, как изменится сумма, если поменять местами уровни i и i + 1. Среди слагаемых c_i·p_k изменится только c_i·p_i + 1 — оно заменится на c_i + 1·p_i. Если порядок уровней является оптимальным, то c_i·p_i + 1 ≤ c_i + 1·p_i (иначе их можно было бы поменять местами и улучшить ответ). Преобразуем это неравенство:

c_i / p_i ≤ c_i + 1 / p_i + 1.

В оптимальном ответе для всех i от 1 до n - 1 верно это неравенство. Значит, в оптимальном ответе уровни отсортированы по c_i / p_i, и чтобы получить его, нужно их отсортировать. Заметим, что если p_i = 0, можно считать c_i / p_i = ∞.

Сортировать по c_i / p_i нужно осторожно. Если производить деление в числах с плавающей точкой, то в случае, когда c_i = p_i = 0, получится NaN, что приведёт к ошибке. Если сравнивать дроби c_i / p_i и c_k / p_k при помощи компаратора c_i·p_k < c_k·p_i, то в случае, когда c_i = p_i = 0, результат всегда будет false, что тоже приведёт к неправильной сортировке. Поэтому уровни с c_i = p_i = 0 нужно обработать отдельно. Эти уровни могут быть пройдены в любой момент: нетрудно заметить, что они не вносят никакого вклада в ответ, кроме фиксированных слагаемых b_i. Их можно поместить, например, в самый конец.

После сортировки нужно посчитать искомое математическое ожидание. Оно вычисляется по вышеприведённой формуле при помощи префиксных сумм c_i.

D. Менеджер памяти

Для начала для каждого запроса q_i найдем go_i — минимальное j, такое, что среди q_j, q_j + 1, ..., q_i не более k различных чисел — это будет означать, что перед j-м запросом можно так поставить указатели, что j, j + 1, ..., i запросы выполнятся мгновенно. Это делается за O(sum(|q_i|)) например двумя указателями, идя с конца массива запросов.

Теперь будем использовать динамическое программирование, вычислим значения dp_i — минимальная время, за которое можно выполнить первые i запросов. Если go_i = 0, то dp_i = 0. Если нет, то несложно видеть, что dp_i = min_{j = goi..i}(dp_j - 1 + s_j) — мы выбираем, запрос j, перед которым будем менять указатели, и платим соответствующую стоимость. Так как go_i не убывают, посчитать эту величину можно либо поддерживая set значений dp_j - 1 + s_j, либо используя очередь с операцией «минимум».

E. ЛИСА

Рассмотрим сначала задачу для двух конкретных строк: посчитаем число вхождений каждой буквы в первую строку, и количество каждой вхождений буквы во вторую строку, не будем при этом учитывать первую букву в первой строке и последнюю букву во второй строке, которые надо взять в любом случае. Чтобы получить ответ, надо вычислить произведение длин строк и отнять от это го значения сумму cnt1[letter] * cnt2[letter] по всем буквам. Доказательство этого утверждения оставим как упражнение, такая задача предлагалась на северном четвертьфинале 2015 http://neerc.ifmo.ru/archive/2015/northern/north-2015-statements.pdf, задача C. Широкий круг участников мог решать ее на кубке трех четвертьфиналов.

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

Осталось научиться отвечать на запросы на отрезке. Будем использовать sqrt-декомпозицию, разобьем строки в группы по сумме длин. Будем жадно набирать в группу строки, пока суммарная длина в группе не станет больше корня из суммы длин, последняя строка может быть достаточно большой.

Теперь используем алгоритм Мо, отсортируем запросы по блоку левой границы, при равном блоке по правой границе, тогда между сменами блока левой границы правая граница будет двигаться только вправо. Чтобы добавить или удалить строку из бора будем пересчитывать количество вершин в поддереве и, соответственно, число вхождений букв в бор.

Всем привет!

Уже совсем скоро, в это воскресенье, 2 апреля в 19-00 по московскому времени состоится первый квалификационный раунд Russian Code Cup 2017. Лучшие 200 участников попадут в отборочный раунд, а остальные смогут попытать свои силы еще 2 раза, во втором и третьем квалификационных раундах.

Мы приготовили для вас небольшие новинки: в список языков на раунде будут добавлены Kotlin, Haskell и Free Pascal, а в список интерпретаторов языка Python — интерпретатор PyPy. Точные версии компиляторов и строки компиляции опубликованы в правилах олимпиады на сайте. Мы также работаем над добавлением новых языков в дальнейших раундах.

Желаем всем удачи на раунде и ждем на http://russiancodecup.ru!

UPD Выложен разбор задач

Всем привет и спасибо тем, кто принял участие в разогревочном раунде.

Во-первых, хотелось бы извиниться перед участниками за очереди тестирования в середине-конце первого часа. Для разогревочного раунда мы решили использовать задачи ИОИП — команда авторов задач RCC и ИОИП в целом совпадает — тур подготовили Виктория Ерохина (viktoria), Илья Збань (izban), Станислав Наумов (josdas), Михаил Путилин (SpyCheese), Андрей Станкевич (andrewzta), Дмитрий Филиппов (DimaPhil), Григорий Шовкопляс (GShark). Мы хотели дать возможность всем желающим познакомиться с довольно интересным, на наш взгляд, набором задач.

К сожалению, мы не учли один аспект. Можно заметить, что в RCC мы стараемся делать мультитест в задачах, ведь самая затратная операция — запустить решение участника на тесте. Поскольку ИОИП расчитывалась на меньшую нагрузку, в первой задаче оказалось 32 теста. Это не так много по меркам олимпиадной задачи, но когда в течение 15 минут 400 участников прислали правильное решение этой задачи, наших проверяющих мощностей не хватило.

Мы оперативно уменьшили число тестов в задаче и к середине контеста ситуация нормализовалась. Мы учтем этот эффект и будем тщательнее планировать формат тестов в задачах будущих контестов.

Перейдем теперь к разбору.

Всем привет!

Мы рады представить Russian Code Cup 2017! Отборочные раунды начнутся в апреле, а финальный раунд пройдет онлайн в сентябре. В каждом из трех квалификационных раундов в отборочный раунд выйдет по 200 лучших участников, а 50 лидеров отборочного раунда попадут в финал. Задачи будут предложены на русском и английском языках.

Найти полное расписание турнира и зарегистрироваться можно на http://russiancodecup.ru, обратите внимание, что тем, кто участвовал в прошлые годы, необходимо подтвердить регистрацию на этот сезон.

Пока до первого квалификационного раунда еще больше двух недель, мы хотели бы пригласить всех на разогревочный раунд в воскресенье, 19 марта, в 14-00 по московскому времени. Раунд пройдет на http://russiancodecup.ru, продлится 2 часа и позволит познакомиться с системой и потренироваться перед основными раундами.

Удачи всем и до встречи на раундах!

UPD: Напоминаем, контест начнется в 14-00 по московскому времени. Задачи разогревочного раунда базируются на задачах заключительного этапа ИОИП, которую готовит та же команда авторов. Мы просим участников ИОИП поступить честно и не принимать участие в разогревочном раунде. Всем удачи!

UPD2: Спасибо всем участникам, которые устоили нам настоящее стресс-тестирование. К сожалению, в первый час контеста очереди были существенными, мы постарались решить эту проблему, и где-то с середины тура задержки уже не должны превышать 2-3 минут. Мы не допустим образования очередей в квалификационном и отборочном турах.