Нахождение максимальной площади в заданных двоичных данных

Question

У меня проблема с описанием алгоритма нахождения максимальной прямоугольной области двоичных данных, где 1 встречается в k раз чаще, чем 0. Данные всегда n ^ 2 бита, например:

Например, данные дляn = 4 выглядит так:

1 0 1 0
0 0 1 1
0 1 1 1
1 1 0 1

Значение k canбыть 1 .. j (k = 1 означает, что число 0 и 1 равно).

Для приведенного выше примера данных и для k = 1 решение равно:

10 1 0 <- 4 x '0' и 4 x '1' <br> 0 0 1 1
0 1 1 1
1 1 0 1

Но в этом примере:
1 1 1 0
0 1 0 0
0 0 0 0
0 1 1 1

Решение будет:
1 1 1 0
0 1 0 0
0 0 0 0
0 1 1 1

Я пробовал с несколькими алгоритмами перебора, но для n> 20 это слишком медленно.Можете ли вы посоветовать мне, как мне решить эту проблему?

---

Как предложил RBerteig, проблему можно также описать так:найдите самую большую прямоугольную область, где 1 и 0 встречаются в указанном соотношении, k. "

Answer 1

Bruteforce должен нормально работать при n <100, если он правильно реализован: приведенное ниже решение имеет O (n ^ 4) время и O (n ^ 2) сложность памяти.10 ^ 8 операций на современном ПК должны занимать менее 1 секунды (особенно если учесть, что каждая операция очень дешевая: мало сложений и вычитаний). </p>

Некоторые наблюдения

1. Есть O(n ^ 4) под прямоугольников для рассмотрения, и каждый из них может быть решением.
2. Если мы можем найти число 1 и 0 в каждом под прямоугольнике в O (1) (постоянное время), мыРешим задачу за O (n ^ 4) раз.
3. Если мы знаем число 1 в некотором под прямоугольнике, мы можем найти количество нулей (через область).

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

Теперь представьте, что у нас есть под прямоугольник [i0..i1]x[j0..j1].То есть он занимает строки между i0 и i1 и столбцы между j0 и j1.И пусть count_ones будет функцией для подсчета количества единиц в подпрямоугольнике.

Это основное наблюдение:

count_ones([i0..i1]x[j0..j1]) = count_ones([0..i1]x[0..j1]) - count_ones([0..i0 - 1]x[0..j1]) - count_ones([0..i1]x[0..j0 - 1]) + count_ones([0..i0 - 1]x[0..j0 - 1])

То же наблюдение с практическим примером:

AAAABBB
AAAABBB
CCCCDDD
CCCCDDD
CCCCDDD
CCCCDDD

Если нам нужно найти число 1 в под прямоугольнике D (3x4), мы можем сделать это, взяв число 1 во всем прямоугольнике (A + B + C + D), вычтя число 1 в (A +)B) прямоугольник, вычитая число 1 в (A + C) прямоугольнике, и добавляя число 1 в (A) прямоугольнике.(A + B + C + D) - (A + B) - (A + C) + (A) = D

Таким образом, нам нужна таблица sums, для каждого i и j, содержащая количество единиц в под прямоугольнике [0..i][0..j].
Вы можете создать эту таблицу в O (n ^ 2), но даже прямой способ его заполнения (для каждой i и j итерации всех элементов [0..i][0..j] области) будет O (n ^ 4).

Наличие этой таблицы,

count_ones([i0..i1]x[j0..j1]) = sums[i1][j1] - sums[i0 - 1][j1] - sums[i1][j0 - 1] + sums[i0 - 1][j0 - 1]

Следовательно, сложность времени O (n ^ 4) достигнута.

Answer 2

Это все еще грубая сила, но вы должны заметить, что вам не нужно пересчитывать все с нуля для нового i*j прямоугольника. Вместо этого для каждого возможного размера прямоугольника вы можете перемещать прямоугольник по сетке n*n по одному шагу за раз, уменьшая количество битов, которых больше нет в прямоугольнике, и увеличивая количество битов, которые недавно вошли в прямоугольник. Вы можете комбинировать это с изменением размера прямоугольника и попытаться найти оптимальный шаблон для перемещения и изменения размера прямоугольника.

Answer 3

Только несколько подсказок ..

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

N1*(k+1) == S*k, где N1 - число единиц в области, а S=dx*dy - ее поверхность.Его можно переписать в лучшую форму:

N1/k == S/(k+1).

Поскольку наибольший общий делитель чисел n и n+1 всегда равен 1, то N1 должно быть кратно k и dx*dy, чтобы быть кратным k+1.Это значительно уменьшает возможное пространство решений, чем больше k, тем лучше (для случая dx*dy вам нужно будет играть с простыми делителями k+1).

Теперь, потому что вам нужнопросто поверхность самой большой области с таким свойством, было бы разумно начать с самых больших областей и перейти к меньшим.Пытаясь dx*dy от n^2 до k+1, которые удовлетворяли бы делителю и ограничивающим условиям, вы найдете довольно быстрое решение, намного быстрее, чем O (n ^ 4), по особой причине: кроме случаевесли массив был специально создан, если мы предположим случайный ввод, вероятность того, что в (n-dx+1)*(n-dy+1) значениях *1029*, имеющих поверхность S, есть N1 значений, будет постоянно расти с уменьшением S.(большие значения k уменьшают вероятность, но в то же время они усиливают фильтр для пар dx и dy).

Также эта проблема: http://ioinformatics.org/locations/ioi99/contest/land/land.shtml, выглядит как-то похоже, может быть, вы найдете некоторые идеи в их решении.