wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> MATRIX
        
(Message started by: rahul_832 on Feb 11^th, 2009, 7:24am)

Title: MATRIX
Post by rahul_832 on Feb 11^th, 2009, 7:24am

For any matrix MxN, find the largest submatrix which contains elements in decreasing order from left to right and top to bottom.

Ex.

6 23 19 17 18
4 22 18 15 20
26 20 15 13 21
19 32 34 12 45

Ans:

23 19 17
22 18 15
20 15 13

Title: Re: MATRIX
Post by towr on Feb 11^th, 2009, 7:37am

I think dynamic programming might work out.
Form the bottom right, working up to the right find for each position the largest sub-matrix you can form starting with that position as the top left corner. (Assuming that by submatrix you mean a contiguous part of the matrix, i.e. not skipping columns and rows)

Title: Re: MATRIX
Post by howard roark on Feb 11^th, 2009, 10:59am

on 02/11/09 at 07:37:35, towr wrote:

How about finding largest sub matrix with each element as the bottom right of that matrix,

a[i][j] = min(a[i][j-i],a[i-1][j-1],a[i-1][j]) + 1 iff

A[i][j]>A[i][j-1]&& A[i][j]>A[i-1]&&[j-1]A[i][j]>A[i-1][j]

Title: Re: MATRIX
Post by towr on Feb 11^th, 2009, 2:03pm

Same diff, as long as you start on the opposite side.
And you can try the two remaining corners as well.

Title: Re: MATRIX
Post by Hippo on Feb 11^th, 2009, 2:17pm

on 02/11/09 at 10:59:25, howard roark wrote:

What should the a[i][j] contain? Area of the rectangle?
What about the case a[i][j-1]=6x4, a[i-1][j-1]=5x5, a[i-1][j]=4x6, and a[i][j]=1x73?

It would be easier not to thing about the numbers but to draw "forbidden edges", the edges which cannot be inside the resulting rectangle. So suppose only the edge positions are given, find the maximal rectangle not containing any of the forbidden edges.

Code:

6 | 23 19 17 | 18
--
4 22 18 15 | 20
-- --
26 20 15 13 | 21
-- -- --
19 | 32 | 34 12 | 45

I dont thing you can use dynamic programing here without maintaining whole set of maximal rectangles with given corner. That lead to O(n³) for a square matrix of side n.

Title: Re: MATRIX
Post by howard roark on Feb 11^th, 2009, 4:49pm

Yeah........I actually thought question was to find maximum square sub matrix....

Title: Re: MATRIX
Post by howard roark on Feb 11^th, 2009, 5:32pm

on 02/11/09 at 14:17:35, Hippo wrote:

I dont thing you can use dynamic programing here without maintaining whole set of maximal rectangles with given corner. That lead to O(n³) for a square matrix of side n.

If it is not possible to write a n^2 solution. Can you explain a n^3 solution

Title: Re: MATRIX
Post by Hippo on Feb 12^th, 2009, 2:09pm

There is planty of O(n³) solutions.
For example for each height h find by dynamic programming maximal rectangle with high h.

Title: Re: MATRIX
Post by miletus on Feb 13^th, 2009, 2:01am

For each element A[i][j], if the 4-element matrix
( A[i][j], A[i+1][j], A[i][j+1], A[i+1][j+1] ) is a valid sub-matirx,
then denote B[i][j] = 1, otherwise B[i][j] = 0. All B[i][N] and B[M][j] = 0.

Then the problem is equal to finding the maximal
sub-matrix in B whose element are all 1's.
If such sub-matrix in B is m*n, then the largest
sub-matrix in A is (m+1)*(n+1).

Finding the largest sub-matrix containing all 1's
can be done in O(M*N), I think.