Count the number of zero submatrices with size a x b from a big binary matrix?

Revision en1, by Dekacc, 2016-08-15 12:57:20

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Dekacc 2016-08-15 12:57:20 571 Initial revision (published)