836 - Largest Submatrix
Moderator: Board moderators
-
- 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]
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]
-
- Learning poster
- Posts: 67
- Joined: Sun Sep 22, 2002 5:40 am
- Location: Taiwan
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;
}
-
- 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...
Is there something related to floodfill + math method to solve this one?
Thanx...
Re: 836 - Largest Submatrix
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 wrote:Any idea how to solve this problem?
Is there something related to floodfill + math method to solve this one?
![:wink:](./images/smilies/icon_wink.gif)
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![:P](./images/smilies/icon_razz.gif)
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
![:P](./images/smilies/icon_razz.gif)
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.
Re: 836 - Largest Submatrix
Never mind, I forgot to put a blank line between two cases.
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
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
Are you dreaming right now?
http://www.dreamviews.com
Re: 836 - Largest Submatrix
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: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]...
sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1]
836 Largest Submatrix
I got WA all the time , Please someone tell my why, thx
here is my code:
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;
}