×

# METEORAK - Editorial

Author: Roman Rubanenko
Tester: Mahbub
Editorialist: Jingbo Shang

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[Li..Hi, *].

# 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.

if mat[i][j] is an obstacle:
up[i][j] = 0
else
up[i][j] = up[i - 1][j] + 1


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:

for i = 1 to N do {
for j = 1 to M do {
left[j] = j - 1;
while (left[j] > 0 && up[i][left[j]] >= up[i][j]) {
left[j] = left[left[j]];
}
}
}


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.

for i =  1 to N do {
top = 0;
for j = 1 to M do {
while (top > 0 && up[i][stack[top - 1]] >= up[i][j]) {
top = top - 1;
}
if (top == 0) {
left[i][j] = 0;
} else {
left[i][j] = stack[top - 1];
}
stack[top] = j;
top = top + 1;
}
}


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 l-th and r-th rows such that height is r - l + 1.

Initially, c[][] = 0. And then, for each non-obstacle entry (i, j), we update the extremal submatrix to their exact boundaries, as following:

c[i - up[i][j] + 1][i] = max{ c[i - up[i][j] + 1][i], right[i][j] - left[i][j] - 1 }


Finally, we extend the exact boundaries to their inner ones.

c[l][r] = max(c[l][r], c[x][y]), (1 <= x <= l <= r <= y <= N)


we can update c[][] in O(N^2), as following:

for len = N downto 2 do {
for l = 1 to N - len + 1 do {
r = l + len - 1;
c[l + 1][r] = max{c[l + 1][r], c[l][r]};
c[l][r - 1] = max{c[l][r - 1], c[l][r]};
}
}


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][i-1] = 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.
Tester's solution will be uploaded soon. here and here.

This question is marked "community wiki".

161446375
accept rate: 0%

19.8k350498541

 31 No offense against the editorialist. I highly appreciate your efforts. I have some feedback which can be taken -vely but should be taken +vely. I feel that the quality of this editorial needs improvement. Didn't understand half of it. "That is, the candidate submatrix can't extend itself in any directions." - What is candidate matrix? What do you mean by "extend itself". These concepts must be easy for you to understand but very difficult for others. Editorials are not seen by pro/expert coders but by struggling ones who could'nt solve the problem. So I feel that editorials should be as clear as possible rather than a namesake. "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, the new area will not be worse after we extended that submatrix even if the extended parts are not in the query boundary." - :( answered 13 Jan '14, 15:44 5★nitinj 2.2k●11●20●27 accept rate: 5% 5 OK, thanks for your suggestions, I have uploaded a figure to try to help you undertand this editorial (also some sentence are added to explain the "extend"). I hope you can learn the DP from this editorial :) (13 Jan '14, 18:45) Thanks mate :) ..much appreciated (13 Jan '14, 20:20) nitinj5★ 1 my pleasure to help you :D (13 Jan '14, 22:43)
 13 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 3★laxman94 1.2k●3●15●15 accept rate: 6%
 4 I'm just wondering was there worst case (for I/O) test case included? worst test case: 1000 1000 1 1 1 1000000 100 1000 100 1000 ...  where output should be 901000 901000 ...  so we have ~9MB of input to read and ~7MB of output (correct me if I'm wrong) to output and there is no algorithm time included, are SPOJ servers able to that in timelimit of 1s? answered 13 Jan '14, 15:27 16.9k●49●115●225 accept rate: 11% That's a good question to the Problem Setter. (13 Jan '14, 18:47) 1 Why not use some of the accepted solutions and check it yourself? :) The largest input file size is 6957085 bytes, so your test case is not included. It is definitely no problem to handle such amount of data in C and C++ (based on the accepted solutions, even 10 times as big data would be probably feasible). (14 Jan '14, 02:16) pavel6★ 2 As for Java, the best accepted solution has a total run time just below 2 s, which is the time limit for Java, so it's definitely feasible as well. Using my Core i7@2,2 GHz, I'm able to read your input and produce your output in about 0,5 s. SPOJ use Pentium G860@3 GHz. I don't have this CPU, but its performance should be comparable in this case, so handling the I/O in under a second should be possible. (14 Jan '14, 02:19) pavel6★
 1 @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 3★kcahdog 10.0k●28●54●129 accept rate: 14% Indeed, I am still waiting for Suraj to give me the links too... (13 Jan '14, 22:47)
 1 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][i-1] = 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[][]. 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 16●2 accept rate: 0%
 0 I think some drawings should be added to this editorial answered 13 Jan '14, 16:55 212●1●8 accept rate: 0% 1 Thanks for your suggestions. I have added a figure. (13 Jan '14, 18:46)
 0 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 3★hatim009 464●2●11●22 accept rate: 8% 1 freopen("ip.txt","r",stdin); in C submission? (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) hatim0093★ 1 you used cout in C++ and printf in C which is much faster than cout ... (13 Jan '14, 22:14) xpd542★ 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) hatim0093★ Hm? fropen is not commented in code with TLE you linked! (14 Jan '14, 00:58)
 0 O(n^2 m) passed. answered 13 Jan '14, 17:50 105●1●4 accept rate: 0% 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) xellos07★ 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 for-loops 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
 0 Certain O(NNM) solution have got accepted using fast input output :(. answered 13 Jan '14, 22:02 4★nivin 11●1●3 accept rate: 0% add link please ;-) (13 Jan '14, 22:04) 1 similar algorithm to @ivan100sic? (13 Jan '14, 22:48)
 0 What is meant by "Suppose the matrix is.....left and right are both exclusive" in the editorial and why left and right are similar. Plz clear me this that why are we using left, up, right. answered 14 Jan '14, 01:33 1 accept rate: 0% because we will enumerate the lower bound of the "extreme matrix", and then, for given (i, j) and up[i][j], we would like to extend this vertical line to left and right as far as possible. Since the vertical height is fixed, "right[]" is similar to "left[]". We can get "right[]" in a way similar to the way of getting "left[]". (14 Jan '14, 07:41)
 0 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 154●7 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,678
×2,592
×2,169
×51

question asked: 13 Jan '14, 15:12

question was seen: 7,221 times

last updated: 22 Apr '15, 17:38