You are not logged in. Please login at www.codechef.com to post your questions!

×

METEORAK - Editorial

12
2

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

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[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".

asked 13 Jan '14, 15:12

shangjingbo's gravatar image

3★shangjingbo ♦♦
161446375
accept rate: 0%

edited 22 Apr '15, 17:38

admin's gravatar image

0★admin ♦♦
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." - :(

link

answered 13 Jan '14, 15:44

nitinj's gravatar image

5★nitinj
2.2k112027
accept rate: 5%

edited 13 Jan '14, 15:45

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) shangjingbo ♦♦3★

Thanks mate :) ..much appreciated

(13 Jan '14, 20:20) nitinj5★
1

my pleasure to help you :D

(13 Jan '14, 22:43) shangjingbo ♦♦3★
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.

link

answered 13 Jan '14, 21:18

laxman94's gravatar image

3★laxman94
1.2k31515
accept rate: 6%

edited 23 Jan '14, 22:51

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?

link

answered 13 Jan '14, 15:27

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

That's a good question to the Problem Setter.

(13 Jan '14, 18:47) shangjingbo ♦♦3★
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★

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

link

answered 13 Jan '14, 20:46

kcahdog's gravatar image

3★kcahdog
10.0k2854129
accept rate: 14%

Indeed, I am still waiting for Suraj to give me the links too...

(13 Jan '14, 22:47) shangjingbo ♦♦3★

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[][] ...

link

answered 14 Jan '14, 18:08

pratikjain1993's gravatar image

2★pratikjain1993
162
accept rate: 0%

I think some drawings should be added to this editorial

link

answered 13 Jan '14, 16:55

ahmed1ossama13's gravatar image

4★ahmed1ossama13
21218
accept rate: 0%

1

Thanks for your suggestions. I have added a figure.

(13 Jan '14, 18:46) shangjingbo ♦♦3★

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

link

answered 13 Jan '14, 17:24

hatim009's gravatar image

3★hatim009
46421122
accept rate: 8%

1

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

(13 Jan '14, 17:27) betlista ♦♦3★

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) betlista ♦♦3★

O(n^2 m) passed.

link

answered 13 Jan '14, 17:50

ivan100sic's gravatar image

6★ivan100sic
10514
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) shangjingbo ♦♦3★
10

alt text

(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) ivan100sic6★

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) shangjingbo ♦♦3★

No, there are three nested for-loops clearly visible in inline void racunajsol()

(13 Jan '14, 19:54) ivan100sic6★

wait, I see a totally different solution than what I read before.... let me have a look

(13 Jan '14, 22:45) shangjingbo ♦♦3★

okay, you are right. thanks to the weak test cases and relax time limit.

(13 Jan '14, 22:47) shangjingbo ♦♦3★
showing 5 of 7 show all

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

link

answered 13 Jan '14, 22:02

nivin's gravatar image

4★nivin
1113
accept rate: 0%

add link please ;-)

(13 Jan '14, 22:04) betlista ♦♦3★
1

similar algorithm to @ivan100sic?

(13 Jan '14, 22:48) shangjingbo ♦♦3★

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.

link

answered 14 Jan '14, 01:33

killcode1234's gravatar image

2★killcode1234
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) shangjingbo ♦♦3★

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

link

answered 14 Jan '14, 01:54

siddhartha4444's gravatar image

3★siddhartha4444
1547
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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