CODEWITHSUNDEEP
algorithmquery-optimizationdynamic-programmingmultidimensional-array
v78
v78

Reputation: 2933

Efficient Dynamic Programming rectangular queries in a boolean matrix

Please would anyone suggest a dynamic programming approach to solve the SPOJ problem "A STANDARD PROBLEM", link:- http://www.spoj.com/problems/ASTDPROB/

Problem statement: Given a boolean matrix of size NXM .Answer for all Q queries of type int low, high, finds the largest area sub rectangle having only Zeros and lying between rows numbered low and high. 

1 ≤ N, M ≤ 1000 
1 ≤ Q  ≤ 10^6

I need an O(n^2) or O(n^2 * log n) dp algorithm.

Up till my approach goes like this

  1. I precompute the sides of maximum sub rectangle starting each cell (i,j) in almost O(n^2) time using DP.
  2. store the answer for each query in a grid ans[M][M] (currently my doing in O(n^3)=around 10^9 atomic operations in 1s which is impossible)
  3. then answer all queries in O(1).

Please suggest any optimization for 2nd step?

Anyone with more efficient approach,please share that also.

Thanks in advance.

Upvotes: 1

Views: 867

Answers (1)

Łukasz Kidziński
Łukasz Kidziński

Reputation: 1623

Let M be the matrix of 0s and 1s.

Compute a matrix S, where S[k][l]' is the number of consecutive zeros up fromM[k][l]`. This will take O(n^2).

Now for a given query (lo,hi) you can go from line lo to line hi. And for each line line find the maximum rectangle from line to hi in following way: - go with a pointer p through the S[line] and keep track of possible heights.

For example, suppose S[line] = [1,2,2,1,5,6,9,2,1,4]. When p = 5 you should have a list of tuples like: W = [0,4,5] and from this you can compute the sizes of rectangles finishing at p==6:

max(S[line][W[0]], hi-lo+1) * (p-W[0] + 1) = 6
max(S[line][W[1]], hi-lo+1) * (p-W[1] + 1) = 10
max(S[line][W[2]], hi-lo+1) * (p-W[2] + 1) = 6

EDIT: Well, it seems there are more sophisticated solutions, at least after S is computed. You can consider it as the problem H from:

http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html

There is also a related SO question here Maximize the rectangular area under Histogram

EDIT: How to use the histogram idea.

Let M have following structure

1010100101
0001001001
0001000010
0100000000

then S can be computed bottom-up and in this case is

0301041020
3230330310
2120222202
1011111111

Now to find a rectangle starting from some line till the end we use the 'histogram problem'. For the second line we have: 3230330310 and this corresponds to the histogram of the form

X X XX X  
XXX XX X  
XXX XX XX

Finding the largest rectangle here gives the largest rectangle in the starting problem.

Complecity: O(n) - histogram algorithm. Now, for each query we check at most n lines and we have q queries so: O(n^2 q)

Upvotes: 2

Related Questions