Это не официальный разбор, который не претендует на правильность. Извиняюсь за возможные ошибки в тексте.
The Battle of Giants
Если $$$a$$$ $$$mod$$$ $$$3 \neq b$$$ $$$mod$$$ $$$3$$$ ответа нету. Иначе ответ это $$$a/3$$$,$$$a$$$ $$$mod$$$ $$$3$$$, $$$b/3$$$.
Tetris Remastered
Найдем максимальный элемент в массиве и заменим каждый элемент на разницу его и максимума массива. Теперь будем заполнять жадно — идем слева нправо в массиве и поддериживаем число $$$u$$$ — высота текущего заполнения. Если нужно заполнить больше ($$$a_i>u$$$), то увеличиваем u, соответственно ответ на $$$a_i-u$$$, иначе уменьшаем чтобы оно стало $$$a_i$$$ и ничего не добавляем к ответу.
Optimal Truck
Вначале важный для решения факт — если грузовиком с грузоподьемностью $$$x$$$ мы получаем нужную прибыль, то с $$$x+1$$$ тоже.
Отсортируем все контракты так, чтобы выполнялось $$$w_i < w_{i+1}$$$ и $$$c_i < c_{i+1}$$$(если какой-то контракт менее требователен и прибыльнее чем другой, нам никогда не выгодно использовать тот который более требователен).
Теперь будем искать бинпоиском минимальную грузоподьемность и проверять за O(n log n), сколько мы получаем за грузовик грузоподъемностью $$$x$$$.(Всегда выгодно брать последний контракт у каждого клиента, который мы можем взять с текущей грузоподьемностью).
Для того чтобы получить полный бал, сделаем массив, в котором будут пары чисел $$$(w, c)$$$, означающие что с грузоподьемностью $$$w$$$ мы получим еще $$$c$$$ денег. Для этого просто добавим вначале самый дешевый контракт каждого клиента, а потом пары $$$(w_i, c_{i+1}-c_i)$$$. Это показывает, что мы получим дополнительно сколько-то денег, мы ничего не будем считать дважды. Теперь чтобы посчитать сколько денег можно получить с грузоподъемностью x нужно сделать всего один бинпоиск по этому массиву. (Для реализации полезны префикс суммы).
Bookshelf Sorting
Для начала решим задачу на постоянной перестановке. Найдем самую длинную подполследовательность вида $$$l,l+1,l+2, ... r-1, r$$$. Я утверждаю, что ответ это $$$n - (r-l+1)$$$. Достаточность доказать несложно — мы переносим все лишние элементы либо в начало, либо в конец, а она остается нетронутой. Необходимость условия интуитивно понятна(я не помню доказательства).
Как найти эту подпоследовательность? Построим обратную перестановку, и найдем самый длинный подотрезок, который является возрастающим. Несложно убедится, что это и есть эта перестановка. На 75 балов достаточно искать каждый раз заново, полное решение немного сложнее.
Построим ДО, в котором в каждой вершине храним ответ(длину найбольшего возрастающего подотрезка), длину самого длинного возрастающего суффикса, длину самого длинного возрастающего префикса и еще немного полезных вещей. Объеденять две вершины просто — ответ может быть либо в одном из подотрезков, либо нужно обьеденить суффикс левого и префикс правого, если это возможно.
Теперь каждый свап двух книг — это две операции изменения на этом дереве, а овтет хранится в корне
Nice Shape
Заметим, что ответ не может быть больше 4(в этом легко убедится на бумаге).
Если ответ меньше 4, то как минимум две ладьи нет смысла перемещать.
В начале переберем каждую пару ладей которые останутся на месте, и попробуем сооставить прямоугольник из них. Нам нужно подвинуть две ладьи на позиции остальных двух вершин. Если есть ладья, которая уже стоит на своем месте, то ее двигать нет смысла. Если есть ладья в одной строке или столбце с нужной позицией, то нам хватит одного движения.
Такое решение за $$$O(n^2)$$$ при аккуратной реализации у меня набрало 60 балов.
Дальше нужно научится быстро проверять сформирован ли прямоугольник(ответ в таком случае 0). Остальные случаи значительно проще. Возможно есть более простой путь, но я пользовался алгоритмом за $$$O(n \sqrt n)$$$. Вначале соеденим все точки с одинаковой первой координатой в группы. Группы размером меньше $$$\sqrt n$$$ назовем маленькими, остальные — большими. Для начала будем искать ответ с только в маленьких группах. Оставим только маленькие группы, потом перегруппируем все по второй координате. Сделаем массив для всех y-координат, в котром изначально нули. Будем проверять, может ли быть прямоугольник с нижней стороной $$$y_c$$$. Для этого пройдем по всем точкам (из множества) с этой координатой. Пусть мы проверяем точку $$$(x_c, y_c)$$$. Всем точкам $$$(x_c, v), v > y_c$$$ из множества сделаем $$$a_v=a_v+1$$$. Если в массиве $$$a_v=2$$$, мы нашли прямоугольник (ограниченый сторонами $$$v$$$ и $$$y_c$$$). Всего есть не более n точек, каждый раз мы проходим не более $$$\sqrt n$$$ увеличений массива. Получается $$$O(n \sqrt n)$$$.
Чтобы искать среди маленькой и большой группы будем делать вот что. пускай мы рассматриваем маленькую группу $$$S$$$. Сделаем счетчик для каждой большой группы, изначально у всех групп ноль. Для каждой точки $$$(p, q)$$$ в $$$S$$$, рассмотрим все большие группы, в которы есть точки с второй координатой $$$q$$$ и прибавим к их счетчикам 1. Аналогично первому случаю, если в каком-то счетчике 2, мы нашли ответ. мы изменяем каждый раз не более $$$\sqrt n)$$$ групп, снова $$$O( n \sqrt n)$$$.
Что делать с большими группами? Я утверждаю, что если мы свапнем координаты, повторим описаный выше процес, то мы найдем ответ, если он содержался среди только больших групп, (большие группы по х станут маленькими по y).
Остальные случаи значительно проще. Если ответ 1, то это "уголок" и точка, на одной прямой с своим местом(две паралельные прямые на которых есть хотябы одна общая y координата).
Ответ 2 только если у нас есть просто хотя-бы две горизонтали или вертикали, на которых не менее двух ладей.
Ответ 3 только тогда, когда все точки не на одной прямой, и есть хотя-бы одна вертикаль или горизонталь, на которой больше 1 точки.
Иначе ответ 4.
Комментарии (0)
