METEORAK - Editorial

dynamic-programming
editorial
jan14
medium

#1

PROBLEM LINK:

Practice
Contest

Author: Roman Rubanenko
Tester: Mahbub
Editorialist: Jingbo Shang

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[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*[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*[j] is an obstacle:
    up*[j] = 0
else
    up*[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.

alt text

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*[j] and what we need is to calculate the horizonal boundary (left*[j], right*[j]), left and right are both exclusive. Because left and right are similar, we only focus on the left here. By the definition, left*[j] is the first column k on the left side of j, such that up*[k] is smaller than up*[j]. There are two ways to calculate the left*[li].
[/li]
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*[left[j]] >= up*[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*[stack[ptr]] > up*[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*[stack[top - 1]] >= up*[j]) {
            top = top - 1;
        }
        if (top == 0) {
            left*[j] = 0;
        } else {
            left*[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*[j] + 1]* = max{ c[i - up*[j] + 1]*, right*[j] - left*[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*[j] * (j - i + 1), d*[j - 1], d[i + 1][j]} (the bounary case is d*[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.


#2

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?


#3

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.” - :frowning:


#4

I think some drawings should be added to this editorial


#5

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


#6

O(n^2 m) passed.


#7

@shangjingbo The links to the tester and setter’s solution link back to the editorial page itself. Could you please correct the links.


#8

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.


#9

Certain O(NNM) solution have got accepted using fast input output :(.


#10

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.


#11

I used the exact approach as above but getting NZEC error (java) pls help.
http://www.codechef.com/viewsolution/3253203


#12

Similarly, we define d[l][r] as answer for corresponding query. The answer is max{c*[j] * (j - i + 1), d*[j - 1], d[i + 1][j]} (the bounary case is d*[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[][] …


#13

freopen("ip.txt","r",stdin); in C submission?


#14

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 :slight_smile:


#15

Thanks for your suggestions. I have added a figure.


#16

That’s a good question to the Problem Setter.


#17

oh really? can you share some details? It will be helpful to setter and tester to find stronger test cases I think.


#18

alt text


#19

it has been commented.and how it is going to affect the run time of the program…


#20

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.