PROBLEM LINK:Author: Roman Rubanenko DIFFICULTY:Medium PREREQUISITES:Dynamic Programming PROBLEM:Given a N * M matrix mat with some obstacles inside, deal with Q queries of finding the maximum empty submatrix in the submatrix mat[L_{i}..H_{i}, *]. EXPLANATION:First of all, we need to know how to deal with a single query. It is a classical dynamic programming problem, such as POJ 3494 Largest Submatrix with All 1's. We can maintain an array up[1..N][1..M], where up[i][j] stands for the number of consecutive empty entries starting from (i, j) (inclusive). This array can be generated by the formula as following in O(NM) time.
To find the maximum empty submatrix, we only need to consider the extremal submatrix as shown in the following figure. That is, the candidate (extremal) submatrix can't extend itself in any directions. Extend means to enlarge the submatrix by adding an empty row or column to four directions (left, up, right, down). Suppose the matrix is bound by the vertical line based on (i, j), its height should be up[i][j] and what we need is to calculate the horizonal boundary (left[i][j], right[i][j]), left and right are both exclusive. Because left and right are similar, we only focus on the left here. By the definition, left[i][j] is the first column k on the left side of j, such that up[i][k] is smaller than up[i][j]. There are two ways to calculate the left[i][*]. First one, using the similar way to the disjoint set:
This algorithm is O(NM alpha(M)), where alpha() is the inverse of the Ackermann function. The second one is to use the monotonic stack (up[i][stack[ptr]] > up[i][stack[ptr  1]] ) to solve this problem in O(NM) time.
Till now, with the help up, left and right, we can easily deal with a single query in O(NM) time (take all extremal empty submatrix and find the maximum). It is the time to start to deal with the orignal queries. It is worth noting that, even for the query with L, H restrictions, we only need to consider the extremal submatrix too. Because if the best submatrix can extend in any direction (extend means adding an empty row or column to four directions to enlarge the "best submatrix"), the new area will not be worse after we extended that submatrix even if the extended parts are not in the query boundary. Let's define some auxiliary variables. Let c[l][r] is the maximal width of empty rectangle between lth and rth rows such that height is r  l + 1. Initially, c[][] = 0. And then, for each nonobstacle entry (i, j), we update the extremal submatrix to their exact boundaries, as following:
Finally, we extend the exact boundaries to their inner ones.
we can update c[][] in O(N^2), as following:
Similarly, we define d[l][r] as answer for corresponding query. The answer is max{c[i][j] * (j  i + 1), d[i][j  1], d[i + 1][j]} (the bounary case is d[i][i1] = 0). So, we should fill in the d[][] in order of increasing the length of interval j  i + 1, in similar way to that we get c[][]. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 13 Jan '14, 15:12

This problem is similar to "http://www.spoj.com/problems/ASTDPROB" How can a similar question come in a contest.... Setters are supposed to set a new problem!!!!!! I mean a user can get many hints from stackoverflow, forums, and many other things for the problem if it is copied. answered 13 Jan '14, 21:18

@shangjingbo The links to the tester and setter's solution link back to the editorial page itself. Could you please correct the links. answered 13 Jan '14, 20:46

Can somebody elaborate on this part ... really unclear... what is i,j and how are we obtaining d[][] by using c[][] ... answered 14 Jan '14, 18:08

I think some drawings should be added to this editorial answered 13 Jan '14, 16:55

I submitted same program in C++ and in C , my C solution got AC while C++ was giving TLE. Can anyone tell me why? C++ sol http://www.codechef.com/viewsolution/3232566 C sol http://www.codechef.com/viewsolution/3232562 answered 13 Jan '14, 17:24
1
(13 Jan '14, 17:27)
it has been commented.and how it is going to affect the run time of the program...
(13 Jan '14, 18:53)
1
you used cout in C++ and printf in C which is much faster than cout ...
(13 Jan '14, 22:14)
can anyone tell the complexity of my C sol link given above. Is it according to the editorial or not?
(13 Jan '14, 22:29)
Hm?
(14 Jan '14, 00:58)

O(n^2 m) passed. answered 13 Jan '14, 17:50
oh really? can you share some details? It will be helpful to setter and tester to find stronger test cases I think.
(13 Jan '14, 18:48)
10
(13 Jan '14, 18:49)
http://www.codechef.com/viewsolution/3170885 I only used very fast I/O, nothing special besides that. Also, my solution's runtime (other than I/O) depends only on the numbers N,M and not on some other properties of the given matrix or queries.
(13 Jan '14, 19:10)
What? I fast scaned your solution, it looks like a O(NM) algorithm? You mean the "stack" for another M? It seems that all number will be in/out the stack only once. Therefore O(NM) in total?
(13 Jan '14, 19:50)
No, there are three nested forloops clearly visible in inline void racunajsol()
(13 Jan '14, 19:54)
wait, I see a totally different solution than what I read before.... let me have a look
(13 Jan '14, 22:45)
okay, you are right. thanks to the weak test cases and relax time limit.
(13 Jan '14, 22:47)
showing 5 of 7
show all

Certain O(NNM) solution have got accepted using fast input output :(. answered 13 Jan '14, 22:02

I used the exact approach as above but getting NZEC error (java) pls help. http://www.codechef.com/viewsolution/3253203 answered 14 Jan '14, 01:54
