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

Правка en1, от 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

Теги grid, 0-1, polish, iamdeficient

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский minimario 2017-01-03 01:36:15 1009 Initial revision (published)