Author |
Topic: MATRIX (Read 825 times) |
|
rahul_832
Newbie
Gender: 
Posts: 18
|
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
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
 |
Re: MATRIX
« Reply #1 on: Feb 11th, 2009, 7:37am » |
 Quote  Modify
|
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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
howard roark
Full Member
Posts: 241
|
|
Re: MATRIX
« Reply #2 on: Feb 11th, 2009, 10:59am » |
Quote Modify
|
on Feb 11th, 2009, 7:37am, towr wrote: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) |
|
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]
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: MATRIX
« Reply #3 on: Feb 11th, 2009, 2:03pm » |
Quote Modify
|
Same diff, as long as you start on the opposite side.
And you can try the two remaining corners as well.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: MATRIX
« Reply #4 on: Feb 11th, 2009, 2:17pm » |
Quote Modify
|
on Feb 11th, 2009, 10:59am, howard roark 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] |
|
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(n3) for a square matrix of side n.
|
| « Last Edit: Feb 11th, 2009, 2:38pm by Hippo » |
IP Logged |
|
|
|
howard roark
Full Member
Posts: 241
|
|
Re: MATRIX
« Reply #5 on: Feb 11th, 2009, 4:49pm » |
Quote Modify
|
Yeah........I actually thought question was to find maximum square sub matrix....
|
| « Last Edit: Feb 11th, 2009, 4:50pm by howard roark » |
IP Logged |
|
|
|
howard roark
Full Member
Posts: 241
|
|
Re: MATRIX
« Reply #6 on: Feb 11th, 2009, 5:32pm » |
Quote Modify
|
on Feb 11th, 2009, 2:17pm, 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(n3) 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
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: MATRIX
« Reply #7 on: Feb 12th, 2009, 2:09pm » |
Quote Modify
|
There is planty of O(n3) solutions.
For example for each height h find by dynamic programming maximal rectangle with high h.
|
|
IP Logged |
|
|
|
miletus
Newbie
Posts: 4
|
|
Re: MATRIX
« Reply #8 on: Feb 13th, 2009, 2:01am » |
Quote Modify
|
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.
|
| « Last Edit: Feb 13th, 2009, 2:02am by miletus » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print