436A - Feed with Candy
Автор разбора: Fefer_Ivan
В задача А типы съеденных конфет должны все время менятся. Так что первая съеденная конфета определяет тип всех последующих конфет. Возможных типа всего два, так что переберем тип первой съеденной конфеты. Пусть в какой-то момент времени Ом Ном должен съесть конфету типа t и может прыгать на высоту h. Очевидно, что наиболее выгодным решением будет съесть конфету с наибольшей массой среди всех конфет, которые Ом Ном может съесть на текущем этапе. Для решения задачи необходимо промоделировать процесс поедания конфет для начального h = x и t = [0, 1] и выбрать лучшее значение.
436B - Om Nom and Spiders
Автор разбора: Fefer_Ivan
Пронумеруем столбцы таблицы начиная с 0 слева направа, а строки начиная с 0 сверху вниз. Теперь заметим, что в момент времени t > 0 в клетке (x, y) могут находиться только 4 паука:
- Паук, который движется влево и в начале был в клетке (x, y + t).
- Паук, который движется вправо и в начале был в клетке (x, y - t).
- Паук, который движется вниз и в начале был в клетке (x - t, y).
- Паук, который движется вверх и в начале был в клетке (x + t, y).
Давайте переберем столбец в котором Ом Ном начнет свой путь. Пусть это столбец y. В момент времени 0 все пауки стоят на своих исходных позициях, а Ом Ном стоит в клетке (0, y). Так как на нулевой строке нет пауков, то в момент времени 0 Ом Ном их точно не встречает. Когда Ом Ном находится в клетке (x, y), это значит, что с момента начала движения прошло x единиц времени. Следовательно, для того, чтобы вычислить сколько пауков Ом Ном встретим в этой клетке, необходимо проверить лишь 4 клетки, указанные выше, на наличие паука, движущегося в нужном направлении.
436C - Dungeons and Candies
Автор разбора: Fefer_Ivan
Давайте рассмотрим неориентированный взвешенный граф, в котором k + 1 вершина. Пронумеруем вершины целыми числами от 0 до k. Вершины c 1 по k будут соответствовать уровни. Для каждой пары уровней i и j добавим ребро из i в j стоимость которого равно стоимости передачи одного уровня как разность с другим. Так же для каждого уровня i добавим ребро между вершиной 0 и i стоимости n·m, т.е. стоимости передачи уровня целиком. Каждый способ передать все уровни соответсвует остовному дереву в указанном графе. Таким обзаром необходимо вывести минимальное остовное дерево в этом графе.
436D - Pudding Monsters
Автор разбора: Fefer_Ivan
Задача решается при помощи динамического программирования. Введем обозначения: sum(l, r) — количество особых клеток на отрезке с l по r, zi — максимальное количество особых клеток, которые можно покрыть, используя только первые i монстров при условии, что i-тый монстр либо остается на месте, либо отправляется влево, di--- максимальное количество особых клеток, которые можно покрыть, используя только первые i монстров при условии, что i-тый монстр остается на месте.
Рассмотрим процесс вычисления di. Пусть i-тый монстр находится в клетке r. Переберем самую левую особую клетку, которая будет покрыта блоком монстров, в котором будет находиться i-й монстр. Пусть эта особая клетка находится в клетке l. Тогда нам требуется r - l дополнительных монстров отправить вправо для того, чтобы покрыть эту особую клетку. Тогда ответ будет равен zi - (r - l) + sum(l, r). Для вычисления di надо взять максимум по всем особым клеткам, левее i-того монстра.
Теперь, после того, как мы вычислили очередное значение di, необходимо обновить некоторые значения zj. Пусть i-тый монстр находится в клетке l. Переберем самую правую особую клетку, которая будет покрыта блоком монстров, в котором будет находиться i-й монстр. Пусть эта особая клетка находится в клетке r. Тогда нам требуется r - l дополнительных монстров отправить влево для того, чтобы покрыть эту особую клетку. Тогда, zi + (r - l) можно обновить следующим значением di + sum(l + 1, r). Так же необходимо не забыть обновить значение zi значением zi - 1.
Как можно видеть это решение имеет сложность O(n·m), так как для каждого из n монстров мы перебираем все m особых клеток, а все вычисления при фиксированной паре монстр-клетка проходят за O(1).
При реализации могут возникнуть небольшие тонкости, связанные с монстрами, которые уже в начальном состоянии слиплись в один блок.
436E - Cardboard Box
Автор разбора: Gerald
В задаче E нужно было написать правильную жадность. Правильных жадностей существует несколько, вот одна из них:
- Посмотрим на некоторый оптимальный ответ (набор как-то пройденных уровней). Отсортируем все уровни по b[i]. Если рассмотреть последний взятый в ответ уровень, пройденный на 2 звезды, то окажется, что все находящиеся до него в таком порядке уровни пройдены хотя бы на одну звезду. Иначе, можно было бы заменить этот уровень на какой-то не пройденный и не увеличить ответ.
- Пользуясь вышесказанным, зафиксируем префикс L уровней в порядке сортировки по b[i]. Все уровни этого префикса мы должны хоть как-то пройти (либо на 1, либо на 2 звезды). Дополнительно, будет считать, что все уровни пройденные на 2 звезды должны содержаться только в этом префиксе (такой префикс должен существовать для некоторого оптимального ответа, как было показано ранее).
- Так как мы зафиксировали префикс длиной L уровней, которые мы точно хоть как-то пройдем, можно сказать, что нам осталось добрать w - L звезд. Как мы можем добирать эти звезды? Либо допроходить какие-то уровни из префикса L на 2 звезды, либо проходить уровни не из префикса L на одну (потому что уровни, которые мы проходим на 2 звезды должны содержаться только на зафиксированном префиксе).
- Понятно, что для того, чтобы получить оптимальный ответ нужно выбрать w - L самых дешевых звезд. Поэтому отсортируем n элементов: L чисел b[i] - a[i] (для всех i ≤ L), n - L чисел a[i] (для всех i > L). Выберем среди этих чисел w - L минимальных.
Описанное нужно было реализовывать быстрее, чем за квадрат. Самая очевидная реализация использует декартово дерево, чуть менее очевидная использует дерево отрезков.
Итоговая сложность решения: O(n log n).
436F - Banners
Автор разбора: Gerald
Задача F была самой сложной задачей контеста. Чтобы лучше представить себе ее решение, можно перейти к геометрическому представлению задачи. Представим, что люди — это точки на плоскости Opc, тогда, то что требуется найти — для каждой прямой c = i, такую прямую p = j, что некоторая функция принимает максимальное значение. Под некоторой функцией понимается следующая: (количество точек не ниже прямой c = i умножить на w·i) плюс (количество точек ниже прямой c = i и не левее прямой p = j умножить на j).
Будем двигать сканирующую прямую снизу вверх. Сначала рассматриваем c = 0, затем c = 1 и так далее. При этом для каждого p будем хранить величину d[p] — чему равен ответ на задачу при текущем c, если второй параметр будет равен p. Если у нас есть корректно посчитанный массив d[] и мы переходим от c к c + 1, как пересчитать этот массив для нового c?
Посмотрим на всех людей, для которых хоть что-то поменяется, очевидно — это люди у которых b[i] = c. При текущем c они еще пользовались бесплатной версией, но после увеличения на 1, они перестанут ей пользоваться. Понятно, что каждый такой человек i модифицирует массив следующим образом: d[1] + = 1, d[2] + = 2, ..., d[b[i]] + = b[i].
Теперь можно переформулировать задачу в терминах структур данных. Есть два вида запросов: прибавить на префиксе возрастающую арифметическую прогрессию, узнать максимум среди всех элементов массива d. Один из способов решить такую задачу — корневая декомпозиция.
Разобьем все запросы на группы по sqrt(q) штук, в каждой группе выделим отрезки, на которых к ячейке d[i] значение i прибавляется с одним и тем же коэффициентом. Для каждого такого отрезка построим нижнее огибающее множество прямых y = d[i] + i·x. Так как запросов в группе sqrt(q), то и отрезков будет O(sqrt(q)). Значит прибавление на префиксе и взятие максимума можно будет делать за O(sqrt(q)).
Итоговая сложность решения: O(MAXX·sqrt(MAXX)), где MAXX — максимальное значение среди a[i] и b[i].
