Hi guys, I need help with a problem that I've been trying to solve for a while now.
Statement: Given a M x N binary matrix with at most 100000 ones, and given two integers a and b, count the number of zero submatrices with size a x b. Constraints: 1 <= a, b <= M, N <= 10000.
Some more info: The memory and time constraints are 64mb, and 1 sec. Sadly, the problem statement isn't in English, but here's a link to it anyway if you guys want to check it out: http://mendo.mk/Task.do?id=616
I explain O(NM) solution with O(NM) memory, it is up to you to get O(N + M + P) memory (it is not hard).
We will separately count rectangles axb ans bxa (if a ≠ b).
Let's build NxM matrix A such that A[x][y] is number of zeroes to the down to the cell (x, y). It can be done in O(NM) time if we go up in each column (if s[x][y] is 0 then A[x][y] = A[x][y + 1] + 1). What cells can be in the upper row of good rectangle axb? It is exactly the cells with A[x][y] ≥ a. Now for each row we should find the amount of segments of length b with every cell having A[x][y] ≥ a. It is exactly the same problem. Fix y. Now we want to calculate B[x] which is the number of cells with A[x][y] ≥ a to the right to the cell (x, y). The answer is the number of cells with B[x] ≥ b.