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
This problem is taken from here: https://www.hackerrank.com/contests/infinitum-sep14/challenges/demidenko-farmer (editorial includes only some slower and more complex solutions) and here is my code: http://ideone.com/r37Qxb it looks simple enough to understand it (don't ask me about it).
Isn't this very similar to the problem of finding the maximum area sub-rectangle having only 0s. What you can do is first fix the base at y = 0. Now the problem reduces to finding all the possible sub-rectangles having their base at y = 0 consisting of only 0s. If we can solve this in O(n) then for each base we would do the same and eventually the complexity will be O(n^2).
So when we fix the base at y = 0. From x = 0 to x = n - 1 we loop and for each column we know its height (ie. the number of consecutive elements in the upward direction consisting of only 0s, this is precalculated), let this be height[i]. So using the stack approach for each i, we find the left most and right most point up till which this height[i] is the minimum most.
Let these 2 end points be l and r. Now we need to increment +1 for all the subrectangles of dimension —
Length — From 1 to (i - l + 1) * (r - i + 1), ie. from 1 to L (random notation)
Breadth — From 1 to height[i], ie. from 1 to B (random notation)
Meaning all the subrectangles having i'th column up to maximum height[i].
This is essentially a range update in a square grid which can be done by incrementing the cntr[L][B] and after looping through y = 0 to n — 1, we can do a O(n^2) loop on the cntr array with this cntr[i][j] = cntr[i + 1][j] + cntr[i][j + 1] - cntr[i + 1][j + 1] (inclusion exclusion).
The stack approach I referred to is basically the pushing of elements (from x = 0 to n - 1) in a stack and maintaining a strictly increasing order. When a new element is inserted the top element of the stack is popped till the time the top is >= the current height[i] to be inserted. When the popping stops the new top is the l for height[i] and during the popping all the elements popped would record height[i] as their respective r. In this way each element would get its left most and right most point in which it is the minm most.
Seems correct to me if you can find any fault do let me know.