Во-первых, поздравляем jqdai0815 с победой, LHiC и jcvb со вторым и третьим местом. Финал оказался сложным и мы рады, что борьба была жесткой.

Задачи для раунда придумали и готовили Aksenov239, GShark, izban, manoprenko, niyaznigmatul, qwerty787788 и SpyCheese, руководитель жюри andrewzta. Отдельно хочется отметить Илью Збаня izban, который является автором задач D, E и F, а также дал огромное количество полезных комментариев по всем задачам раунда.

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

E. Спутники

Любая точка X задаётся двумя углами α = XAB и β = XBA.

Точка (α₂, β₂) находится в зоне покрытия спутника в точке (α₁, β₁), если α₂ ≤ α₁ и β₂ ≤ β₁.

Пусть два спутника, между которыми нужно установить связь, находятся в точках (α₁, β₁) и (α₂, β₂). Ретранслятор должен находиться в такой точке (α₀, β₀), что α₀ ≤ min(α₁, α₂) и β₀ ≤ min(β₁, β₂). Поскльку требуется, чтобы он не находился в зоне видимости других спутников, следует выбирать α₀ и β₀ как можно больше: α₀ = min(α₁, α₂), β₀ = min(β₁, β₂).

Перейдём к решению. Рассмотрим запрос типа 3: даны два спутника (α₁, β₁) и (α₂, β₂). Нужно проверить, что точку (α₀, β₀) = (min(α₁, α₂), min(β₁, β₂)) не видит ни один другой спутник. Это означает, что среди спутников с α ≥ α₀ максимальный β меньше β₀.

Отсортируем все спутники из всего теста по α. В каждый момент времени для каждого спутника будем хранить его β, если он сейчас существует, и  - ∞, если нет. Построим на этом дерево отрезков на максимум. При добавлении и удалении спутника будем обновлять значения. При запросе типа 3 будем запрашивать максимум на суффиксе. Чтобы не учитывать два спутника из запроса 3, перед запросом максимума присвоим в их ячейки  - ∞, а затем вернём соответствующие β.

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

Кроме того, нужно проверять, что точка (α₀, β₀) не лежит внутри планеты. Точка X лежит внутри, если угол AXB тупой, то есть, скалярное произведение XA и XB меньше нуля. Точку X плохо искать в явном виде, так как её координаты не обязательно целые, но векторы, коллинеарные XA и XB, найти можно — это некоторые из векторов, соединяющие точки запроса и точки A и B.

Всем привет!

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 Разбор задач

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 минут. Мы не допустим образования очередей в квалификационном и отборочном турах.

Всем привет!

Завершился Russian Code Cup 2016, задачи финала оказались очень сложными, но участники не спасовали. Победил Геннадий Короткевич — tourist, второе место занял Владислав Епифанов — vepifanov, а замкнул призовую тройку Николай Калинин — KAN. Поздравляем победителей, официальные результаты финала на сайте http://russiancodecup.ru

Перед тем как перейти к разбору задач, хочется поблагодарить Mail.Ru Group за организацию турнира и призы, жюри из Университета ИТМО за подготовку задач. Председатель жюри Андрей Станкевич andrewzta, члены жюри Виталий Аксенов Aksenov239, Николай Будин budalnik, Артем Васильев VArtem, Николай Ведерников Niko, Илья Збань izban, Борис Минаев qwerty787788, Илья Пересадин pva701, Дмитрий Филиппов DimaPhil, Григорий Шовкопляс GShark.

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

Всем привет!

Уже завтра, 18 сентября 2016 года, в 12-00 состоится финал RCC-2016. Лучшие 50 участников отборочного раунда сразятся за ценные призы. Продолжительность финала в этом году — 2 часа, финал проходит в режиме онлайн. За ходом финала можно наблюдать на сайте http://russiancodecup.ru

А мы рады объявить, что команда Russian Code Cup совместно с проектом Codeforces приготовили небольшой сюрприз всем тем, кто не прошел на финальный раунд RCC-2016. Сразу после окончания финала, в 14-05 на платформе Codeforces пройдет онлайн-контест по задачам финала.

Контест пройдет по правилам ACM ICPC и будет нерейтинговым. Задачи буду предложены на русском и английском языках. Задачи были подготовлены для финала Russian Code Cup, и поэтому они довольно сложные, контест будет интересен, скорее, участникам из Div1. Разумеется, мы просим всех финалистов не использовать онлайн-контест для дорешивания задач, а, дождавшись окончания, дорешивать в архиве.

Итак, приглашаем всех поболеть за финалистов, а потом ждем всех желающих на онлайн-контесте! Всем удачи!

Всем привет!

Напоминаем, что 19 июня 2016 года в 14-00 по московскому времени состоится отборочный раунд Russian Code Cup 2016. В раунде могут принять участие по 200 лучших с каждой из квалификаций, 200 лучших в отборочном раунде получат футболку чемпионата, а топ 50 попадут в финал, который пройдет в сентябре, в финале участники сразятся за денежные призы.

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

Всем привет!

Последний в этом году шанс попасть в отборочный раунд Russian Code Cup предоставляется всем в это воскресенье, 5 июня в 16:00. Приглашаем всех, кто еще не прошел в отборочный раунд, принять участие. Удачи и до встречи на Russian Code Cup 2016!

Всем привет!

В воскресенье, 29 мая 2016 года, в 12-00 состоится второй квалификационный раунд Russian Code Cup! Мы будем рады видеть на нем всех, кто не прошел в отборочный раунд в первом квале. Ну а те, кто и завтра не сможет пройти в отборочный раунд, смогут принять участие в третьем квалификационном раунде 5 июня. Всем удачи и до встречи на раунде, не забудьте зарегистрироваться на чемпионат на сайте http://russiancodecup.ru

A. Двоичная строка

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

• Либо |b - c| > 1
• Либо b = 0, c = 0, и при этом a ≠ 0 и d ≠ 0

Для остальных случаев будем решать в два этапа: Сначала соберем минимальную строку, которая будет удовлетворять условиям на строки 01 и 10, а затем допишем после первого встреченного нуля a - 1 ноль, а после первой встреченной единицы d - 1 единицу. Очевидно, что условия на 01 и 10 от таких действий не испортятся.

B. Поезд и туннель

Разобьем весь поезд на отрезки вагонов без света. Будем идти по каждой группе из таких вагонов, и в том вагоне, на котором суммарная длина вагонов становится не меньше h, будем включать свет. Очевидно, что данная стратегия дает наименьший результат. Также нужно не забыть включить свет в первом и последнем вагонах: при въезде в туннель и выезде из него, соответственно, эти вагоны образуют темный момент времени.

C. Красивое разбиение

Первый элемент массива входит либо в M₁, либо в M₂. Не умаляя общности, будем считать, что он входит в M₁. Тогда a[1] делится на gcd(M₁), то есть gcd(M₁) — делитель a[1].

Переберем все делители a[1] (их не больше 1344 для чисел до 10⁹). Рассматривая текущий делитель d, возьмем все элементы массива, делящиеся на d, в M₁ (так как от этого gcd(M₁) не станет меньше d, а чем меньше элементов в M₂, тем gcd(M₂) больше), а все остальные элементы в M₂ и обновим ответ величиной min(gcd(M₁), gcd(M₂)). Заметим, что мы можем пренебречь тем, что M₂ будет пустым, считая в этом случае gcd для него равным бесконечности, поскольку все элементы в таком случае делятся на d, то и gcd(M₂) будет не меньше d.

Асимптотика решения — O(sqrt(a[1]) + d(a[1])·n), где d(a[1]) ≤ 1344.

D. Подготовка задач

Для начала решим задачу, если нет запросов на изменение времен. Из массива t_i сгенерируем новый массив cnt_j, в котором будем хранить количество задач, на которые необходимо потратить j минут, а также предподсчитаем массив его префиксных сумм. Тогда количество времени, которое потратит каждый друг, если их всего k, можно посчитать за O(MAX / k), где MAX — максимальное необходимое на задачу время (просто перебрав, на какие задачи потребуется 1, 2, ... MAX / k минут). Как известно, суммарное время работы такого алгоритма для всех k от 1 до MAX равно O(MAXlog(MAX)).

Теперь посмотрим, что происходит, когда время, необходимое на задачу, изменяется с t на t + 1. Ответы поменяются только для k являющихся делителями t. Поскольку максимальное количество делителей у чисел до 5·10⁵ равно 200, то можно просто их все перебрать за время пропорциональное их количеству и обновить ответ только для них.

Аналогично, если время изменяется с t на t - 1, то ответы меняются для чисел, которые являются делителями t - 1.

E. Похожее метро

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

Посчитаем для пары ориентированных ребер (u₁, v₁) в первом дереве и (u₂, v₂) во втором дереве значение dp[u₁][v₁][u₂][v₂], равное размеру наибольшей пары изоморфных поддеревьев, если вершина u₁ перейдет в вершину u₂, а вершины v₁ и v₂ обязательно не войдут в выбранные поддеревья. Кроме того, разрешим v_i быть равной какой-нибудь фиктивной вершине -1, это будет значить, что удаленного поддерева v_i нет, и можно использовать для общего поддерева все вершины. Если мы посчитаем такую величину, ответом будет максимум по всем парам вершин u₁, u₂ величины dp[u₁][-1][u₂][-1].

Чтобы посчитать dp[u₁][v₁][u₂][v₂], нужно каким-то образом сопоставить поддеревья u₁ и u₂ друг другу. Заметим, что если e₁ — сын вершины u₁, отличный от v₁, то поддерево e₁ содержит меньше вершин, чем поддерево u₁, при подвешивании дерева за v₁. Для сыновей e₁ вершины u₁ и e₂ вершины u₂ мы по предположению индукции уже посчитали dp[e₁][u₁][e₂][u₂], так что мы знаем, сколько вершин можно добавить в искомое поддерево, если вершине e₁ в нем будет соответствовать e₂. Если у вершины u₁ — k сыновей, у u₂ — m сыновей, то мы получаем матрицу a_i, j размера k·m, в которой нужно выбрать несколько ячеек с максимальной суммой, при условии, что в каждом столбце и в каждой строке выбрано не больше одной ячейки. Это стандартная задача о назначении, которая решается Венгерским алгоритмом.

Итоговая сложность решения — O(n⁵), n² способов выбрать пару ребер в двух деревьях и O(n³) — время работы Венгерского алгоритма. Для оптимизации можно не решать задачу о назначении для одинаковых (изоморфных) пар деревьев несколько раз, а запомнить ответ.

Всем привет!

Мы рады представить окончательную версию правил Russian Code Cup 2016! Важнейшее нововведение этого года — чемпионат становится международным, теперь задачи предлагаются на русском и английском языках. Все могут принять участие, для этого необходимо зарегистрироваться на сайте http://russiancodecup.ru, участникам прошлых чемпионатов необходимо подтвердить участие в этом году в личном кабинете.

В этом году участники вновь сразятся за звание лучшего программиста и призовой фонд в размере 750 000 рублей. Мы изменили структуру призового фонда, чтобы дать еще больше денежных призов, теперь участники, занявшие места с 11 по 25 также получат призы. Победитель чемпионата получит 150 тыс. рублей, обладатели второго и третьего места — 100 тыс. и 65 тыс. рублей, соответственно. Программистам, занявшим с четвертого по десятое места, достанется по 30 тыс. рублей, с 11 по 25 место – 15 тыс. рублей. 200 лучших участников отборочного раунда получат футболки с символикой чемпионата.

Основная программа чемпионата состоит из трех этапов: квалификационных раундов (8 мая, 29 мая и 5 июня), отборочного тура (19 июня) и финала (18 сентября). На каждом этапе участники олимпиады должны решить от четырех до восьми разноплановых задач. Программисты, которым не повезло в первом квалификационном туре, могут попытать удачу в следующих. В отборочный тур пройдут по 200 лучших участников из каждого квалификационного раунда, а в финале будут сражаться 50 лучших программистов.

Приглашаем всех на первый квалификационный раунд в воскресенье 8 мая, в 19-00 по московскому времени и желаем удачи всем участникам!

A. Секретный код

Задача относится к типу «сделайте что просят». Очевидно, как посчитать количество совпадающих символов у двух строк. Для проверки встречался ли данный символ в исходной строке достаточно предподсчитать массив логических значений used[c], где хранится true если символ c встречался в секретном коде и false иначе.

B. Хаос

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

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

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

C. Новое приключение Марти и Дока

Требуется минимизировать сумму Sum(i = 1..n, j = 1..m, 2·a_i, j·(|i - x| + |j - y| + 1)). Заметим, что нет слагаемых, зависящих от обеих коорданат, поэтому ее можно разбить на три: Sum(2·a_i, j), Sum(2·a_i, j·|i - x|) и Sum(2·a_i, j·|j - y|).

Первая сумма — константа, вторую и третью можно минимизировать независимо, выбирая, соответственно, ряд и столбец. Исходя из вида второй суммы получаем, что оптимальный ряд — медиана набора чисел Sum(j = 1..m, a_1, j) раз 1, Sum(j = 1..m, a_2, j) раз 2, ..., Sum(j = 1..m, a_n, j) раз n.

Аналогично для второй координаты.

D. Разбиение на команды

Будем решать задачу методом динамического программирования.

Для начала отсортируем все числа и посчитаем, сколько раз каждое число встречается в массиве. Если в команде есть школьники с навыками l и r, то все школьники с силой m, где l < m < r, тоже обязательно будут в этой команде. Таким образом, можно решать задачу, считая значения dp[i][j][f] — количество способов разбить всех школьников с навыком не большим i на j команд, если в последнюю (одну из команд, в которой есть школьник силы i) команду мы f=true|false добавим или не добавим еще учеников. Переход — пусть у нас есть k школьников с силой i + 1. Тогда переберем g — на сколько команд мы их разобьем, и, используя вспомогательное значение f[k][g] обновим значения dp[i + 1][j'][f']. Заметим, что время заполнения массива есть O(nk), поскольку общее число значений g для фиксированного j равно n.

Чтобы посчитать f[k][g] — количество способов разбить k школьников одинаковой силы на g команд, нужно посмотреть, в какой команде находится k-й школьник — либо в своей отдельной команде (f[k - 1][g - 1]), либо в одной из уже существовавших до него (f[k - 1][g]·g).

Итого, каждый из массивов f и dp заполняется за O(nk), поэтому все решение работает за O(nk).

E. Максимальная сумма

Отсортируем b_j по убыванию. Будем добавлять в массив a_i все числа, не меньше очередного b_j. Таким образом в массиве a_i будут содержаться только отрезки чисел, для которых выполнено a_i ≥ b_j. При добавлении очередного a_i, на каждом вновь образованном отрезке нужно находить отрезок с максимальной суммой. Это является достаточно стандартной подзадачей, которую можно решить, например, деревом отрезков (см, например, обсуждение здесь http://codeforces.com/blog/entry/17780).

Всем привет!

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

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

Всем удачи и до встречи на Russian Code Cup 2016!

Задача А. Сгибание ленточки.

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

В задаче дана полоска 1×2ⁿ, которую сначала n раз сложили ровно пополам, а потом развернули обратно. Складывания возможны двух способов: левую половину наложить на правую или правую половину наложить на левую. Требуется отвечать на запросы — по номеру сгиба узнать, ориентирован он вверх или вниз.

Научимся отвечать на запрос за O(log 2ⁿ), то есть за O(n). Суммарное количество запросов не превосходит 10⁵, поэтому этого вполне достаточно. Будем эмулировать процесс сгибания для каждого запроса. Зная текущие длину ленточки и номер сгиба, легко понять, в какой половине этот номер находится, а затем, зная, в какую сторону произойдет сгиб пополам, можно найти и новое положение сгиба в укороченной в два раза ленточке. Для ответа на запрос одновременно с положением поддерживаем, в какую сторону сейчас ориентирован сгиб. Итого, получаем решение за O(qn), где q — суммарное количество запросов.

Задача B. Сбор монет.

В задаче дана лента, разбитая на клетки, по которой ходит игрок. Каждую секунду в каждой клетке дополнительно появляется некоторое число монет, фиксированное для каждой клетки. Игрок за секунду может перейти в соседнюю клетку или остаться в текущей. Каждый раз когда игрок находится в некоторой клетке, он собирает все монеты, которые в ней находятся. Необходимо посчитать, какое максимальное число монет может собрать игрок за t секунд.

Заметим, что для каждой клетки важно знать только последний момент, когда игрок в ней находился. Рассмотрим путь игрока с конца. В каждый момент времени про некоторый непрерывный отрезок клеток уже известен последний момент их посещения, а для остальных клеток нет. Поэтому можно воспользоваться методом динамического программирования, состоянием которого будет отрезок посещенных клеток и текущее время. Кроме того необходимо хранить текущую позицию игрока. Заметим, что можно хранить только те позиции, когда игрок стоит на одном из концов отрезка посещенных клеток. Из каждого состояния существует не более чем два перехода — игрок может посетить клетку слева или справа от уже посещенных. Таким образом, время работы алгоритма составляет O(n²t).

Задача C. Топологическая сортировка и дети.

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

Рассмотрим сначала алгоритм, а потом докажем его корректность. Вершины, для которых дан порядок, будем называть помеченными, остальные — непомеченными. Мы знаем какие числа не использовались в топологической сортировке, будем выставлять их по одному от больших к меньшим в соответствие вершинам. У нас есть очередное нерасставленное число. Первым делом удалим все уже помеченные стоки. Далее для каждого непомеченного стока узнаем максимальное значение в помеченной вершине, достижимой по обратным рёбрам. Для каждой вершины это число можно предподсчитать заранее: находим какую-либо топологическую сортировку графа и решаем задачу динамического программирования. В качестве соответствующей вершины нерасставленному числу выбираем любой сток, у которого предподсчитанное число наибольшее, и удаляем его из графа.

Предподсчёт чисел выполняется за O(V+E). Каждую итерацию нужно выполнять как можно быстрее, поэтому в каждой вершине мы храним количество оставшихся из неё исходящих рёбер. Когда мы удаляем сток, у всех вершин, из которых есть в него ребро, уменьшается исходящая степень, и если эта степень становится нулём, помещаем эту вершину в сет по предподсчитанному значению. Тем самым в нашем сете хранятся все стоки, и для выбора нужного нам достаточно взять самую последнюю вершину из сета. Каждая вершина кладётся в сет и вытаскивается ровно один раз. Итого время работы алгоритма: O(V·log(V) + E).

Теперь докажем корректность нашего алгоритма. Заметим, что нам достаточно доказать правильность первого шага алгоритма, далее используем метод математической индукции. Рассмотрим корректно заполненную топологическую сортировку p, предварительно выкинув все помеченные стоки. Далее рассмотрим сток s, который мы выбрали нашим алгоритмом для максимального числа, и сток, которому оно соответствует в топологической сортировке p. Если мы все числа в перестановке большие p(s) уменьшим на единицу, а выбранному нами стоку s выдадим максимальное число, перестановка останется корректной. Операция произошла корректно: мы сохранили свойство топологической сортировки для непомеченных вершин, а для помеченных вершин значение топологической сортировки не поменялось, так как по свойству выбора вершины s p(s) больше, чем значение топологической сортировки любой помеченной вершины.

Задача D. Правильный сад.

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

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

Сформулированное свойство помогает дойти до решения: для точки (x_i, y_i) обозначим за left_i такой максимальный x < x_i, что в заданном наборе существует точка (x, y_i). В случае, когда это значение не определено, считаем его равным равным минус бесконечности. Аналогичным образом введем величины right_i, down_i и up_i. Рассмотрим область (left_i, right_i) × (down_i, up_i). Если в этой области есть другая точка из заданного набора, то можно найти две точки, для которых построенный прямоугольник нарушает свойство. Стоит заметить, что подходит не любая точка из этой области. В качестве второй точки всегда подходит, к примеру, ближайшая по евклидовому или манхэттенскому расстоянию. Когда в этой области находится только точка (x_i, y_i), все прямоугольники содержат другую точку на стороне, смежной с ней. Таким образом, решение свелось к проверке n прямоугольников на наличие более одной точки внутри.

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

Задача E. Междуречье.

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

Заметим, что поскольку многоугольник выпуклый, а ломаные монотонны и не пересекаются, верен следующий факт: если многоугольник пересекает ломаные i, k, то для любого j, что i ≤ j ≤ k, этот многоугольник пересечет и j-ю ломаную. Используя этот факт, будем решать задачу жадно: найдем максимальное i₁, такое, что существует многоугольник, пересекающий все ломаные с 1-й по i₁-ю, добавим его к ответу, и продолжим: найдем максимальное i₂ такое, что существует многоугольник, покрывающий ломаные с i₁+1-й по i₂-ю, и так далее. Число многоугольников, которые пришлось использовать, и будет ответом.

Научимся для ломаной i_k находить значение i_k+1. Это максимальный индекс, такой, что существует многоугольник, покрывающий i_k+1-ю и i_k+1-ю ломаную. Решим сначала более простую задачу: есть точка A и отрезок BC, нужно проверить, существует ли многоугольник, содержащий внутри себя и данную точку, и какие-то точки отрезка. Для этого построим сумму Минковского этого многоугольника и его самого же, инвертированного относительно (0, 0) (то есть, с противоположными по знаку координатами всех точек). Это какой-то новый многоугольник, назовем его P, с O(n) вершин, содержащий внутри себя точку (0, 0). Сдвинем его так, чтобы точка (0, 0) перешла в точку A, и проверим, что отрезок BC пересекается со сдвинутым многоугольником P — несложно убедиться, что это необходимое и достаточное условие.

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

Пусть k — суммарное число вершин на всех ломаных. Найдём асимптотику используемых нами операций — O(n) на построение многоугольника P, O(n) на построение суммы Минковского P и отрезка ломаной и O(log n) на проверку пересечения выпуклого многоугольника и отрезка. Так как многоугольников нужно построить максимум k, а пересечь в худшем случае нужно каждый многоугольник с каждым отрезком, итоговая асимптотика времени работы равна O(nk + k²log n).

Задача F. Робот на дереве.

В задаче дано неориентированное дерево из n ≤ 10 вершин. Про каждое ребро известна его прочность w_i, которая не превышает 15. По дереву перемещается робот, который изначально находится в случайной вершине. Каждый раз робот равновероятно выбирает ребро из тех, по которым он может пройти, и перемещается по нему. Каждый раз когда робот проходит по ребру, его прочность уменьшается на единицу. Если прочность становится равна нулю, то ребро удаляется. Если у робота нет ребер, по которым он может пойти, он останавливается. Необходимо посчитать математическое ожидание длины пути робота.

Для начала решим более простую задачу. Предположим, что необходимо посчитать не математическое ожидание длины пути, а количество различных путей, по которым мог пройти робот. Представим, что мы зафиксировали вершины, в которых робот начал и закончил свой путь, а также количество раз, которые робот прошел по каждому ребру. Рассмотрим, какие существуют ограничения на эти количества. Во-первых, ребра, по которым робот прошел положительное число раз, должны образовывать связный подграф исходного дерева. Во-вторых, рассмотрим некоторую вершину и количество раз, которые робот прошел по всем ребрам, которые являются смежными с этой вершиной. Если эта вершина является концом пути, то каждое смежное с ней ребро должно использоваться ровно w_i раз. Максимум два ребра смежных с вершиной должны быть использованы нечетное число раз. Причем, если эта вершина лежит на пути из стартовой в конечную, то ровно два ребра должны быть использованы нечетное число раз. Для стартовой и конечной вершины (если они не совпадают) должно быть ровно одно ребро, которое используется нечетное количество раз, либо ноль, если вершины совпадают. Для всех остальных вершин все смежные ребра должны быть использованы четное число раз.

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

Заметим, что для подсчета общего количества путей можно воспользоваться методом динамического программирования. Посчитаем количество путей, которые проходят по некоторому ребру заданное число раз и каким-либо образом проходят по поддереву, которое ограничено этим ребром. При этом считается, что каждый раз, когда путь идет вверх по ребру, он сразу же возвращается назад по нему. Чтобы посчитать значение динамического программирования необходимо зафиксировать количество раз, которые робот прошел по каждому из ребер, которые идут в поддеревья, умножить на уже посчитанные значения для поддеревьев, а также на количество способов расположить переходы в поддеревья. Будем рассматривать поддеревья вершины по очереди и фиксировать количество раз, которые суммарно робот пойдет во все рассмотренные поддеревья. Рассматривая очередное поддерево переберем количество раз, которые робот перейдет в это поддерево. Домножим ответ на значение динамического программирования от поддерева, а также на количество способов расставить переходы в поддерево среди других переходов.

Вернемся к первоначальной задаче. Теперь вместо количества способов будем хранить вероятность выбрать такой путь, а также математическое ожидание его длины. Подсчет вероятности отличается от подсчета количества способов только тем, что при каждом переходе по ребру необходимо поделить значение на количество ребер, которые инцидентны данной вершине. Единственная проблема, которая возникает при этом заключается в том, что степень вершины не является константой, так как ребра удаляются во время путешествия робота. Чтобы посчитать значения динамического программирования для ребра воспользуемся следующей идеей. Зафиксируем все поддеревья, ребра в которые будут удалены, а также общее количество раз, которое робот будет идти из вершины по некоторому ребру. Будем восстанавливать путь с конца. Существует два возможных варианта, которые необходимо различать. Либо робот идет по ребру, которое не будет удалено, тогда нужно уменьшить количество ребер, по которым еще необходимо пойти роботу и перейти к меньшей задаче. Либо робот идет по ребру, которое будет удалено, тогда к общему количеству ребер, по которым роботу необходимо пройти, нужно добавить количество раз, которые он пройдет по данному ребру, а также увеличить количество существующих инцидентных ребер на единицу.

Всего существует O(2^children∑w_i) состояний в динамическом программировании для заданного ребра, и переход между ними осуществляется за O(1). Так как необходимо посчитать значение динамического программирования для каждого количества раз, в которых было использовано ребро, общее время работы алгоритма получается равным O(2ⁿ(∑w_i)²).

Всем привет!

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

В то время как участники будут решать выданные задания, с 11:30 по московскому времени на сайте https://it.mail.ru/rcc в прямом эфире будет транслироваться ток-шоу, посвящённое прошлому, настоящему и будущему программирования и высоких технологий.

Среди гостей такие известные люди как Николай Никифоров — министр связи и массовых коммуникаций РФ, Наталья Касперская — генеральный директор InfoWatch, Сергей Андреев — президент ABBYY, Болтунов Олег — член PostgreSQL Foundation, Алексей Пажитнов — изобретатель игры «Тетрис» и многие другие.

Гости будут обмениваться мнениями по самым разным вопросам, связанным с развитием IT и программирования. В качестве ведущих выступят Антон Комолов и Михаил Мирзаянов, руководитель Центра олимпиадной подготовки программистов Саратовского Государственного Университета.

Трансляция пройдёт 19 сентября с 11.30 до 16.00 московского времени на https://it.mail.ru/rcc

Среди зрителей будут разыгываться призы, так что приглашаем всех присоединиться к трансляции Russian Code Cup, а финалистам желаем удачи!