## 836 - Largest Submatrix

Moderator: Board moderators

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

### 836 - Largest Submatrix

As you con see, there is no doubt that 836 is a simple question.

But I still got wrong answer again,would you like give me some hints about my wrong code?Thanks a lot.

[cpp]#include<stdio.h>

void main(void)
{
int t;
int s[26][26];
int m[26][26];
char l;
int u,v,i,j,keep,max;
//freopen("input.txt","r",stdin);
scanf("%d\n",&t);
while(t>0)
{
for(u=0;u<26;u++)
{
s[0]=0;
s[0]=0;
}
keep=2;
for(u=1;u<=keep;u++)
{
for(v=1;v<27;v++)
{
scanf("%c",&l);
if(l=='\n')
{
keep=v-1;
break;
}
else if(l=='0')
{
s[v]=0;
}
else if(l=='1')
{
s[v]=1;
}
}
}

for(u=0;u<=keep;u++)
{
for(v=0;v<=keep;v++)
{
m[v]=0;
}
}

for(u=0;u<26;u++)
{
for(v=0;v<26;v++)
{
for(i=1;i<=keep;i++)
{
for(j=1;j<=keep;j++)
{
if(i>=u&&j>=v)
{
m[j]+=s[v];
}
}
}
}
}
/*for(u=0;u<=keep;u++)
{
for(v=0;v<=keep;v++)
{
printf("(%d,%d)=%d ",u,v,m[v]);
}
}*/
max=0;

for(u=1;u<=keep;u++)
{
for(v=1;v<=keep;v++)
{
for(i=u;i<=keep;i++)
{
for(j=v;j<=keep;j++)
{
if(m[u-1][v-1]+m[j]-m[u-1][j]-m[v-1]==(i-u+1)*(j-v+1)||m[u-1][v-1]+m[j]-m[u-1][j]-m[v-1]==0)
{
if((i-u+1)*(j-v+1)>max)
{
max=(i-u+1)*(j-v+1);
//printf(" %d %d %d %d \n",u,v,i,j);
}
}
}
}
}
}

printf("%d\n\n",max);
if(t!=1)
{
scanf("\n");
}
t--;
}
}[/cpp]

cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan
cytse , thanks a lot.

I have missed one line of the description , and I got A.C. with your help.

yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am
I can't understand why i got wrong answer. Will anybody check my code or give me some input to check myself. Here is my code.

Code: Select all

#include <stdio.h>
#include<string.h>

main()
{

long tab[100];
long m, mini, wynik, n, k, znak, p, x, l, i;
long FORLIM, FORLIM1,flag;
int cases,qw,a[50][50],j;
freopen("c:\\in.txt","r",stdin);
char ch[100];
scanf("%d",&cases);
for(qw=0;qw<cases;qw++)
{
if(qw) printf("\n");
scanf("%s",ch);
m=n=strlen(ch);
for(i=0;i<m;i++) a[0][i]=ch[i]-'0';
for(i=1;i<m;i++)
{
scanf("%s",ch);
for(j=0;j<m;j++) a[i][j]=ch[j]-'0';
}
flag=0;  wynik=0;
for(i=0;i<m;i++)
for(j=0;j<m;j++)
if(a[i][j]==1) {flag=1;break;}
if(flag)
{
wynik = 0;
FORLIM = m;
for (i = 1; i <= FORLIM; i++) {
tab[i-1] = 0;
}
if (n != 0) {
FORLIM = n;
for (i = 1; i <= FORLIM; i++) {
FORLIM1 = m;
for (k = 1; k <= FORLIM1; k++) {
mini=a[i][k];
if(mini==1) mini=0;else mini=1;
if (mini == 1) {
tab[k-1] = 0;
} else {
tab[k-1]++;
}
}
FORLIM1 = m;
for (k = 1; k <= FORLIM1; k++) {
if (tab[k-1] > 0) {
l = k + 1;
mini = 1000;
while (l > 1 && tab[l-2] > 0) {
l--;
if (tab[l-1] < mini)
mini = tab[l-1];
if (mini * (k - l + 1) > wynik)
wynik = mini * (k - l + 1);
}
}
}
}
}
}
if(m!=0 &n!=0)
printf("%ld\n", wynik);
}
return 0;
}



Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

### 836 - Largest Submatrix

Any idea how to solve this problem?
Is there something related to floodfill + math method to solve this one?
Thanx...

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

### Re: 836 - Largest Submatrix

Roby wrote:Any idea how to solve this problem?
Is there something related to floodfill + math method to solve this one?
I don't know about how to solve this problem using floodfill+math, but you can try to use the same algorithm as problem 108 (Maximum Sum).

Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:
Thanx Angga...
But I haven't try problem #108 so I don't know how to solve it...
Is it related to LCS, I mean the way to find the match one?

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
Yes, if you can solve 108 you can solve this too. It's a dynamic problem.

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
Here is the hint:

Let sum[row][col] be the summation of all elements from the top left corner of the matrix (0,0) up to the (row, col) position.
If you want to count the summation of elements between position (x1,y1) and (x2,y2) where x1<x2 and y1<y2, then you only need to calculate sum[x2][y2]-sum[x1-1][y1-1].
Now, to check whether a given range (x1,y1) up to (x2,y2) is a rectangle full of '1', you only need to check whether sum[x2][y2]-sum[x1-1][y1-1] is equal to (x2-x1+1)*(y2-y1+1).

Hope it helps

Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:
Thanx Angga, I'll try the method you mentioned above... and thanx also for mamun for the reply.

snail.123
New poster
Posts: 14
Joined: Wed Jun 13, 2007 3:29 am
Location: Taiwan

### Re: 836 - Largest Submatrix

I used Angga's algo but got WA. Can anyone tell me what went wrong with my code? Or give me some critical input to test. Thanks a lot!

Code: Select all

Deleted after AC
Last edited by snail.123 on Wed May 07, 2008 2:54 pm, edited 1 time in total.

snail.123
New poster
Posts: 14
Joined: Wed Jun 13, 2007 3:29 am
Location: Taiwan

### Re: 836 - Largest Submatrix

Never mind, I forgot to put a blank line between two cases.

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### Re: 836 - Largest Submatrix

I solved this problem using the O(n^4) algorithm described above.
I was wondering if it is possible to solve this in O(n^3). Any idea?

Edit: Yes, it is possible to solve this in O(n^3) (although O(n^4) is enough for n = 25) like this:
For every pair of rows i, j (i <= j) make a row r containing the sum of elements of rows i through j. Notice that if the solution were included in the submatrix formed by these rows, then r would have a consecutive sequence of equal numbers (because all previous rows must have only ones so respective sums should be all the same) such that the area formed by the submatrix that goes from rows i through j and from the start to the end of the consecutive sequence must be maximal. This last part can be checked in O(n).

Let me explain with an example. Given the matrix:
1 1
0 1

We only have three possibilities for a pair (i, j) that are (1,1), (1,2), (2,2):
For the pair (1,1) we have r = [1, 1]
We only have a sequence of consecutive equal elements (whose sum its equal to the area from (1,1) to (2,2)), so the best answer so far is 2.

For the pair (1,2) we have r = [1, 2]
We have two distinct sequences, only the sum of the second sequence equals its area (from (1,2) to (2,2)) so the answer is also 2.

For the last pair (2,2) we have r = [0, 1]
which are all smaller than the maximum found answer. So the total answer is 2.

Here's some tricky case:
1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

### Re: 836 - Largest Submatrix

Let sum[row][col] be the summation of all elements from the top left corner of the matrix (0,0) up to the (row, col) position.
If you want to count the summation of elements between position (x1,y1) and (x2,y2) where x1<x2 and y1<y2, then you only need to calculate sum[x2][y2]-sum[x1-1][y1-1]...
This insight was very helpful indeed (thanks). However, I don't think sum[x2][y2]-sum[x1-1][y1-1] is the correct formula for doing what was intended here. This is what I have instead:
sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1]

New poster
Posts: 1
Joined: Sat Nov 21, 2009 6:31 pm

### 836 Largest Submatrix

I got WA all the time , Please someone tell my why, thx

here is my code:
#include<stdio.h>
#include<string.h>
#define MAX 25
char Matrix[MAX][MAX],buffer[MAX+2];
int up[MAX],right[MAX],left[MAX];
int N,Cases,max_value,value;
int min(int a,int b){if(a>=b)return b;return a;}
int main(){
int i,j,k,l;
scanf("%d",&Cases);
while(Cases--){
//input
scanf("%s",buffer);
N=strlen(buffer);
for(j=0;j<N;j++)Matrix[0][j]=buffer[j];
for(i=1;i<N;i++){
scanf("%s",buffer);
for(j=0;j<N;j++)
Matrix[j]=buffer[j];
}
//initialize
max_value=0;
for(i=0;i<N;i++){
up=0;
right=N+1;
left=N+1;
}
//practice the algorithm O(N^2)
for(i=0;i<N;i++){
for(j=0,k=0,l=0;j<N;j++){
if(Matrix[j]=='1'){
up[j]+=1;
left[j]=min(++k,left[j]);
}
else{
up[j]=0;
left[j]=j+1;k=0;
}
if(Matrix[N-j-1]=='1')
right[N-j-1]=min(++l,right[N-j-1]);
else{right[N-j-1]=j+1;l=0;}
}
for(j=0;j<N;j++){
if(Matrix[j]=='1'){
value=up[j]*(left[j]+right[j]-1);
if(value>max_value)max_value=value;
}
}
}
printf("%d",max_value);
if(Cases>0)printf("\n\n");
}
return 0;
}