Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

mredigonda's blog

Maximum Subsquare
By mredigonda, 10 years ago, In English

Hello, i'm an OI contestant and recently I found a lot of problems like this one:

You have a n by n matrix, each cell is either 0 or 1. Find the maximum subsquare in which all the cells are 1.

This is the classic problem, but there are a lot of variants: find the maximum rectangle, find the maximum area of two consecutive subsquares, etc.

I know a solution in O(n^3) and I know there is a solution in O(n^2) but I can't understand it, can you please explain me how it works? or give me some resource to read about it?

Also I have a particular interest in "find the maximum area of two consecutive subsquares".

It'd be great if you can help me, thanks!

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Let dp(i,j) be: The largest square sub matrix length with bottom right corner as cell (i,j).

No Try finding the link between dp(i,j) and dp(i-1,j-1) in O(1).

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

this problem can be reduced to this http://www.informatik.uni-ulm.de/acm/Locals/2003/html/histogram.html, check the explanation here http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html

for the problem of the matrix you can fix a row and run the algorithm above in a new array of size # of columns, where the entry in position i is equal to the maximum sequence of one in column i above the (r, i) entry, here r is the current row...

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi Maxi! I know you understand the problem now, but anyways here's a very good video for those who want to learn how to solve it.

https://www.youtube.com/watch?v=g8bSdXCG-lA&feature=youtu.be

It's the cuadratic solution.

→ Reply