836 - Largest Submatrix

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

836 - Largest Submatrix

Post by Ghost77 dimen » Sun Sep 29, 2002 4:34 am

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]

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

Post by cytse » Wed Oct 09, 2002 6:34 pm

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

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

Post by Ghost77 dimen » Sat Oct 12, 2002 3:37 pm

cytse , thanks a lot.

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

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

Post by yahoo » Sun Mar 02, 2003 10:39 pm

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




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

836 - Largest Submatrix

Post by Roby » Fri Nov 11, 2005 6:17 am

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

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

Re: 836 - Largest Submatrix

Post by angga888 » Fri Nov 11, 2005 7:41 am

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). :wink:

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

Post by Roby » Fri Nov 11, 2005 10:37 am

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
Location: Bangladesh
Contact:

Post by mamun » Fri Nov 11, 2005 1:46 pm

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

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

Post by angga888 » Fri Nov 11, 2005 2:32 pm

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

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

Post by Roby » Sat Nov 12, 2005 2:02 pm

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

Post by snail.123 » Sun May 04, 2008 4:26 pm

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

Post by snail.123 » Wed May 07, 2008 2:53 pm

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

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

Re: 836 - Largest Submatrix

Post by andmej » Wed Jul 23, 2008 6:20 am

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

Post by stcheung » Wed Sep 10, 2008 6:30 am

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
New poster
Posts: 1
Joined: Sat Nov 21, 2009 6:31 pm

836 Largest Submatrix

Post by icnivad » Mon Nov 23, 2009 9:06 am

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

Post Reply

Return to “Volume 8 (800-899)”