Weeks ago I ran into this algorithmic problem:
https://www.hackerrank.com/contests/w8/challenges/cross-matrix
Given a binary matrix up to 1500x1500, you are to compute the number of pairs of all-1 rectangles that overlap yet neither of them is completely contained by the other. We have to output this number mod a big fixed number M=1000000007. The time limit for C/C++ is 4 seconds.
My journey with this problem was a bit long. During the contest I submitted a version v0 that failed at two test cases. After the contest I got another version v1 that passed! But I found that the most nasty test case is missing, which my version still fails to solve within time limit, and author's solution passes just fine! With some brain storm, I came up with the solution v2 that nails the worst case as well.
===================== v0: O(N^3) ==========================
The problem itself is a bit intimidating. Given the size limit 1500, we can imagine an O(N^3) algorithm will probably exceed the time limit. However the number of rectangles itself is O(N^4), and not to mention the goal is to compute the number of rectangle pairs!
After some thought, it seems directly counting the pairs that satisfy the condition is hard, as there're many possible relative positions among the two. So, why not count the pairs that DON'T satisfy the condition?
Let's first define some variables:
n_rec: #rectangle
n_total_pair: #rectangle pairs=C(n_rec, 2)
n_disjn_pair: #disjoint pairs
n_intra_pair: #pairs that one completely contains the other
From now on by rectangle we mean all-1 rectangle.
At high level, the answer we're seeking is n_total_pair-n_disjn_pair-n_intra_pair. First, a O(N^2) preprocessing gives us the max number of consecutive 1s we can get any give cell (x, y) and direction d if we walk from (x, y) along d.
Moreover, we want to get these values as well:
N(y): #rectangle north of line Y=y AND touches line Y=y
E(x)
S(y)
W(x)
And the following can be obtained by accumulating values above in the appropriate direction and order in O(N):
Nacc(y): #rectangle north of line Y=y
Eacc(x)
Sacc(y)
Wacc(x)
NE(x,y): #rectangle northwest of (x,y) AND touches line Y=y and X=x
SE(x,y)
SW(x,y)
NW(x,y)
And the following can be obtained by accumulating values above in the appropriate direction and order in O(N^2):
NWacc(x,y): #rectangle northwest of (x,y)
SEacc(x,y)
SWacc(x,y)
NWacc(x,y)
Why do we need them? Because they essentially tell us the number of pairs that can be split horizontally, vertically, and both, and n_disjn_pair can be computed as
sum_x[E(x)*Wacc(x-1)] + sum_y[S(y)*Nacc(y+1)] -
sum_{x,y}[SW(x,y)*NEacc(x+1,y+1)] - sum_{x,y}[SE(x,y)*NWacc(x-1,y+1)]
So, in order to get these numbers, we can do this O(N^3) scan:
for each row y
for each segment x0, x1 s.t. x0 <= x1
update n_rec
update n_intra_pair
update N(y), S(y), E(x), W(x)
update SE(x,y), SW(x,y), NE(x,y), NW(x,y)
end
end
At each position, we're counting the rectangles with one side (x0,y)--(x1,y). After this scan we'll get n_rec, and compute n_total_pair=C(n_rec,2), and then update those accumulated stats and get n_disjn_pair.
What remains is the core part: how do we update n_rec, n_intra_pair, and etc.? At each (y, x0, x1) we know h=the maximum number of rows from Y=y upwards that have all 1s from x0 to x1, i.e. it boils down to a rectangle with dimensions w=x1-x0+1 and h, so we'll add A=w*h to n_rec, N(y), E(x0), W(x1), NE(x0,y), NW(x1,y).
How about n_intra_pair? With some mathematics, you will find that we should add C(w+1,2)*C(h+2,3) to it. And since it actually counts self-identical rectangles, we'll just subtract n_rec from the answer at the end. Note that, it is with the math that we can count much more "aggregatively" and thus much more efficiently.
===================== v1: O(N^3) only for worst case ==========================
Solution v0 is not too smart, because it scans every (x0, x1) out of C(N,2) combinations, so we have to get rid of it. How do we precisely represent the status as we scan? Imagine we scan upwards column by column, and look at the maximum number of consecutive 1s to the right. The numbers of such 1s at previous cell is all we need: below we'd like to store (4,5,3,3,1,6) before we enter the next cell.
1111
11111
111
111
1
111111
This is not concise enough. In fact some info are redundant. For instance the 5 is not as meaningful because there's a 4 before it, i.e. any attempt to make a rectangle will be restricted by the 4 first. Similarly the last 6 doesn't help more than just 1. Intuitively, we only need to keep a decreasing stack of numbers (4,4,3,3,1,1). Even more concise is (4,3,1) with their number of replicas.
With this stack, how should we update n_rec, n_intra_pair, etc.? First of all, unlike v0 here at each position we're counting the rectangles with SE corner at (x,y), if we scan in the same direction and order as v0. You'll observe that except for n_intra_pair, all we need to do is to add the sum of this stack to n_rec and other appropriate numbers. In the example above we'll have to add 4+4+3+3+1+1=16. Although the stack will get updated as we scan, we can store an array of prefix sums in another array (2,8,16), so that getting the sum to add takes O(1). What is the cost to update the stack? My first thought is to do
binary search with O(log(N)), but later I notice in the author's solution that simply popping the stack until its top is strictly less than the current max number of consecutive 1s will give an amortized cost of O(1).
Now, everything looks great except for n_intra_pair. It didn't seem possible to update it quickly with just this stack and prefix sum, so I just compute sum[C(h+1,2)*C(w+1,2)] in the stack with O(N). Therefore unfortunately the time complexity of this version is still O(N^3). But what's the case that really takes O(N^3)? It'll be something like 1s and 0s divided by a diagonal, and it seems missing the author's test case though, so this solution passed.
===================== v2: O(N^2) ==========================
Now the only thing we have to deal with is n_intra_pair, which we still computed in O(N^3). The reason we couldn't do it more efficiently was there doesn' seem to be a simple prefix sum that'd work and is similar to the one we used to store the partial sum in
the stack. I got stuck with this for a really long time, until I decided to put everything in math formula with absolute cooridates on the paper.
Let's assume we have a stack y[] of max number of consecutive 1s, and their absolute positions x[], where x[0] = -1 and y[0] won't be used ever. In the following example, x[] = {-1,3,5,7}, y[] = {?,2,4,6}
111111
1111111
1111
11111
11
111
...
....
---------matrix boundary
As before, combinatorics tells us that the total addition to n_intra_pair with this stack with length K is
sum_{i=1}^{K}[C(y_i+2,3)*[C((x_K-x_{i-1})+2,3)-C((x_K-x_i)+2,3)]]
Expanding this gives us three terms:
A=sum_{i=1}^{K}f0(x_i,x_{i-1},y_i)
B=sum_{i=1}^{K}f1(x_i,x_{i-1},y_i)*x_K
C=sum_{i=1}^{K}f2(x_i,x_{i-1},y_i)*x_K^2
We can therefore keep 3 prefix sums for A, B/x_K, C/x_K^2, and sum them up after
multiplying with x_K and x_K^2 appropriately in O(1). So now, n_intra_pair takes O(N^2) too.
And that's it! Easy enough to verify the correctness of the code and efficiency against the worst test case, the problem is totally solved. As mentioned by the author, it is indeed a good problem to train the skill of counting, patience, and math skill. Looking forward to another interesting problem next time!
