413A - Восстановление данных

Посчитаем минимум и максимум в заданном массиве размера m. Если минимум уже меньше заданного min, либо если уже максимум больше заданного max, то ответ Incorrect.

Посчитаем минимальное значение 0 ≤ need ≤ 2, которое будет равняться числу элементов, которые надо добавить в исходный массив, чтобы его минимум стал равен min, а максимум стал равен max. Для этого нужно попарно сравнить минимум заданном массиве со значением min и максимум в заданном массиве со значением max. Тогда ответ Correct, если n - m ≥ need. Иначе ответ Incorrect.

413B - Spyke чат

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

413C - Своя игра

Для начала выберем все вопросы не аукционы и ответим на них. Затем у нас останутся только вопросы аукционы. Отсортируем их по неубыванию стоимости. Далее переберём минимальный размер суффикса, вопросы из которого нужно будет взять за их стоимость, а остальные вопросы возможно будет использовать для умножения нашего выигрыша на 2.

Очевидно, что это наиболее выгодно, поскольку чем меньше стоимость вопроса, тем меньше нужно иметь очков для умножения своего баланса на 2. Так же чем больше стоимость вопроса, тем более выгодно брать его за реальную стоимость.

413D - 2048

Рассмотрим произвольное состояние в нашей игре. Заметим, что нам имеет смысл поддерживать максимальный по длине суффикс чисел в убывающем порядке. При этом будем хранить только младшие k - 1 степень двойки, а также запомним была ли уже достигнута k-ая степень или выше. Действительно, если убывающий порядок нарушился, то мы никогда не сможем использовать эти числа, поскольку значения могут только увеличиваться.

Поэтому посчитаем следующую динамику dp[i][mask][j], где i — размер уже рассмотренного префикса элементов, а mask — маска размера k, в которой бит x возведён тогда и только тогда, когда среди последних идущих по убыванию степеней двойки присутствует 2^x, j — была ли уже достигнута k-ая степень или выше (0 или 1). Возможны два типа переходов, когда пришло число 2 и когда пришло число 4. Если пришло число 0, то выполним оба перехода.

413E - Лабиринт 2D

Будем обрабатывать запросы по очереди. Вначале проверим, достижима ли одна клетка из другой. Для этого вначале найдем компоненты связности. Если клетки находятся в разных компонентах связности, то ответ -1.

Иначе предположим, что обе клетки находятся в столбцах, в которых ровно одно препятствие. Чтобы найти длину пути между ними, необходимо предподсчитать с помощью частичных сумм длины путей между такими столбцами.

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

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