836 - Largest Submatrix

[Ghost77 dimen]

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]

I haven't read your program. But what is your output if there are no '1's?

[Ghost77 dimen]

cytse , thanks a lot.

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

[yahoo]

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]

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

[angga888]

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]

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]

Yes, if you can solve 108 you can solve this too. It's a dynamic problem.

[angga888]

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]

Thanx Angga, I'll try the method you mentioned above... and thanx also for mamun for the reply.

[snail.123]

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

[snail.123]

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

[andmej]

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

[stcheung]

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]

[icnivad]

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;
}