Впервые я ее увидел на форуме codenet.ru. Практического применения у нее, скорее всего, нет. Зато она очень похожа на олимпиадную задачу. Если вы знаете что-нибудь о ее происхождении, сообщите мне, пожалуйста.
На прямоугольном клетчатом поле можно рисовать прямоугольники. Их углы должны быть в углах клеток поля, стороны должны быть параллельны сторонам поля. Вычеркнем некоторые ребра — стороны клеток. Правильным называется прямоугольник, стороны которого не проходят через вычеркнутые ребра. Требуется сосчитать число различных непустых правильных прямоугольников.
Например, прямоугольное поле 6 на 4, вычеркнутые ребра стерты:
Пусть m — ширина поля, n — высота.
Для решения задачи нужно просмотреть все ребра в поле. Отсюда оценка сложности снизу: mn.
Простейшее решение — перебрать все прямоугольники и проверить их првильность. Число прямоугольников равно ((m + 1)m / 2)((n + 1)n / 2). Чтобы проверить правильность одного прямоугольника, надо проверить все ребра. Их не более 2m + 2n. Сложность будет O(m2n2(m + n)).
Для каждой строки горизонтальных ребер построим кумулятивный массив для числа вычеркнутых ребер. Правильность цепочки ребер можно проверить, сравнив значения из кумулятивного массива на концах цепочки. Если они равны, то цепочка правильная. Строятся все необходимые кумулятивные массивы за O(mn). С этим ускорением сложность алгоритма уменьшится до O(m2n2).
Зафиксируем два числа x1 и x2 так что x1 < x2. Теперь сосчитаем все прямоугольники с левой границей равной x1 и правой — x2. Забудем на время о вычеркнутых вертикальных ребрах. Тогда любая пара правильных горизонтальных ребер задает правильный прямоугольник. Если таких ребер всего k, то число их упорядоченных пар, таких, что y1 < y2, будет равно k(k - 1) / 2.
Эта техника применима и в случае, когда есть вычеркнутые вертикальные ребра. Только применять ее надо к таким диапазонам [y1, y2], что вертикальные ребра (x1, y1) - (x1, y2) и (x2, y1) - (x2, y2) правильные. Такие диапазоны естественно назвать правильными. Чтобы посчитать все прямоугольники, нужно найти все правильные диапазоны максимальной высоты, в каждом сосчитать правильные горизонтали, рассчитать число прямоугольников и сложить все такие числа.
Для фиксированных x1 и x2 время подсчета числа прямоугольников — O(n). Число пар x1 < x2 равно (m + 1)m / 2. Время работы всей программы — O(m2n).
Это не единственное кубическое решение: то же время можно получить, использовав динамическое программирование. Наверняка есть и другие решения.
Пусть n ≥ m. Если это не так, то поле можно равернуть на 90 градусов. Разобьем поле на две примерно равные половины горизонтальной линией y0. Все прямоугольники на поле можно разбить на три группы. В первую попадают все прямоугольники, пересекающие линию, то есть y1 < y0 и y0 < y2; во вторую — все прямоугольники под линией (y2 ≤ y0); в третью — над линией (y0 ≤ y1).
Подсчет прямоугольников во второй и третьей группах выполним рекурсивно. Рекурсия будет продолжатся до тех пор, пока размер поля не сократится до единичного квадрата, а в этом случае достаточно просто проверить четыре стороны единственного единичного прямоугольника.
Подсчитаем число прямоугольников в первой группе. Переберем все пары x1 < x2 и для каждой подсчитаем число прямоугольников, отвечающих условию y1 < y0 < y2. Для этого сосчитаем правильные П-образные скобки со сторонами x1, x2 и опирающиеся на y0 и такие же перевернутые скобки. Каждая пара, состоящая из одной нормальной скобки и одной перевернутой, задает правильный прямоугольник и наоборот, каждый прямоугольник, пересекающий y0, задается такой парой. Чтобы сосчитать число прямоугольников, надо перемножить количество нормальных скобок на число перевернутых.
Обозначим через corners(x1, x2) число правильных углов вида (x1, y0) - (x1, y) - (x2, y), где y — любое число больше y0.
Утверждение. Число правильных скобок от x1 до x2 равно min(corners(x1, x2), corners(x2, x1)).
Доказательство.
Определим y1: y1 ≥ y0 и (x1, y0) - (x1, y1) — самое длинное правильное ребро идущее вверх от (x1, y0). Аналогично определим y2 для (x2, y0).
Введем два множества
Y12 = {y | y0 < y ≤ y1 ∧ (x1, y) - (x2, y) — правильная} и
Y21 = {y | y0 < y ≤ y2 ∧ (x1, y) - (x2, y) — правильная}.
Очевидно, что
y1 ≤ y2 ⇒ Y12 ⊆ Y21 и
y2 ≤ y1 ⇒ Y21 ⊆ Y12.
Заметим, что
corners(x1, x2) = |Y12| и
corners(x2, x1) = |Y21|.
Отсюда
y1 ≤ y2 ⇒ corners(x1, x2) ≤ corners(x2, x1) и
y2 ≤ y1 ⇒ corners(x2, x1) ≤ corners(x1, x2).
Любому элементу множества Y = Y12 ∩ Y21 соответствует правильная скобка. И наоборот, любой правильной скобке соответствует ее высота y: y ∈ Y.
Доказательство завершено.
Опеределим функцию right: right(x, y) = max {x' | (x, y) - (x', y) — правильное}. То есть, фукция right для каждой точки поля указывает конец самой длинной правильной цепочки ребер, идущих вправо. Аналогично определим функцию left. Обе функции можно вычислить за O(mn) для всего поля.
Вычислим функцию corners для фиксированного x1. Найдем y1. Заведем временный массив а[0 .. m] и заполним его нулями. Для каждого y от y0 + 1 до y1 добавляем единицы в ячейки a[right(x1, y)] и a[left(x1, y)]. Тогда если x2 > x1, то corners(x1, x2) будет равно сумме элементов массива a в диапазоне от x2 до m. Если x2 < x1, то corners(x1, x2) равно сумме в диапазоне от 0 до x2.
Время подготовки массива corners — m(m + n). Время подсчета прямоугольников — m2. В сумме снова m(m + n). Если вспомнить, что m < n, то время работы пропорционально mn.
Слияние выполняется за время пропорциональное площади поля. Деление поля делит площадь примерно пополам. Следовательно, полное время работы — O(mnlog(mn)).
Существует ли решение задачи за mn?
Во втором решении получилась несимметричная сложность m2n. Можно ли ускорить второе решение?
Спасибо Антону Козыреву, который обратил мое внимание на эту задачу. Хорошую задачу найти трудно. Он же решил ее за m2n с помощью динамического программирования.
Спасибо коллективу программистов CreatStudios, которые в 2006 году пытались решить эту задачу.
Спасибо Дмитрию Лебедеву, который улучшил решение с mnlog2(mn) до mnlog(mn). Его решение во многом совпадает с приведенным здесь решением в стиле "разделяй и властвуй".