426A - Сережа и кружки

Посчитаем сумму всех элементов Sum и значение максимального элемента M. Если Sum - M ≤ S то ответ — да, иначе — нет.

426B - Сережа и развороты

Решим задачу с обратной стороны. Будем пытаться свернуть нашу матрицу как можно больше число раз. Свернуть означает операцию, обратную к описанной в условии. Для проверки, можно ли свернуть матрицу нужно, что бы выполнялись следующие условия:
1). n mod 2 = 0
2). a_i, j = a_{n - i + 1, j} for all 1 ≤ i ≤ n, 1 ≤ j ≤ m.

425A - Сережа и обмены

Переберем интервал, на котором будет находится максимальная сумма. Для улучшения суммы, мы можем поменять не более K минимальных элемента из интервала на не более K максимальных элементов, не принадлежащих отрезку. Так как n не большое мы можем делать это любым образом, например отсортировать все элементы на интервале по возрастанию и вне интервала по убыванию, а дальше будем менять максимальный элемент из вне интервала на минимальный в интервале по тех пор, пока не поменяем k элементов или не останется не замененных элементов в отрезке или не останется не замененных элементов вне отрезка или операция обмена вообще не будет оптимальной. Сложность авторского решения O(n³·log(n)).

Есть ли у Вас идеи о ток, как решать эту задачу за время O(N) или O(N·log(N)) ?

425B - Сережа и таблица

Заметим, что если у нас есть массив x[1..n], 0 ≤ x_i ≤ 1 и y[1..m], 0 ≤ y_i ≤ 1, то матрица описанная в условии имеет следующий вид a_i, j = x_i xor y_j.
Если n ≤ k, то мы можем перебрать массив x и с помощью жадного алгоритма найти наилучший y. Иначе у нас найдется хотя бы одно i, что мы не должны менять ничего в строке номер i. Таким образом мы можем просто перебрать строку и выбрав ее за x жадно посчитать y. Из всех строк выберем самую оптимальную. Такая строка найдется, потому что ошибок меньше, чем количество столбцов в которых они могут быть.

Под жадным алгоритмом понимается следующий: будем для каждого элемента из y смотреть: лучше ли будет ответ, если определенный бит будет равен 0 или 1. Что бы проще проверять, что оптимальнее можно просто взять текущую строку(i) и посмотреть: сколько бит в ней совпадают с x, а сколько нет. Если совпадающих больше, то y_i = 0, иначе y_i = 1.

425C - Сережа и две последовательности

Для этой задачи будем использовать динамическое программирование: dp_i, j — минимальный номер позиции удаленного элемента во втором массиве, что мы провели первую операцию j раз и удалили из первого массива не более i элементов.

Разберемся теперь как делать переходы. Находясь в состоянии dp_i, j мы можем оставить все как есть и перейти в состояние dp_{i + 1, j}, иными словами сделать dp_{i + 1, j}:  = min(dp_{i + 1, j}, dp_i, j). Что происходит, когда мы делаем первую операцию, при фиксированном префиксе по элемент номер i? Нам нужно найти элемент второго массива с номером больше dp_i, j и равный a_i, пусть это будет элемент номер t, тогда нужно сделать переход dp_{i + 1, j + 1}:  = min(dp_{i + 1, j + 1}, t).

Как быстро искать нужный элемент: просто сделаем вектор вхождений во второй массив для каждого числа и по нему будем запускать бинарный поиск.

425D - Сережа и квадраты

Пускай прямая x = k содержит не более точек. Тогда мы можем просто для каждой пары точек на ней (пускай они будут (k, y₁) и (k, y₂)) проверить: есть ли квадрат, который содержит их как вершины. То есть на нужно проверить: есть ли в наших входных данных пара точек (k - |y₂ - y₁|, y₁) и (k - |y₂ - y₁|, y₂), или пара (k + |y₂ - y₁|, y₁) и (k + |y₂ - y₁|, y₂).

Удалим все просмотренные точки и отразим оставшиеся относительно прямой x = y. Мы получили ситуацию, что каждая прямая x = k содержит не более точек. Решим задачу так же как и в первый раз.

Теперь нужно научится проверять: есть ли пара точек на некоторой прямой. Запишем все эти пары в вектора для тех прямых, где мы хотим проверить. Допустим, мы проверяем все пары для прямой номер k. Пометим в некотором массиве u для всех точек с абсциссой k u_y = k. Теперь пройдем по всем интересующим нас парам (y₁, y₂). Пара нам подходит, только если u_y1 = u_y2 = k.

425E - Сережа и множества

Сначала посмотрим на то, как мы считаем величину F(S). Сперва мы сортируем все интервалы по правому концу, а затем при обходе их в отсортированном порядке смотрим: если текущий интервал не пересекается с последним взятым в множество, то просто возьмем его.

Решение нашей задачи будет использовать эту жадность. Решение задачи, это динамика с параметрами:
1). номер позиции, в которой будут заканчиваться поставленные интервалы.
2). количество поставленных интервалов
3). правая позиция последнего поставленного интервала

Как делать переходы: заметим, что считая dp_{i, count, last} мы можем изменить last только на i, либо вообще не изменять. Давайте посмотрим, что произойдет в обеих случаях. В первом случае last меняется на i, тогда мы должны поставить хотя бы один из интервалов [last + 1, i], [last + 2, i], ..., [i, i], таких интервалов ровно i - last. Что бы узнать количество способов поставить их как нам нужно, можно использовать метод включений-исключений, но на самом деле можно просто взять число 2^i - last - 1. Все остальные интервалы: [1, i], [2, i], ..., [last, i] мы можем брать как хотим, таким образом имеем 2^last способов. Перемножим количества и получим количество переходов из dp_{i, count, last} в dp_{i + 1, count + 1, i}. Если же мы считаем количество переходов из dp_{i, count, last} в dp_{i + 1, count, last}, то просто будем брать число 2^last.

Так же стоит не забыть про случай dp_i, 0, 0. Из которого тоже нужно делать переходы, которые по своей сути тривиальны.

Таким образом мы получили очень простое решение.