A. Проблемные обеды

Для нахожения ответа переберем все возможные рестораны, в которых могли пообедать три Кролика. Посчитаем ответ для каждого ресторана. Из всех ответов выберем максимальный. Ответ для ресторана i считается по формуле, описанной в условии. Сложность решения O(N).

Код на С++

Код на Java

B. Девочка и игра

Посчитаем количество букв, которые встречаются в строке s нечетное количество раз. Пусть это количество равно k.

Заметим, что если k = 0, то первый игрок сразу же побеждает — он легко может составить палиндром, поставив одинаковые буквы в разные концы строки (так как общее количество всех букв четное, он сможет это сделать).

В случае k = 1 первый игрок опять-таки сразу же побеждает — сначала он строит палиндром из букв, которые встречаются четное количество раз, а потом вставляет в середину полученной строки те символы, количество вхождений которых в строку s нечетно. Утверждается, при k > 1 задача имеет следующее решение: если k четное – победил второй игрок, иначе победил первый игрок.

Докажем это утверждение. Пусть k = 2. Первый игрок своим ходом может сделать ходы двух типов. Ход первого типа состоит в том, чтобы уменьшить k до 1, удалив одно вхождение буквы, которая встречалась нечетное количество раз. Однако такой ход ведет к поражению, ведь после него второй игрок может составить палиндром.

Ход второго типа состоит в том, чтобы удалить букву, которая встречается четное количество раз, таким образом увеличив k до 3. В таком случае, второй игрок может ответить аналогичным ходом, удалив такую же букву. Так как количество ходов этого типа конечно, то рано или поздно первый игрок вынужден будет сделать ход первого типа, а значит — перейти в проигрышную для себя позицию.

В случае k = 3 первый игрок первым же ходом может уменьшить k до 2, убрав букву, встречающуюся нечетное количество раз. Если второй игрок попробует увеличить k до 3, то первый игрок аналогичным ходом сможет опять уменьшить k до 2. Легко увидеть, что последним в этой цепочке ходов будет ход первого игрока, а значит – он переводит игру в состояние с k = 2, которое является выигрышным для него и проигрышным для его соперника. Аналогичными размышлениями, применяя математическую индукцию, утверждение доказывается для произвольного k.

Получается достаточно простое решение за О(|S|)

Код на С++

Код на Java

C. Девочка и максимальная сумма

Для каждой ячейки массива посчитаем количество запросов, которые ее покрывают. Утверждается, что ячейке, которую покрывает большее количество запросов, нужно ставить в соответствие большее число. Более формально: пусть b — массив, в i-ой ячейке которого записано количество запросов, покрывающих эту ячейку, а – входной массив. Отсортируем эти массивы. Утверждается, что ответ в таком случае равен

Докажем это утверждение. Рассмотрим какие-то индексы i < j, а так же соответсвующие им элементы a[i], a[j] , b[i], b[j] (a[i] ≤ a[j], b[i] ≤ b[j]). Эти элементы вносят в ответ следующую величину: a[i]·b[i] + a[j]·b[j]. Поменяем элементы a[i] и a$[j]$ местами. Теперь эти элементы вносят в ответ величину a[i]·b[j] + a[j]·b[i]. Рассмотрим разницу между полученными значениями:

a[i]·b[j] + a[j]·b[i] - a[i]·b[i] - a[j]·b[j] = b[j]·(a[i] - a[j]) + b[i]·(a[j] - a[i]) = (b[j] - b[i])·(a[i] - a[j]) ≤ 0.

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

Теперь нам нужно быстро научиться считать массив b.

Для этого можно использовать разные структуры данных, поддерживающие модификацию на отрезке (дерево отрезков, декартово дерево и т.д). Однако, существует гораздо более простой метод.

Создадим некоторый массив d. При поступлении запроса l_i, r_i увеличим элементы массива d[l_i] на 1, и уменьшим значение элемента d[r_i + 1] на 1. Таким хитрым образом мы добавляем 1 всем ячейкам от l_i до r_i включительно. После этого необходимо пробежаться по массиву d, накапливая соответствующий результат для b[i].

Теперь, зная массив b, можно легко узнать ответ. Сложность авторского решения — O(NlogN + Q)

Код на С++

Код на Java

D. Девочка и максимальный XOR

Честно говоря, удивлен тем, что с задачей справилось так много участников. Я предполагал решение использующее динамическое программирование, его и опишу.

Для начала, переведем числа L и R в двоичную систему счисления. Теперь заведем такую динамику: d[p][fl1][fr1][fl2][fr2], где p – текущая позиция в двоичной записи чисел a и b (от 0 до количества бит в числе R), fl (от 0 до 1) — переменная, показывающая, что набранное число а строго больше L, fr1 (от 0 до 1) — переменная, показывающая, что набранное число а строго меньше R, fl2, fr2 — переменные, означающие аналогичное значение для числа b.

Напишем динамику в виде рекурсии с запоминанием.

Определим базу рекурсии. Если мы рассмотрели все биты — просто вернем 0.

Определим рекурсивный переход. Узнаем, какой бит может стоять у числа а на позиции p. Мы можем поставить там 0 при одном из двух условий: или у числа L на этой позиции стоит 0, или у числа L на этой позиции стоит 1, а переменная fl1 показывает, что когда-то был выбран бит, который больше соответствующего бита в числе L. Аналогично, мы можем использовать там 1 при одном из двух условий: или у числа R на этой позиции стоит 1, или у числа R на этой позиции стоит 0, а переменная fr1 показывает, что когда-то был выбран бит, который меньше соответствующего бита в числе R. Аналогично, можно узнать, какие биты мы можем ставить в число b. Переберем все возможные варианты расстановки бит, и если результат операции xor в этом бите равен 1, то добавим к ответу для данной расстановки соответствующую степень двойки. Так же необходимо аккуратно пересчитать значения переменных fl1, fr1, fl2, fr2. Среди всех возможных вариантов расстановки надо выбрать максимум.

Запускать рекурсию необходимо от параметров (P,0,0,0,0), где P — количество бит в числе R.

Надеюсь, мой код прояснит все непонятные моменты.

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

Сложность алгоритма O(logR)

Код на С++

Код на Java

Благодря комментариям я узнал еще одно замечательное решение, которое тоже решил включить в разбор.

Отдельно рассмотрим случай, когда L = R. Ответ в таком случае, очевидно, равен 0.

Теперь пускай L ≠ R. Пусть R_i — i-ый бит числа R, L_i — i-ый бит числа L. Пускай p — наибольшее число такое, что R_p ≠ L_p (индексируем p c 0). Рассмотрим произвольное число в отрезке [L;R]. Легко видеть, что биты, старшие чем бит с индексом p у всех этих чисел одинаковы. А значит, как бы мы не выбирали числа a и b, эти биты ничего не внесут в ответ, ведь их xor равен 0.

Теперь давайте построим числа a и b таким образом:

1) Число a — биты, старшие чем бит с индексом p совпадают с битами числа L, p-ый бит равен 0, остальные биты равны 1.

2) Число b — биты, старшие чем бит с индексом p совпадают с битами числа L, p-ый бит равен 1, остальные биты равны 0.

Легко увидеть, что оба эти числа лежат в промежутке [L;R], а также что их xor превращает в 1 все двоичные розряды, не старшие чем p-ый, то есть ответ при таком выборе максимизируется, и равен 2^p + 1 - 1

Сложность алгоритма O(logR)

Решение на Java от AlexanderBolshakov

Если подбирать значение p бинарным поиском, то можно улучшить время работы алгоритма до O(log(logR)), однако на контесте этого делать, естественно, не требовалось.

E. Девочка и задача про дерево

Заметим, что наше дерево – это совокупность некоторых цепочек, начинающихся в корне.

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

Теперь вспомним задачу С. Там для модификации на отрезке мы использовали массив d, в котором обрабатывали все запросы. Узнавать значения b[i] в той задаче нужно было после поступления всех запросов. Здесь же запросы изменения и запросы на вывод значения, записанного в вершине, выполняются в некотором смысле онлайн. Именно поэтому стоит использовать дерево Фенвика — оно позволяет за cложность O(logN) изменять элемент, и за такую же сложность находить сумму на некотором отрезке. Научимся с помощью дерева Фенвика обрабатывать запросы на добавление на отрезке массива, а так же на нахождение элемента массива. Как уже говорилось, наше дерево умеет выполнять два типа операций:

add(x, y) — добавляет элементу с индексом x значение y

find(x) – находит значение суммы на отрезке от 1 до x

Предположим что поступил запрос на добавление на отрезке l до r значения val.

Тогда просто выполним операции add(l, val) и add(r + 1,  - val).

Пусть поступил запрос на нахождения значения элемента с индексом v.

Тогда выполним операцию find(v).

Теперь мы можем вернуться к изначальной задаче.

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

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

Сложность полученного алгоритма — O(N + QlogN)

Код на C++

Код на Java

На этом все. Вопросы в комментариях очень приветсвуются.