580A - Кефа и первые шаги

Заметим, что если в массиве есть две пересекающиеся непрерывные неубывающие подпоследовательности, то их можно объединить в одну. Поэтому можно просто проходиться по массиву слева направо. Если текущую подпоследовательность можно продолжить с помощью i-го элемента, то делаем это, иначе начинаем новую. Ответом будет максимальная из всех найденных подпоследовательностей.

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

Решение

580B - Кефа и компания

Сначала отсортируем всех друзей по возрастанию денег. Теперь ответом будет какой-то подотрезок массива. Далее будем использовать метод двух указателей для нахождения требуемого подотрезка.

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

Решение

580C - Кефа и парк

Будем спускаться по дереву от корня, поддерживая дополнительный параметр k — количество встреченных подряд вершин с котами. Если k превысило m, то выходим. Тогда ответ — это количество листьев, до которых мы смогли дойти.

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

Решение

580D - Кефа и блюда

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

Асимптотика — O(2ⁿ * n²).

Решение

580E - Кефа и часы

Для начала посчитаем хэш для всех элементов строки в зависимости от их позиций. То есть хэш цифры k, стоящей на i-й позиции будет равен gⁱ * k, где g — основание хэша. Для всех хэшей построим дерево отрезков сумм, поддерживающее групповую модификацию. Таким образом, запросы на модификацию мы можем выполнять за O(log n). Осталось разобраться с запросами второго типа. Допустим, нужно обработать запрос 2 l r d. Очевидно, что подстрока с l по r будет иметь период d, если подстрока с l + d по r равна подстроке с l по r - d. С помощью дерева сумм мы можем узнать сумму хэшей на подотрезке, а значит можем сравнить две строки за O(log n).

Асимптотика — O(m log n).

Решение