Посчитаем сумму всех элементов Sum и значение максимального элемента M. Если Sum - M ≤ S то ответ — да, иначе — нет.
Решим задачу с обратной стороны. Будем пытаться свернуть нашу матрицу как можно больше число раз. Свернуть означает операцию, обратную к описанной в условии. Для проверки, можно ли свернуть матрицу нужно, что бы выполнялись следующие условия:
1). n mod 2 = 0
2). ai, j = an - i + 1, j for all 1 ≤ i ≤ n, 1 ≤ j ≤ m.
Переберем интервал, на котором будет находится максимальная сумма. Для улучшения суммы, мы можем поменять не более K минимальных элемента из интервала на не более K максимальных элементов, не принадлежащих отрезку. Так как n не большое мы можем делать это любым образом, например отсортировать все элементы на интервале по возрастанию и вне интервала по убыванию, а дальше будем менять максимальный элемент из вне интервала на минимальный в интервале по тех пор, пока не поменяем k элементов или не останется не замененных элементов в отрезке или не останется не замененных элементов вне отрезка или операция обмена вообще не будет оптимальной. Сложность авторского решения O(n3·log(n)).
Есть ли у Вас идеи о ток, как решать эту задачу за время O(N) или O(N·log(N)) ?
Заметим, что если у нас есть массив x[1..n], 0 ≤ xi ≤ 1 и y[1..m], 0 ≤ yi ≤ 1, то матрица описанная в условии имеет следующий вид ai, j = xi xor yj.
Если n ≤ k, то мы можем перебрать массив x и с помощью жадного алгоритма найти наилучший y. Иначе у нас найдется хотя бы одно i, что мы не должны менять ничего в строке номер i. Таким образом мы можем просто перебрать строку и выбрав ее за x жадно посчитать y. Из всех строк выберем самую оптимальную. Такая строка найдется, потому что ошибок меньше, чем количество столбцов в которых они могут быть.
Под жадным алгоритмом понимается следующий: будем для каждого элемента из y смотреть: лучше ли будет ответ, если определенный бит будет равен 0 или 1. Что бы проще проверять, что оптимальнее можно просто взять текущую строку(i) и посмотреть: сколько бит в ней совпадают с x, а сколько нет. Если совпадающих больше, то yi = 0, иначе yi = 1.
Для этой задачи будем использовать динамическое программирование: dpi, j — минимальный номер позиции удаленного элемента во втором массиве, что мы провели первую операцию j раз и удалили из первого массива не более i элементов.
Разберемся теперь как делать переходы. Находясь в состоянии dpi, j мы можем оставить все как есть и перейти в состояние dpi + 1, j, иными словами сделать dpi + 1, j: = min(dpi + 1, j, dpi, j). Что происходит, когда мы делаем первую операцию, при фиксированном префиксе по элемент номер i? Нам нужно найти элемент второго массива с номером больше dpi, j и равный ai, пусть это будет элемент номер t, тогда нужно сделать переход dpi + 1, j + 1: = min(dpi + 1, j + 1, t).
Как быстро искать нужный элемент: просто сделаем вектор вхождений во второй массив для каждого числа и по нему будем запускать бинарный поиск.
Пускай прямая x = k содержит не более точек. Тогда мы можем просто для каждой пары точек на ней (пускай они будут (k, y1) и (k, y2)) проверить: есть ли квадрат, который содержит их как вершины. То есть на нужно проверить: есть ли в наших входных данных пара точек (k - |y2 - y1|, y1) и (k - |y2 - y1|, y2), или пара (k + |y2 - y1|, y1) и (k + |y2 - y1|, y2).
Удалим все просмотренные точки и отразим оставшиеся относительно прямой x = y. Мы получили ситуацию, что каждая прямая x = k содержит не более точек. Решим задачу так же как и в первый раз.
Теперь нужно научится проверять: есть ли пара точек на некоторой прямой. Запишем все эти пары в вектора для тех прямых, где мы хотим проверить. Допустим, мы проверяем все пары для прямой номер k. Пометим в некотором массиве u для всех точек с абсциссой k uy = k. Теперь пройдем по всем интересующим нас парам (y1, y2). Пара нам подходит, только если uy1 = uy2 = k.
Сначала посмотрим на то, как мы считаем величину F(S). Сперва мы сортируем все интервалы по правому концу, а затем при обходе их в отсортированном порядке смотрим: если текущий интервал не пересекается с последним взятым в множество, то просто возьмем его.
Решение нашей задачи будет использовать эту жадность. Решение задачи, это динамика с параметрами:
1). номер позиции, в которой будут заканчиваться поставленные интервалы.
2). количество поставленных интервалов
3). правая позиция последнего поставленного интервала
Как делать переходы: заметим, что считая dpi, count, last мы можем изменить last только на i, либо вообще не изменять. Давайте посмотрим, что произойдет в обеих случаях. В первом случае last меняется на i, тогда мы должны поставить хотя бы один из интервалов [last + 1, i], [last + 2, i], ..., [i, i], таких интервалов ровно i - last. Что бы узнать количество способов поставить их как нам нужно, можно использовать метод включений-исключений, но на самом деле можно просто взять число 2i - last - 1. Все остальные интервалы: [1, i], [2, i], ..., [last, i] мы можем брать как хотим, таким образом имеем 2last способов. Перемножим количества и получим количество переходов из dpi, count, last в dpi + 1, count + 1, i. Если же мы считаем количество переходов из dpi, count, last в dpi + 1, count, last, то просто будем брать число 2last.
Так же стоит не забыть про случай dpi, 0, 0. Из которого тоже нужно делать переходы, которые по своей сути тривиальны.
Таким образом мы получили очень простое решение.