Автор andrewzta, история, 11 дней назад, По-русски,

Всем привет!

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

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

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

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

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

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

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

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +196
  • Проголосовать: не нравится  

Автор RussianCodeCup, история, 13 дней назад, По-русски,

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

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

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

Очевидно, что чётность вхождения простых чисел в произведение ab не меняется во всех операциях. Тогда давайте оставим все простые в первой степени. Остались числа p1, p2, ..., pn. Давайте назовём произведение всех этих простых чисел d, d ≤ ab. Утверждается, что этих простых не может быть больше 14. Если 1 ≤ a, b ≤ 109, то произведение ab ≤ 1018, а произведение первых 15 простых чисел превышает 1018) Теперь заметим, что конечный ответ — пара чисел (x, y) таких, что xy = d. Из этого следует, что второй элемент пары определяется однозначно по первому. Переберём всевозможные делители d за число x за O(2n), и выберем наилучшую пару.

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 — клетку (xi, yi). За линию сгиба возьмем вертикальную прямую x = xi, касающуюся этой клетки. Теперь слева нужно восстановить k - n клеток первоначальной фигуры, чтобы после складывания левой части вдоль линии сгиба на правую получилась данная во входных данных сложенная фигура. Так как k - n ≤ n (иначе после сгиба получилось бы больше n клеток), достаточно выделить из сложенной фигуры k - n клеток, образующих связную фигуру, содержащую клетку (xi, yi). Это можно сделать простым обходом в глубину.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3) Найдя две лексикографически минимальные подпоследовательности SA и SB, их надо объединить в одну лексикографически минимальную длиной k. Будем двигаться по подпоследовательностям двумя указателями p1 и p2. Если SAp1 ≠ SBp2, то двигаем указатель, стоящий на меньшем числе. Если SAp1 = SBp2, двоичным поиском найдем наибольший общий префикс SA[p1..|SA|] и SB[p2..|SB|] и сравним следующие числа. Для сравнения подотрезков SA и SB можно использовать хеши.

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

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

Решение за O(k2):

Будем называть массив 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. Их можно разбить на классы эквивалентности. Каждой вершине поставим в соответствие ck[v] — метку класса эквивалентности, которому принадлежит её k-поддерево.

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

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

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

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

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

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

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

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

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +26
  • Проголосовать: не нравится  

Автор RussianCodeCup, история, 2 недели назад, По-русски,

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

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

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +84
  • Проголосовать: не нравится  

Автор RussianCodeCup, история, 4 недели назад, По-русски,

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

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

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

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

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

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

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

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(n2·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. Красивый отчёт

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

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

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

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

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

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

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

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +36
  • Проголосовать: не нравится  

Автор RussianCodeCup, история, 4 недели назад, По-русски,

Всем привет!

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

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

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +56
  • Проголосовать: не нравится  

Автор RussianCodeCup, история, 6 недель назад, По-русски,

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], такого, что prefL - 1 = prefR, где prefi = a1 + a2 + ... + ai — префиксная сумма массива a (pref0 = 0). Далее будем считать, что мы работаем с массивом pref0, pref1, ..., prefn, и по запросу [l, r] требуется найти максимальный по длине подотрезок [L, R] отрезка [l - 1, r], такой, что prefL = prefR.

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

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

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

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

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +34
  • Проголосовать: не нравится  

Автор RussianCodeCup, 6 недель назад, По-русски,

Всем привет!

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

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

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +41
  • Проголосовать: не нравится  

Автор RussianCodeCup, история, 2 месяца назад, По-русски,

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

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

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

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

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

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

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

1 2 3 4 1 2 3 4 1 2

2 3 4 1 2 3 4 1 2 3

3 4 1 2 3 4 1 2 3 4

...

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

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

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

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

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

b1 + ... + bn + p1·c1 + p2·(c1 + c2) + ... + pn·(c1 + ... + cn).

b1 + ... + bn не зависит от порядка уровней, поэтому будем стремиться уменьшить оставшуюся часть суммы. Если раскрыть скобки, можно заметить, что она равна сумме ci·pk по всем парам i, k, таким что i ≤ k.

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

ci / pi ≤ ci + 1 / pi + 1.

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

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

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

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

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

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

E. ЛИСА

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

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

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

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

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +33
  • Проголосовать: не нравится  

Автор RussianCodeCup, 2 месяца назад, По-русски,

Всем привет!

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

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

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

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

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +118
  • Проголосовать: не нравится  

Автор RussianCodeCup, 2 месяца назад, По-русски,

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

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

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

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

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

A. Космический корабль

Заметим, что если сила босса равна x, то сумма сил всех врагов равна 2x. Следовательно, чтобы найти силу босса, необходимо посчитать суммарную силу всех врагов и разделить ее на 2. После этого необходимо найти какого-нибудь врага с такой силой и поменять это значение в массиве f со значением последнего врага.

B. Рейнджеры в автобусе

Будем обрабатывать пассажиров по очереди и для каждого определять, кем он мог бы быть. Сразу заметим, что Розовый Рейнджер может есть куда угодно, поэтому каждый пассажир мог бы быть Розовым.

Для каждого места будем помнить, свободно ли оно. Для этого заведем unordered_set, в котором будем хранить занятые места. Проверим, мог бы очередной пассажир быть Красным Рейнджером. Для этого найдём место, на которое сел бы Красный. Переберём циклом ряд от 1 до n, если попался ряд, в котором есть свободное место, выбираем левое, если оно свободно, или правое, если нет — это и есть место, куда сел бы Красный. Поскольку он выбирает место однозначно, мы можем определить, мог бы этот пассажир быть Красным — нужно проверить, что он сел именно на это место. Таким же образом узнаем, куда сели бы Синий, Жёлтый и Чёрный – разница будет в порядке перебора рядов (от 1 до n или наоборот) и в порядке выбора места в ряду (сначала левое или правое). После обработки пассажира отметим его место как занятое.

Решение работает за O(nk) и использует O(k) памяти.

Чтобы улучшить решение, заметим, что каждый из циклов останавливается, когда находит ряд, в котором есть свободное место. Это означает, что нужно быстро находить первый и последний незанятые ряды. Будем поддерживать эти значения — first и last. Изначально first = 1, last = n. После каждой итерации цикла обновим эти значения. Будем увеличивать first на 1, пока ряд first занят, затем уменьшать last на 1, пока ряд last занят. Занятых рядов не может оказаться больше k / 2, поэтому first и last сделают O(k) шагов. Таким образом, улучшенное решение работает за O(k) и проходит все тесты.

C. Волшебное оружие

Предпочитаем массивы: R[a][b] — количество фрагментов у красного рейнджера, у которых первая цифра равна a, а последняя равна b; G[a] — количество фрагментов у зеленого рейнджера, у которых последняя цифра равна a; и B[b] — количество фрагментов у синего рейндждера, у которых первая цифра равна b.

Если бы у разных рейнджеров не было одинаковых моделей фрагментов, ответ был бы равен сумме по всем a и b значений G[aR[a][bB[b].

Чтобы учесть ситуацию, когда у какой-то пары совпадают модели, посчитаем количество пар фрагментов с одинаковым номером модели у красного и синего, красного и зеленого и синего и зеленого рейнджеров, соответственно (например, с помощью std::map). Заметим, что подходящими являются только номера, у которых первая и последняя цифра совпадает. Воспользуемся формулой включения-исключения, вычтем из ответа число таких пар, и добавим удвоенное количество троек фрагментов, когда у всех трех рейнджеров совпадают модели.

D. Рыцари и лжецы

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

Пусть dp[i][mask_prev][mask_cur] — максимальное количество рыцарей, которые могут быть в расстановке из первых i столбцов, mask_cur — маска i-го столбца, а mask_prev — (i - 1)-го.

Затем переберем маску для (i + 1)-го столбца и проверим выполняются ли ограничения на соседей, для солдат из i-го столбца, так как теперь известны все их соседи.

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

База: dp[2][mask_prev][mask_cur] равно количеству единиц в mask_prev и mask_cur, если mask_prev может стоять слева от mask_cur.

Переход: dp[i + 1][mask_cur][mask_next] = dp[i][mask_prev][mask_cur] + ones(mask_next), где ones(x) — количество единиц в маске x.

Ответ будет максимумом среди всех dp[k][mask_prev][mask_cur], таких что mask_cur может находится справа от mask_prev.

Наконец заметим, что случай k = 1 стоит разобрать отдельно, поскольку в этом случае нет предыдущего столбца.

E. Параллелепипед

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

Пусть теперь все три стороны различны. Построим следующий неориентированный граф: вершинами будут возможные длины сторон, соединим ребром числа a и b, если имеется хотя бы два листа размером a × b. Задача свелась к рассмотрению треугольников в получившемся графе, это можно сделать за O(n2 / w) или O(nsqrt(n)) (здесь w обозначет размер машинного слва, 32 или 64, этот множитель возникает при битовом сжатии в поиске треугольников).

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +23
  • Проголосовать: не нравится  

Автор RussianCodeCup, 2 месяца назад, По-русски,

Всем привет!

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

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

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

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

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

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

Полный текст »

 
 
 
 
  • Проголосовать: нравится  
  • +87
  • Проголосовать: не нравится