1

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.

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
v78
  • 2,803
  • 21
  • 44
  • 1
    this is a possible duplicate of http://stackoverflow.com/questions/20937580/maximum-area-of-rectangle-without-any-monsters. moreover step one could be done faster with divide&conquer and i think it could be combined with 2nd step as well. – rostok Jan 07 '14 at 21:33
  • 1
    Please, elaborate how the solution of @M Oehm help in answering queries . Also please share your approach of combining step 1 and step 2. – v78 Jan 08 '14 at 02:50
  • @rostok Could you give your idea,please. – v78 Jan 09 '14 at 07:00
  • sorry. i wanted to suggest sth similar to M Oehm that involves recursive search but since we do not know the number of 1s Lukasz's idea is more predictable. note that you can have two algorithms and execute them based on number of 1s from the input. – rostok Jan 09 '14 at 18:12
  • you mean when number of ones are large then Lukasz's idea is better because height of histograms is less. and when matrix is sparse then then M ohem' s algo is correct . Am I right? – v78 Jan 09 '14 at 18:17
  • yes this is exactly what i meant. – rostok Jan 09 '14 at 18:20
  • one more thing: in worst case scenario Q=M*N. so precalculating all the possible answers is unnecessary. it is better to cache results based on input and reuse them in case low/high parameters are passed several times. – rostok Jan 09 '14 at 18:23
  • I solved the problem using only Lukasz's idea in c++, It passed test cases and is very optimized one in inputs etc. But the there are users who solved it in almost one-fourth time. – v78 Jan 09 '14 at 18:25
  • can you post the best solution? – rostok Jan 12 '14 at 12:06

1 Answers1

2

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)

Community
  • 1
  • 1
Łukasz Kidziński
  • 1,613
  • 11
  • 20
  • 1
    Please give some idea how to use the Histogram problem here. And also about your solution. 1.i think you are trying to calculate the maximum probable sides of rectangle here. 2.each query is consuming O(n^2) time and with memoization we can do it it for all queries in O(n^3) time but still it is slow. – v78 Jan 08 '14 at 03:02
  • 1
    O K .now i understand and one thing more, also with dp we can answer in O(n*q) time by creating a matrix[N][N] but still it means around 10^9 operations which beyond the time limit.Can it be done in O(q* log n). Thank you for clearing me the algorithm so nicely. – v78 Jan 08 '14 at 09:44
  • 1
    You can implement [this](http://www.cs.princeton.edu/~chazelle/pubs/ComputLargestEmptyRectangle.pdf). It gives O(qn log^3 n). – Łukasz Kidziński Jan 08 '14 at 17:31