485A - Фабрика

Производство остановится только в том случае, если существует такое целое K ≥ 0, что a·2^K делится на m. Из этого следует, что K может быть максимум порядка log₂(m). Так как K — это по сути сколько пройдёт дней до этого момента, то можно промоделировать описанные в условии задачи действия, например, в течение 20-ти дней (не забыв при этом про 64-битный тип данных). Если в какой-то момент производство остановилось, то ответ "Yes". Если не остановилось в течение этих дней, то оно не остановится никогда, а значит ответ "No".

485B - Ценные ресурсы

Найдём минимальную длину, необходимую чтобы покрыть все точки по оси Ox — это будет в точности Maximum(x_i) - Minumum(x_i). Аналогично и для оси Oy — это Maximum(y_i) - Minumum(y_i). Так как нам необходим квадрат, то следует взять максимальную из этих двух величин в качестве длины его стороны.

484A - Биты

Опишем функцию f(L, R), которая будет ответом на задачу. Она ведёт себя следующим образом:

• если L = R, то f(L, R) = L;

• иначе, если 2^b ≤ L, где b — максимальное целое число такое, что 2^b ≤ R, то f(L, R) = f(L - 2^b, R - 2^b) + 2^b;

• иначе, если 2^b + 1 - 1 ≤ R, то f(L, R) = 2^b + 1 - 1;

• иначе f(L, R) = 2^b - 1.

Итоговая сложность — O(logR) на один запрос.

484B - Максимальное значение

Переберём все различные числа a_j исходной последовательности. Так как нужно максимизировать , то переберём в цикле по x все числа, кратные a_j в диапазоне от 2a_j до M, где M — удвоенное максимальное значение элемента последовательности. Для каждого такого числа нужно найти максимальное a_i, такое, что a_i < x. Ограничения на числа позволяют сделать это за O(1) при помощи массива. Обновим ответ величиной . Так как перебираются только различные a_j, то итоговая сложность составит O(nlogn + MlogM).

484C - Странная сортировка

Заметим, что d-сортировка не зависит от того, какие символы находятся в строке, а значит является перестановкой (назовём её P). Посмотрим на операцию перемешивания по другому: вместо того, чтобы переходить к очередной следующей подстроке и сортировать её, сделаем циклический сдвиг всей строки на один символ влево. Таким образом, сортироваться будет только префикс строки, а строка сдвигаться. Осталось понять, что сдвиг влево — это тоже перестановка (назовём её C). Теперь всё просто, к строке нужно поочерёдно применять перестановки P и C, то есть нужно получить S·P·C·P·C... = S·(P·C)^{n - k + 1}. После этого строку нужно сдвинуть ещё на k - 1 символ влево, чтобы получить то, что получится после операции перемешивания. Здесь используется умножение перестановок, а оно в свою очередь ассоциативно, а значит для вычисления (P·C)^{n - k + 1} можно воспользоваться бинарным алгоритмом. Итоговая сложность составит O(nmlogn).

484D - Детский сад

Заметим, что существует оптимальный ответ такой, что любой отрезок, который образует группу, содержит свои максимальные и минимальные значения на границах. Иначе было бы выгодно разбить отрезок хотябы на два. Так же можно заметить, что каждый отрезок будет строго монотонным (элементы на нём строго возрастают или убывают). Выделим интересные точки в последовательности — это либо локальные максимумы (то есть a_i - 1 < a_i > a_i + 1), либо минимумы (a_i - 1 > a_i < a_i + 1), либо соседние с ними точки. Будем решать задачу методом динамического программирования, D_i — наилучший ответ для префикса i. Тогда при вычислении очередного значения необходимо обработать не более трёх предыдущих интересных точек, а так же предыдущую точку. Итоговая сложность — O(n).

484E - Объявление на заборе

Заметим, что при поиске ответа на конкретный запрос можно воспользоваться бинарным поиском по ответу. Пусть в какой-то момент зафиксировалась высота h и необходимо узнать, помещается ли прямоугольник размера w на h в участок забора с l-ой по r-ой доски включительно. Заведём перед обработкой запросов структуру данных, которая поможет отвечать на такой вопрос. Это будет персистентное дерево отрезков с необычной функцией: максимальное количество подряд идущих единиц на отрезке (далее maxOnes). В листьях дерева будут только числа 0 и 1. Чтобы реализовать такую функцию, необходимо ввести ещё некоторые величины, а именно:

len — длина отрезка в вершине дерева отрезков, prefOnes — длина префикса, полностью состоящего из единиц, sufOnes — длина суффикса, полностью состоящего из единиц.

Вычисляются эти функции следующим образом:

maxOnes, требуемая функция, равна max(maxOnes(Left), maxOnes(Right), sufOnes(Left) + prefOnes(Right));

prefOnes равна prefOnes(Right) + len(Left) в случае, если len(Left) = prefOnes(Left), иначе она равна prefOnes(Left);

sufOnes равна sufOnes(Left) + len(Right) в случае, если len(Right) = sufOnes(Right), иначе она равна sufOnes(Right);

len = len(left) + len(Right);

Left и Right — соответственно левый и правые сыновья текущей вершины в структуре дерева отрезков.

Как уже упоминалось выше, дерево должно быть персистентным (то есть хранить все свои версии после изменений), строиться оно должно следующим образом. Сначала строится пустое дерево — из одних нулей. Далее в позицию, где в заборе находится самая высокая доска, ставится единица. Тоже самое делается для второй по убыванию высоты доски и так далее. Например, если забор описывался последовательностью [2, 5, 5, 1, 3], то изменения последнего слоя дерева будут следующими:

[0, 0, 0, 0, 0] -> [0, 1, 0, 0, 0] -> [0, 1, 1, 0, 0] -> [0, 1, 1, 0, 1] -> [1, 1, 1, 0, 1] -> [1, 1, 1, 1, 1].

При этом для каждой высоты h_i нужно запомнить соответствующую версию дерева, назовём её как tree_height. Теперь, чтобы ответить на вопрос выше, нужно сделать запрос на отрезке [l, r] у дерева tree_h. Если maxOnes этого запроса меньше w, то прямоугольник невозможно разместить, иначе возможно.

Построение дерева займёт O(nlogn) времени и памяти. Ответ на запрос займёт O(log²n) времени.