467A - George and Accommodation

В этой задаче нужно было просто посчитать количество пар, у которых q_i - p_i ≤ 2

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

467B - Fedor and New Game

В этой задаче нужно было уметь считать количество различных битов в двух числах. Как вариант, можно просто побежать по битам и посчитать количество различных. Ещё, как вариант, если исходные два числа X и Y, то количество различных битов равнялось бы количеству единиц в числе X xor Y, где xor — операция исключающего или.

Асимптотика O(M·N)

467C - George and Job

Решение этой задачи — динамическое программирование. Изначально нужно посчитать psum_R, где psum_R — сумма на префиксе массива p длиной R.

Обозначим dp_i, j — максимальная прибыль которую может получить Юра, если мы уже выбрали i последовательностей и последний элемент в i-ой последовательности имеет индекс j.

Очевидно, что если i·m > j, то dp_i, j = 0. Иначе dp_i, j = max(dp_{i, j - 1}, dp_{i - 1, j - m} + psum_j - psum_j - m) Ответом будет dp_k, n.

Ещё нужно было не забыть использовать long long при вычислениях.

Асимптотика: O(N·K)

467D - Fedor and Essay

Первое, что нужно сделать, чтобы облегчить себе работу — перевести все строки в нижний регистр. Затем словам дать номера. Различным словам дать различные номера, а одинаковым — одинаковые.

Затем, из всех строк нужно построить граф. Пусть каждое слово — просто вершина. А пара слов синонимов X и Y — ребро между вершинами, которые отвечают за данные слова. Ребра ориентированные. Также, для каждого слова мы должны хранить его длину и количество букв «R». Будем использовать номера, данные словам, для построения графа.

После создания графа, у нас мог быть петли, кратные ребра, циклы. Поэтому нужно сжать все сильно связные компоненты в одну вершину. После чего задача состоит в том, чтобы посчитать dp_ver — пара, отвечающая за минимальное количество букв «R» и минимальную длину слова с минимальным количеством букв «R», которым можно заменить слово, за которое отвечает вершина ver.

Пересчет очевиден — dp_ver = max(dp_nextVev, dp_ver), где nextVer — все вершины, в которые можно пойти из ver. Максимум из двух пар берется как у pair в C++.

Затем нужно пройти по всем словам текста, получить номер вершины, который соответствует нужному слову. Пусть это ver. Тогда к ответу нужно прибавить dp_ver.

Также, важно было не забыть использовать long long при вычислениях.

Асимптотика: , где w — множество всех слов, которые есть в тексте и в словаре.

467E - Alex and Complicated Task

Данная задача решалась жадно.

Алгоритм решения такой:

Набираем числа из массива a по очереди, пока в последовательности набранных чисел(далее G) не найдется нужная нам четверка. Напоминаю, что нужная четверка чисел имеет вид: [c₁, c₂, c₃, c₄] = [x, y, x, y]. Если набрали такую четверку чисел, то добавляем в ответ. Очищаем G и v (далее будет описано, что такое v).

Очевидно, что этот алгоритм оптимален.

Для удобности сжимаем числа в массиве a. То есть каждому числу присваиваем его порядковый номер в отсортированном списке всех уникальных чисел из массива a. Это делается, потому что в дальнейшем нам удобнее использовать числа порядка O(N). Теперь как быстро узнать, что в G найдется нужная нам четверка.

Давайте для каждого уникального числа X хранить список его позиций в G. Назовем этот список v_X. Теперь просто можно обработать операцию добавления числа в G. Пусть добавляемое число — это X. Добавим число X в список G. Пусть i — позиция добавленного числа в список G.

Теперь давайте добавим позицию i в список v_X.

Можно заметить такой факт:

Если размер списка v_x равен 4, то мы нашли нужную нам четверку.

Можно заметить ещё один факт:

Если до добавления мы не нашли нужную четверку чисел, а после добавления нашли, то последнее добавленное число является последним в четверке. То есть наше последнее добавленное число равно c₄. Значит мы знаем позицию последнего числа из четверки. Давайте переберем позицию числа c₂. Всего возможных позиций числа c₂ не больше двух, так как всего позиций, на которых стоит число c₂, не больше трех (смотреть предыдущий факт). Одна позиция уже занята числом c₄. Итого остается максимум две позиции. Пусть мы проверяем, то что c₂ имеет позицию L, а c₄ имеет позицию R. Остается только проверить существование таких c₁ и c₃, что c₁ = c₃ и их позиции P и Q соответственно. P и Q должны удовлетворять следующим условиям: 1 < P < L, L < Q < R. Это очень легко проверить. Давайте заведем массив T. T_i =  максимальное j, что G_i = G_j. Поддерживать такой массив не составляет труда. Теперь проверка будет требовать только одного запроса: Максимум на отрезке [1, L - 1] в массиве T. Пусть результат запроса равен Z. Если он удовлетворяет условию L < Z < R, то четверка существует. Этим запросом мы нашли позицию числа c₃ в списке G. По этим данным мы можем восстановить четверку.

Чтобы найти максимум на отрезке за , можно воспользоваться деревом отрезков или деревом Фенвика.

Итоговая асимптотика: .