Geek asks and answers

How to find minimum sub-screening with at least K 1 in matrix 0-1

I ran into an extraordinary problem that defined the matrix NxM 0-1 and the number K (<= NxM), and I need to find the minimum region of the rectangle of this matrix 0-1 with at least K 1 inside, subrectangle. In addition, its area (product of both sizes) should be minimized.

For example:
00000
01010
00100
01010
00000
K = 3

So I can find a subrectangle with a minimum area of ​​6 that contains 3 1 inside.
10
01
10

Note that the target subelement, which I mean, must contain consecutive numbers of rows and columns from the original matrix 0-1.

+5
3
Compute cumulative sum of rows R[i,j] and columns C[i,j].
For top-left corner (i,j) of each possible sub-rectangle:
   Starting from a single-row sub-rectangle (n=i),
   Search the last possible column for this sub-rectangle (m).
   While m>=j:
     While there are more than 'k' "ones" in this sub-rectangle:
       If this is the smallest sub-rectangle so far, remember it.
       Remove column (--m).
       This decreases the number of "ones" by C[m+1,n]-C[m+1,j-1].
     Add next row (++n).
     This increases the number of "ones" by R[m,n]-R[i-1,n].

- O (NM (N + M)).

( -).

( / -) O (1) / , - .

- O (1). , - [1..i, 1..j] (X [i, j]). - [i..m, j..n] X[m,n]-X[i-1,n]-X[m,j-1]+X[i-1,j-1].

Compute cumulative sum of columns C[i,j].
For any starting row (k) of possible sub-rectangle:
  For any ending row (l) of possible sub-rectangle:
    Starting column (m = 1).
    Ending column (n = 1).
    While n is not out-of-bounds
      While there are less than 'k' "ones" in sub-rectangle [k..l,m..n]:
        Add column (++n).
        This increases the number of "ones" by C[l,n]-C[k-1,n].
      If this is the smallest sub-rectangle so far, remember it.
      Remove column (++m).
      This decreases the number of "ones" by C[l,m-1]-C[k-1,m-1].

- O (N 2 M).

Loop by 'l' , , , - ( ), -, , "" ( ).

+3

NP-hard, = a > . , , , ( P = NP).

:

  • .
  • K = L ^ 2, L - , .
  • . L-clique iff - LxL, ( ).
0

On top of my head, you can make a list of coordinate pairs (?) Of all units in the matrix, find the (smallest) contained under the rectangles for each K-combination among them *, then select the smallest of them.

*, which is determined by the smallest and largest indices of rows and columns in the K-combination.

0
source

More articles:


All Articles