Спешу познакомить вас с авторскими идеями решений задач сегодняшнего раунда. Авторы разбора первых пяти задач — HolkinPV и gridnevvvit, разбор последних двух задач написан мной.

479A - Выражение

В этой задаче нужно было рассмотреть несколько случаев и выбрать лучших ответ. Это можно было сделать так:

int ans = a + b + c;
ans = max(ans, (a + b) * c);
	ans = max(ans, a * (b + c));
	ans = max(ans, a * b * c);

	cout << ans << endl;

479B - Башни

Эта задача решается жадным образом. На каждой итерации нашего алгоритма будем перекладывать кубик с башни с максимальной высотой на башню с минимальной высотой. Для этого можно каждый раз за время O(N) заново находить позиции минимума и максимума в массиве. Итоговое решение тогда будет иметь асимптотику O(KN).

479C - Экзамены, 480A - Экзамены

Эта задача решается жадным образом. Отсортируем все экзамены по неубыванию даты фактической сдачи (то есть по a_i), при равенстве по неубыванию даты досрочной сдачи (то есть b_i). Рассмотрим экзамены в получившемся порядке и будем поддерживать текущий ответ. В первую очередь будем стараться сдать очередной экзамен досрочно (если это не нарушит условие задачи, то есть если никакой предыщий экзамен мы не сдавали позже досрочной даты этого экзамена). В противном случае сдадим этот экзамен в дату его фактической сдачи. Обновим текущим ответ выбранной датой сдачи этого экзамена.

std::sort(a, a + n);  // а - массив пар, где первый элемент фактическая сдача экзамена, а                        второй элемент - досрочная
int best = -1;
for(int i = 0; i < n; i++) {
if (best <= a[i].second) {
		best = a[i].second;
	} else {
	 	best = a[i].first;
	}
}	

479D - Прыжки в длину, 480B - Прыжки в длину

Нетрудно догадаться, что ответом на эту задачу может быть 0, 1 или 2. Если изначально мы можем отмерить расстояния x и y, то сразу выведем 0. Иначе попробуем получить ответ нанесением одной метки. Если это не удастся, в качестве ответа всегда можно вывести две метки, равные x и y соответственно.

Чтобы проверить, можно ли получить ответ 1, переберем каждую из имеющихся отметок, пусть она находится на расстоянии r. Тогда попробуем добавить отметку на одной из позиций: r - x, r + x, r - y, r + y. Если хотя бы в одном из случаев станет возможным отмерить x и y, то можно сразу выводить полученный ответ. Проверить, что можем отмерить x и y, просто. К примеру, пусть мы сделали отметку в r + x (т.е. x мы уже научились отмерять). Тогда надо лишь проверить, что есть отметка в r + x + y или r + x - y, например, бинарным поиском (т.е. отметки отсортированы). Надо также не забыть проверить, что отметки попадают в [0, L].

479E - Катаемся на лифте, 480C - Катаемся на лифте

Эта задача решается при помощи динамического программирования. Состоянием динамики будет пара (i, j), где i — количество посещенных этажей, j — номер этажа, на котором мы сейчас находимся. Начальным состоянием является пара (0, a), конечными состояниями являются пары (k, v), где v — любой этаж от 1 до n.

Чтобы осуществить переход, нужно перебрать следующий посещаемый этаж и пересчитать ответ. Однако нельзя выполнять такой переход в явном виде, поскольку решение будет иметь асимптотику O(N³). Чтобы решение уложилось в требуемый лимит по времени, нужно воспользоваться частичными суммами. При переходе от i к i + 1 предпосчитаем в дополнительном массиве частичные суммы посчитанных ранее динамик (с предыдущей итерации). После этого воспользуемся динамическим программированием “назад” и при подсчете очередного значения будем делать запрос суммы на отрезке в посчитанном массиве частичных сумм. Таким образом, решение будет иметь асимптотику O(N²).

Авторское решение: 8322623

480D - Посылки

Сделаем два наблюдения.

Во-первых, посмотрим на посылки как на отрезки [$in_i, out_i$]. Верно следующее утверждение: если коробка i оказалась в какой-то момент времени сверху коробки j (не обязательно непосредственно сверху), то .

Во-вторых, представим, что на платформе находятся какие-то посылки. Оказывается, что все, что нам нужно знать про этот набор посылок, чтобы понимать, можем ли мы положить что-то сверху, это “остаточная прочность” всех этих посылок. Остаточная прочность определяется так: для каждой посылки из набора остаточная прочность равна прочности этой посылки за вычетом суммарного веса всех стоящих на ней. Для набора посылок остаточная прочность считается как минимум из остаточных прочностей посылок в наборе. Таким образом, новую посылку можно положить, если ее вес не превосходит остаточной прочности уже имеющихся коробок.

Это приводит нас к идее решения задачи динамическим программированием. Пусть в данный момент времени верхняя посылка на платформе имеет номер i, а остаточная прочность имеющихся на платформе коробок равна rs. Сделаем эту пару (i, rs) состоянием динамики: представим, что у нас есть исходная задача, в которой есть только те посылки, которые вкладываются в [in_i, out_i], а платформа имеет прочность rs. В значении динамики d(i, rs) будем хранить ответ для этой новой задачи. Какие существуют переходы? Мы должны выбрать набор посылок i(1), i(2), ... i(k) таких, что

• out_i(j) ≤ in_i(j + 1), т.е. отрезки не пересекаются (кроме концов) и отсортированы по времени;
• вес любой из выбранных посылок не превосходит rs.

Этот выбор соответствует следующей последовательности операций: сначала поставить сверху посылки i посылку i(1). Мы перейдем в состояние i(1), min(rs - w_i(1), s_i(1)), прибавив к сумме стоимость коробки i(1) и ответ для нового состояния. Затем мы снимем все коробки, включая i(1), и поставим i(2), сделаем переход, затем снимем все вплоть до i(2), поставим i(3), и т.д.

Поскольку количество состояний в динамике у нас получилось O(NS), то переходы должны суммарно выполняться за O(N). Этого можно добиться, реализовав внутри несложную вспомогательную динамику. Должно получиться решение со сложностью O(N²S). Отметим, что для единообразия можно считать платформу коробкой номер 0, которая приходит раньше всех, и выходит позже всех. Тогда ответ на задачу — просто значение d(0, S).

480E - Парковка

Будем называть приезды машин на парковку событиями.

Рассмотрим следующее решение (оно поможет нам прийти к авторскому): давайте рассмотрим все возможные пустые квадраты в таблице. Их, конечно, много, но допустим, что мы все же можем их перебрать. Если мы зафиксировали квадрат, то давайте поймем, когда он перестанет быть пустым (найдем первое событие парковки машины в этом квадрате). Пусть номер этого события x, а размер квадрата k. Тогда для всех событий с номерами меньшими, чем x, попробуем обновить ответ значением k.

Авторское решение использует принцип разделяй и властвуй. Давайте напишем рекурсивную функцию, которая принимает подтаблицу, границами которой являются r₁, r₂, c₁, c₂ (r₁ ≤ r₂, c₁ ≤ c₂), а также список всех событий парковки, которые происходят в этой подтаблице. Задача функции — рассмотреть то, как меняются максимальные пустые квадраты в этой таблице по прошествии этих событий, и попытаться обновить ответы для некоторых событий.

Предположим, что c₂ - c₁ ≤ r₂ - r₁ (второй случай будет симметричным). Давайте возьмем среднюю строку подтаблицы: r = (r₁ + r₂) / 2. Разделим все квадраты в подтаблице на три части: те, что строго выше r, те, что строго ниже r, и те, что пересекают r. Для первых двух частей вызовемся рекурсивно (естественно, списки событий при этих вызовах будут свои). Теперь осталось только рассмотреть квадраты, пересекающие (имеющие общие клетки) со строкой r.

По исходной таблице для каждой клетки (r, c) мы можем посчитать расстояние до ближайшей занятой клетки в каждом из четырех направлений (или до края, если такой нет): up(r, c), down(r, c), left(r, c) и right(r, c). Используя эту информацию, мы сейчас построим для строки r две гистограммы: первая представляет из себя массив значений up(r, c) при c₁ ≤ c ≤ c₂, вторая — массив значений down(r, c) при c₁ ≤ c ≤ c₂. Здесь я называю массивы гистограммами, потому что они фактически означают высоты столбиков из пустых клеток, начинающихся в строке r. Назовем первую гистограмуу верхней, а вторую — нижней. Рассмотрим все события, происходящие в подтаблице, в порядке их появления. Каждое событие меняет лишь одно значение в гистограмме. Пусть после мы имеем гистограммы после события с номером x, а следующие событие имеет номер y. Тогда, если мы найдем максимальный пустой квадрат в этих гистограммах (пусть его размер k), то мы сможем обновить ответы для всех событий от x до y - 1 значением k.

Осталось только научиться искать максимальный квадрат в двух гистограммах. Это можно сделать с помощью метода двух указателей. Поставим первый указатель в начало. Будем двигать второй указатель до тех пор, пока в гистограммах есть такой квадрат: квадрат со стороной k имеется, если (минимум на отрезке в первой гистограмме) + (минимум на отрезке во второй гистограмме) — 1 >= k. После того, как это свойство нарушилось, двигаем первый указатель. Для того, чтобы находить минимум за O(1), авторское решение для каждой гистограммы заводит очередь с поддержкой минимума за O(1). Таким образом, поиск максимального квадрата осуществляется за линейное время.

Давайте попробуем оценить время работы. Количество действий внутри одного вызова (без учета рекурсивных вызовов в половинах) равно len·q, где len — длина наименьшей из сторон подтаблицы, а q — количество событий в ней. Если мы представим себе дерево рекурсии, то увидим, что через вызов (т.е. каждый второй вызов) величина len уменьшается в два раза. Суммарное количество действий на одном уровне дерева рекурсии равно O(NK), где k — общее количество событий. Поскольку уровней в дереве O(logN), то общая асимптотика O(NKlogN).