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

miollnyr
New poster
Posts: 2
Joined: Mon Feb 08, 2010 8:44 pm

Re: 836 Largest Submatrix

Post by miollnyr » Tue Feb 09, 2010 5:30 pm

Can anybody take a look what is wrong with my code or provide some inputs?:)

Code: Select all

#include <iostream>
#include <vector>
#include <string>

using namespace std;

typedef vector<bool> line;
typedef vector<line> matrix;

int size = 0;

istream& operator>>(istream& in, line& L)
{
	string str;
	int i;

	in >> str;

	size = str.size();

	for(i = 0; i < size; ++i)
	{
		L[i] = (str[i] == '1');
	}

	return in;
}

int func(const matrix& m)
{
	int i, j, p, k, columns, ret = 0, curr;

	for(i = 0; i < size; ++i)
	{
		for(j = 0; j < size; ++j)
		{
			if(m[i][j] && ret < (size - i)*(size - j))
			{
				curr = 0;
				p = i;
				k = j;
				columns = size;
				
				for(p = i; p < size && m[p][j]; ++p)
				{
					for(k = j ; k < columns && m[p][k]; ++k);
					
					if(k < columns)
					{
						columns = k;
					}										
					curr = max(curr, (p - i + 1) * (k - j));					
				}
				
				ret = max(curr, ret);
			}
		}
	}

	return ret;
}

int main()
{
	int num, i;
	matrix m(25);

	for(i = 0; i < 25; ++i)
	{
		m[i].resize(25);
	}

	cin >> num;

	while(num--)
	{
		cin >> m[0];

		for(i = 1; i < size; ++i)
		{
			cin >> m[i];
		}
		
		cout << func(m) << (num == 0 ? "" : "\n\n");
	}

	return 0;
}
The idea is simple:
I start with cell with 1 and find the largest line with 1's - this is curr, size of line is columns
Then I start from the next line and find the largest line with ones with size <= columns (I am looking for rectangles), and curr = max(curr, size of new rect)
And so on, until the next line contains 1's.

But I get WA all times. Please notice that I have solved 108 - Maximum sums :)

sir. manuel
New poster
Posts: 18
Joined: Sat Nov 20, 2010 7:44 pm

836.-Largest submatrix

Post by sir. manuel » Sat Nov 20, 2010 7:55 pm

Hi, this is my first post, i can´t write english fine, so you have to be patient...

I´m trying to solve the problem 836,,,i use DP,,,the test cases that i input to my solution it´s fine,,,but when i send to the judge i got WA...
I don´t can see my error...can you help me???

Code: Select all

ACCEPTED
I did a stupid error,,,

The idea is the same that the problem 108(maximum sum),,,but in this problem, i chance '0' for '-1000', and '1' to 1, and use the code of 108...

triker
New poster
Posts: 5
Joined: Tue Apr 19, 2005 9:56 am

836 - Largest Submatrix

Post by triker » Sun Jun 12, 2011 1:39 am

I got WA in this problem.
I changed 0 to -1000 and used the same code as 108. (I solved 108).

I have no idea what's wrong. Would you please give the test case that could be incorrect with my code.
Or find out what's wrong with my code?

Please help me.

Code: Select all

remove after ac
Here's my test cases

Code: Select all

6

111000
111111
111111
111111
111111
011110

11
01

10111000
00010100
00111000
00111010
00111111
01011110
01011110
00011110

1010
0101
1010
0101

0000
0000
0000
0000

111
111
111
and output

Code: Select all

24

2

16

1

0

9
Edit: The problem was wrong output format. I had one more blank line at the last output.

amin__
New poster
Posts: 10
Joined: Thu Jul 01, 2010 10:44 am

Re: 836 Largest Submatrix

Post by amin__ » Tue Aug 16, 2011 10:59 pm

hello can anybody help me ??? I am getting repeatedly Runtime Error in my code...please help..
here is my code


#include<cstdio>
#include<cstring>

int main()
{
long T,i,j,k,l,len,len1,max,val,m,n;
int grid[100][100];
char str[100000];

scanf("%ld",&T);
getchar();
getchar();
//getchar();

for(i=0;i<T;i++)
{
k=0;
//getchar();
while(1)
{
//scanf("%[^\n]",str);

gets(str);

len=strlen(str);
//if(k==0) len1=len;
if(len==0) break;
for(j=0;j<len;j++)
{
grid[k][j]=str[j]-'0';
}
k++;
}
len1=k;

//printf("%ld %ld\n",k,len1);

/*for(j=0;j<k;j++)
{
for(l=0;l<len1;l++)
{
printf("%ld ",grid[j][l]);
}
printf("\n");
}*/

for(j=0;j<k;j++)
{
for(l=0;l<len1;l++)
{
if(j-1>=0 && l-1>=0)
grid[j][l]+=(grid[j-1][l]+grid[j][l-1]-grid[j-1][l-1]);
else if(j-1>=0)
grid[j][l]+=(grid[j-1][l]);
else if(l-1>=0)
grid[j][l]+=(grid[j][l-1]);
}
}



//printf("\n\n");

max=0;
for(j=0;j<k;j++)
{
for(l=0;l<len1;l++)
{
for(m=j;m<k;m++)
{
for(n=l;n<len1;n++)
{
if(j-1>=0 && l-1>=0)
{
val=(grid[m][n]-grid[j-1][n]-grid[m][l-1]+grid[j-1][l-1]);
}
else if(j-1>=0)
{
val=(grid[m][n]-grid[j-1][n]);
}
else if(l-1>=0)
{
val=(grid[m][n]-grid[m][l-1]);
}
else val=grid[m][n];

//printf("%ld %ld\n\n",val,((n-l)+1)*((m-j)+1));
if(val==((n-l)+1)*((m-j)+1))
{
if(max<((n-l)+1)*((m-j)+1))
{

//printf("%ld %ld\n\n",val,((n-l)+1)*((m-j)+1));
//printf("%ld %ld %ld %ld\n",j,l,m,n);
max=((n-l)+1)*((m-j)+1);
}
}
}
}
}
}
if(i) printf("\n");
printf("%ld\n",max);
//if(i<T-1)
//getchar();

//printf("%ld %ld\n",k,len);

/*for(l=0;l<k;l++)
{
for(j=0;j<len1;j++)
{
printf("%ld",grid[l][j]);
}
printf("\n");
}*/
}

//scanf("%ld",&i);
return 0;
}


:(

shoos099
New poster
Posts: 1
Joined: Wed Jun 14, 2017 9:32 pm

Re: 836 - Largest Submatrix

Post by shoos099 » Tue Aug 08, 2017 1:34 am

Hi everyone. I have tested my soulution to this problem with the datasets provided at uDebug (https://www.udebug.com/UVa/836) and it produces the correct output. But I get WA when I sublit. Could anyone help me what's wrong?

Code: Select all

#include <iostream>
#include <algorithm>
using namespace std;
//input matrix
#define MAX 25
int A[MAX][MAX]; //current matrix
int N; //size of the matrix

int M[MAX][MAX]; //keep track

void addMatrix(string s, int linenum) {
    N = s.size();
    for (int c = 0; c < s.size(); c++)
        A[linenum - 1][c] = s[c] - '0';
}

int sumSubMatrix(int i1, int j1, int i2, int j2) {
    int left, top , corner;
    left = top = corner = 0;
    int sum = 0;
    if (i1 != 0)
        top = M[i1 - 1][j2];
    if (j1 != 0)
        left = M[i2][j1 - 1];
    if (i1 != 0 && j1 != 0)
        corner = M[i1 - 1][j1 - 1];
    sum = M[i2][j2] - top - left + corner;
}

int findMaxSub() {
    //first row
    M[0][0] = A[0][0];
    for (int c = 1; c < N; c++)
        M[0][c] = M[0][c - 1] + A[0][c];
    //first column
    for (int r = 1; r < N; r++)
        M[r][0] = M[r - 1][0] + A[r][0];
    //other rows and columns
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < N; j++) {
            M[i][j] = M[i - 1][j] + M[i][j - 1] - M[i - 1][j - 1] + A[i][j];
        }
    }

    //search all submatrixs
    int max = 0, cur;
    for (int i1 = 0; i1 < N; i1++)
        for (int i2 = i1; i2 < N; i2++)
            for (int j1 = 0; j1 < N; j1++)
                for (int j2 = j1; j2 < N; j2++) {
                    cur = sumSubMatrix(i1, j1, i2, j2);
                    bool full1 = cur == (i2 - i1 + 1) * (j2 - j1 + 1);
                    if (cur > max && full1) {
                        max = cur;
                    }
    }
    return max;
}

int main() {
  int ncases;
  cin >> ncases;

  string s;
  getline(cin, s);
  getline(cin, s);
  int linenum = 0;
  for (int i = 1; i <= ncases; i++) {

    while (getline(cin, s) && !s.empty()) {
        linenum++;
        addMatrix(s, linenum);
    }


       if (i != 1)
        {
            cout << endl;
        }

        cout << findMaxSub() << endl;


    linenum = 0;
  } //next case
    return 0;
}

Post Reply

Return to “Volume 8 (800-899)”