A. Марсианский волейбол

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

Рассмотрим условие победы одной из команд. Необходимо набрать минимум k очков и обогнать проигравшую команду как минимум на 2 очка.

Итоговый ответ max(k, min(x, y) + 2) - max(x, y).

B. Раскраска стены

Чтобы решить данную задачу, поймем сколько минимум цветов нужно, чтобы условия выполнялись. Для этого найдем самый длинный непрерывный отрезок плиток по вертикали или по горизонтали. Пусть длина этого отрезка равна L.

Затем представим квадрат L × L, где первая строка это последовательность чисел от 1 до L, а каждая следующая получается циклическим сдвигом предыдущей на один вправо. Такими квадратами замостим наш исходный прямоугольник, откинув лишнее и не забыв про лампы. Например, если L = 4, замощение будет начинаться так:

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

Если у Маши цветов меньше чем L, то ответа не существует.

C. Магический артефакт

Обозначим как c_i выигрыш во времени, который Максим получает от артефакта на i-м уровне: c_i = a_i - b_i.

Пусть уровни проходятся в порядке 1, 2, ..., n. Если артефакт был найден на i-м уровне, то время прохождения равно сумме значений b_j плюс c₁ + ... + c_i. Тогда математическое ожидание времени прохождения равно:

b₁ + ... + b_n + p₁·c₁ + p₂·(c₁ + c₂) + ... + p_n·(c₁ + ... + c_n).

b₁ + ... + b_n не зависит от порядка уровней, поэтому будем стремиться уменьшить оставшуюся часть суммы. Если раскрыть скобки, можно заметить, что она равна сумме c_i·p_k по всем парам i, k, таким что i ≤ k.

Посмотрим, как изменится сумма, если поменять местами уровни i и i + 1. Среди слагаемых c_i·p_k изменится только c_i·p_i + 1 — оно заменится на c_i + 1·p_i. Если порядок уровней является оптимальным, то c_i·p_i + 1 ≤ c_i + 1·p_i (иначе их можно было бы поменять местами и улучшить ответ). Преобразуем это неравенство:

c_i / p_i ≤ c_i + 1 / p_i + 1.

В оптимальном ответе для всех i от 1 до n - 1 верно это неравенство. Значит, в оптимальном ответе уровни отсортированы по c_i / p_i, и чтобы получить его, нужно их отсортировать. Заметим, что если p_i = 0, можно считать c_i / p_i = ∞.

Сортировать по c_i / p_i нужно осторожно. Если производить деление в числах с плавающей точкой, то в случае, когда c_i = p_i = 0, получится NaN, что приведёт к ошибке. Если сравнивать дроби c_i / p_i и c_k / p_k при помощи компаратора c_i·p_k < c_k·p_i, то в случае, когда c_i = p_i = 0, результат всегда будет false, что тоже приведёт к неправильной сортировке. Поэтому уровни с c_i = p_i = 0 нужно обработать отдельно. Эти уровни могут быть пройдены в любой момент: нетрудно заметить, что они не вносят никакого вклада в ответ, кроме фиксированных слагаемых b_i. Их можно поместить, например, в самый конец.

После сортировки нужно посчитать искомое математическое ожидание. Оно вычисляется по вышеприведённой формуле при помощи префиксных сумм c_i.

D. Менеджер памяти

Для начала для каждого запроса q_i найдем go_i — минимальное j, такое, что среди q_j, q_j + 1, ..., q_i не более k различных чисел — это будет означать, что перед j-м запросом можно так поставить указатели, что j, j + 1, ..., i запросы выполнятся мгновенно. Это делается за O(sum(|q_i|)) например двумя указателями, идя с конца массива запросов.

Теперь будем использовать динамическое программирование, вычислим значения dp_i — минимальная время, за которое можно выполнить первые i запросов. Если go_i = 0, то dp_i = 0. Если нет, то несложно видеть, что dp_i = min_{j = goi..i}(dp_j - 1 + s_j) — мы выбираем, запрос j, перед которым будем менять указатели, и платим соответствующую стоимость. Так как go_i не убывают, посчитать эту величину можно либо поддерживая set значений dp_j - 1 + s_j, либо используя очередь с операцией «минимум».

E. ЛИСА

Рассмотрим сначала задачу для двух конкретных строк: посчитаем число вхождений каждой буквы в первую строку, и количество каждой вхождений буквы во вторую строку, не будем при этом учитывать первую букву в первой строке и последнюю букву во второй строке, которые надо взять в любом случае. Чтобы получить ответ, надо вычислить произведение длин строк и отнять от это го значения сумму cnt1[letter] * cnt2[letter] по всем буквам. Доказательство этого утверждения оставим как упражнение, такая задача предлагалась на северном четвертьфинале 2015 http://neerc.ifmo.ru/archive/2015/northern/north-2015-statements.pdf, задача C. Широкий круг участников мог решать ее на кубке трех четвертьфиналов.

Для n строк задача решается похожим образом — добавим все строки в префиксный бор, добавим все строки в суффиксный бор, посчитаем количествово вершин в первом боре и во втором боре (не считая корня), перемножим эти два числа — столько строк мы можем сгенерить прикладывая путь в префиксном боре к пути в суффиксном боре. Теперь нужно вычесть повторения: это делается аналогично — в префиксном боре считается количество во каждой буквы на ребрах, не считая буквы на ребрах из корня, эти значения перемножаются, и эта сумма вычитается из произведения числа вершин в борах.

Осталось научиться отвечать на запросы на отрезке. Будем использовать sqrt-декомпозицию, разобьем строки в группы по сумме длин. Будем жадно набирать в группу строки, пока суммарная длина в группе не станет больше корня из суммы длин, последняя строка может быть достаточно большой.

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