Interesting Blog on All-0 Rectangles in 0-1 Grids

Revision en1, by minimario, 2017-01-03 01:36:15

Hi, everyone!

Recently I was solving problem Plot Purchase from OI 15 and Parcels from OI 9. Then, Errichto shared with me a great article with a similar problem here.

Unfortunately, I am no pole, and even with Google Translate I was not able to understood the idea of the solution mentioned in the blog. Here is the problem mentioned in the blog: Given a N by N square grid of 0s and 1s, compute an array A[N][N], where A[x][y] denotes the number of rectangles of all 0s with height x and width y. The blog solves the task in O(N2).

I'm wondering if anyone (Polish or not), can understand the solution in this blog (I guess there's pseudocode at the end, but I couldn't understand it either) or invent a solution of your own to solve the task. I've thought about it for a few days, to no success.

Thanks!

-minimario

Tags grid, 0-1, polish, iamdeficient

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English minimario 2017-01-03 01:36:15 1009 Initial revision (published)