501A - Контест

В этой задаче требовалось сделать то, что написано в условии. Считать числа и определить у кого из ребят больше баллов.

Асимптотика: O(1).

501B - Миша и смена хэндлов

Для начала немного переформулируем задачу. Был дан ориентированный граф, вершинами которого являются хэндлы пользователей, а ребрами запросы изменения хэндлов. Он состоит из некоторого количества цепочек, нужно было найти их количество, начальные и конечные вершины каждой цепочки. То есть у каждой вершины входящая и исходящая степень не превосходит 1. Ввиду последнего ограничения, ребра этого графа можно хранить в словаре(в C++ — std::map\unoredered_map, Java — TreeMap\HashMap), где ключом является вершина из которой исходит ребро, а значением — вершина, в которую оно входит.

Каждому уникальному пользователю соответствует вершина с нулевой входящей степенью. Из всех таких вершин нужно переходить по ребру, до тех пор, пока существует переход. Чтобы найти вершины с нулевой степенью, запомним вершины в которые входит ребро, и добавим их в множество(в C++ — std::set\unoredered_set, Java — TreeSet\HashSet).

Асимптотика: .

504A - Миша и лес

Заметим, что у непустого леса найдется вершина со степенью 1(такая вершина называется листом). Будем удалять ребра графа по очереди и поддерживать актуальные значения (degree_v, s_v), до тех пор пока он не станет пустым. Для этого будем поддерживать очередь(или стек) вершин являющихся листьями. На очередной итерации мы достаем вершину v из очереди, и удаляем ребро (v, s_v), для этого делаем degree_sv -= 1 и s_sv ^= v. Если у вершины s_v степень стала равной 1, то добавим ее в очередь.

Необходимо обработать случай, когда мы достаем вершину v из очереди и у нее degree_v = 0, тогда стоит проигнорировать это, так как мы уже удалили нужное ребро.

Асимптотика: O(n)

504B - Миша и сложение перестановок

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

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

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

В итоге получаем, что нам необходимо получить индексы перестановок, сложить их в факториальной системе счисления по модулю n!, и провести обратное преобразование. Для лучшего понимания ознакомьтесь с wiki и/или любым прошедшим решением.

Асимптотика: или .

504C - Миша и палиндромность

Заметим, что если количество элементов, встречающихся нечетное число раз, больше одного — ответ равен нулю. Аналогично, если массив изначально является палиндромом — ответ .

Будем обрезать с обоих концов палиндрома одинаковые символы, пока это возможно. Пусть при этом мы получили массив b длины m, его первый и последний элементы различны. Нужные нам отрезки [l, r] содержат какой-то префикс или суффикс массива b.

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

Асимптотика O(n) или .

504D - Миша и XOR

Переведем каждое число в двоичную систему счисления, для одного числа это делается MAXBITS² c малой константой, если хранить число в системе счисления с основанием 10⁹ или 10¹⁸. MAXBITS ≤ 2000.

Для решения задачи нам потребуется небольшая модификация алгоритма Гаусса. Будем обрабатывать запросы по одному, проделывать итерацию алгоритма Гаусса, и поддерживать следующую информацию, для бита с индексом i хранить индекс p[i] запроса, или  - 1, если такого запроса нет, у которого этот бит является младшим выставленным после его(запроса) нормировки. Нормировкой я называю, процесс, в котором число приводится к такому виду, что его индекс наименьшего выставленного бита максимален. При нормировке мы можем XOR-ить число с любыми другими числами из запросов с индексами меньше текущего. Также нам понадобится информация о том, с числами из каких запросов мы проXOR-или текущее число чтобы его отнормировать, будем хранить это в битсете x[j], где j-индекс запроса.

Итак, обрабатывая очередной запрос v, мы пробегаем по его битам от младшего к старшему. В случае если текущий бит i выставлен, мы пытаемся обнулить его. Если p[i] =  - 1, то обнулить этот бит нельзя и мы заканчиваем обработку этого запроса, иначе XOR-им текущее число с отнормированным числом из запроса p[i], а так же XOR-им x[v] с x[p[i]]. Если после обработки запросов нам удалось обнулить число, тогда ответ на запрос — да, и в битсете x[v] содержится множество индексов являющееся ответом, иначе — нет.

Асимптотика решения O(m × MAXBITS × (MAXBITS + m)) с малой константой, засчет битового сжатия.

504E - Миша и LCP на дереве

Построим heavy - light декомпозицию дерева и запишем все строки соответствующие heavy-путям идущим вверх и вниз в одну строку T.

Обрабатывая очередной запрос разобьем пути (a, b) и (c, d) на части, целиком принадлежащие heavy-путям. Таких частей будет . Заметим, что каждой части пути соответствует некоторая подстрока T.

Теперь для ответа на запрос нам необходимо находить наибольший общий префикс двух подстрок в строке. Это можно сделать, найдя суффиксный массив строки T, массив lcp и построить sparsetable на минимумы на нем.

Асимтотика:

Для лучшего понимания ознакомьтесь с моим решением.

P.S. Вместо суффиксного массива можно использовать хэши, сохраняя асимптотику.

P.P.S. Решения, использующие двоичный подъем и хэши, отсекались по времени большими тестами.

Привет, Codeforces!

12 января в 12.00 MSK пройдет очередной 285-й раунд Codeforces. Автором задач являюсь я(Савинов Евгений). Это мой первый раунд на Codeforces и, надеюсь, не последний.

Хочу поблагодарить Сергея Кияна(sokian) и Александра Голованова(Golovanov399) за помощь в подготовке и прорешивании задач, Макса Ахмедова(Zlobober) за неоценимую помощь в подготовке контеста, Алекса Фетисова(AlexFetisov) за прорешивание раунда, Марию Белову(Delinur) за перевод условий на английский язык и, конечно же, Михаила Мирзаянова(MikeMirzayanov) за замечательные системы Codeforces и Polygon.

Кстати, сегодня(11 января) у Михаила Расиховича день рождения, давайте поздравим его с этим!

Раунд состоится в обоих дивизионах. Информация о разбалловке будет опубликована перед началом раунда.

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

UPD2: Разбор задач можно найти здесь.

Предлагаю здесь обсудить задачи прошедшего Гран-При.

Интересно узнать решение задачи K.

Предлагаю здесь обсудить задачи прошедшего Гран-При.

Интересно, как решать I? Мы дошли до того что, эта операция это умножение на простенькую матрицу в кольце по модулю 2. Но непонятно какой у нее период.

итак, есть задача: дан двумерный массив размерами до 5000, требуется отвечать на запросы вида (i, j, r), ответом будет сумма/минимум/максимум элементов массива с индексами x, y, таких что (x - i)² + (y - j)² ≤ r². Интересуют идеи как онлайн, так и оффлайн решения задачи. Решения за O(r) на запрос не предлагать, ибо слишком скучно.

зы. Источника задачи нет, т.к. возникла у меня в голове:-)

Наверное, многие встречались с задачей:

Даны n(n - 1) / 2 попарных сумм чисел множества из n элементов, найти элементы этого множества или определить, что решения не существует. Но неизвестно к каким парам элементов относятся соответствующие суммы. У этой задачи есть стандартное решение: упорядочим исходные числа и переберем первое(т.е минимальное) число, затем раз за разом будем определять очередное число. Есть ощущение, что возможно(или невозможно :) ) делать это с помощью потока, прав ли я? а если нет, то почему?

Давайте обсуждать задачи здесь.
Корректный ли был тест номер 6 в задаче G?
ADD: И как решать B?
ADD: ссылка на условия

Пытаюсь решить эту задачу, над жадностями не думал. Но попытался переформулировать так, как написано в топике. Можно ли ее(сформулированную задачу) вообще решить, и, если да, то как? И как можно решить исходную задачу?

Привет всем! Дальше я постараюсь объяснить решение задачи E Codeforces Round #132.

Давайте научимся решать немного другую задачу и будем искать число периодических чисел в полуинтервале (2^k, x], где . Тогда видно, что x имеет длину len = k + 1.

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

Теперь посчитаем число таких блоков g[i], которые имеют длину i, i делитель len. Возьмем старшие i бит числа x и назовем соответствующее число t = x >> (len - i), например если взять x = 10011000₂, а i = 4, то тогда t = 1001₂, а если i = 2, то t = 10₂. Первым делом, проверим подходит ли этот блок t, это можно сделать, например, посчитав p = ttttt..., где t повторяется раз, p можно посчитать в цикле p = (p << i) + t. Понятно, что если p ≤ x, то посчитаем этот блок и сделаем g[i] = 1, иначе g[i] = 0. Все подходящие блоки должны быть меньше или равны t, и первая цифра у них обязательно 1, так как не может быть лидирующих нулей. Случай равенства мы уже учли, тогда осталось добавить к g[i] разницу между t и 2^i - 1 = 10000...₂, где i-1 нулей, g[i] = g[i] + t - (1 << (i - 1)). Может показаться, что все уже готово и можем сложить все g[i], где i делитель len, и не равно len, но нельзя. Покажем, что таким образом мы учли некоторые случаи по нескольку раз, например для x = 10101100₂, i = 4, g[4] = 1 + (1010₂ - 1000₂) = 3, мы посчитали блоки 1000, 1001, 1010, и если взять i = 2,g[2] = 1 + (10₂ - 10₂) = 1, мы учтем 10, но 1010 получается из 10 повторением два раза. Но эта проблема очень легко решается, для этого необходимо вычесть из g[i] все g[j], где j < i и j делитель i.

То есть мы считаем, своего рода, динамику.g[i] начиная с i = 1 до самого большого делителя len не равного len, и обновляем значения, вычитая соответствующие g[j].

Теперь мы научились считать количество таких чисел на полуинтервале (2^k, x], перебирая все делители len и считая динамику g[i], и потом возвращаем сумму g[i], по всем делителям i < len . Заметим, что степень двойки не может быть периодическим числом. Теперь мы можем посчитать аналогичную величину для x = 2^k - 1, дальше для 2^k - 1 - 1 и так далее, пока не станет x = 1, теперь на этих непересекающихся полуинтервалах посчитаем сумму и вернем ответ. Это можно реализовать рекурсией. Вот мой код на C++, я дополнительно предпосчитал все делители для чисел до 60. Спасибо за внимание, надеюсь вам все понятно, а если не понятно задавайте вопросы)

UPD: Еще один код, который немного асимптотически быстрее.

Приветствую всех! На днях я решал задачу, в которой требовалось определить, представимо ли число N < 10¹⁵ в виде суммы двух квадратов. И у меня возникли проблемы с этим, банальный перебор за корень давал TL. Так же пробовал разложить на простые сомножители за тот же корень, и потом проверял четность степеней у простых делителей вида 4k + 3, опять же TL. Скорее всего задача сдается за корень, и мне интересно именно техническая реализация этого, т.е. как конкретно писать аккуратный перебор или факторизацию за корень, и в чем конкретно проявляется эта аккуратность. Если что, эта задача с тимуса link HERE Заранее благодарен!