OJ Board

Posted: **Mon Aug 16, 2004 4:59 pm**

Well, that sux; the pdf-version and the html-version should be the same. Maybe you can notify the judges so they can fix it.

I remember reading somewhere that there are two types of programmers: programmers that think iteratively, and programmers that think recursively when they are trying to concieve an algorithm. The second type (to which I also belong) seems to be in the minority.

Posted: **Mon Aug 16, 2004 7:52 pm**

little joey wrote: I remember reading somewhere that there are two types of programmers: programmers that think iteratively, and programmers that think recursively when they are trying to concieve an algorithm. The second type (to which I also belong) seems to be in the minority.

And the majority of this minority are more mathematicians then progreammers

Posted: **Wed Aug 18, 2004 8:18 am**

I am getting P.E. for this problem. I wish some of these problems would explicitly specify where you are supposed to put newlines. ^^; I have tried always putting two newlines after a test case, as well as putting two newlines after each test case but only one newline after the last one, but both got P.E.

Does anyone know what you're supposed to do ?

Posted: **Thu Sep 16, 2004 10:53 am**

The following code returns WA:

[cpp]
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

//functor for solving the problem
struct Solve
{
int *a, *b;
int lena, lenb;
int dynLen[200][200];

int operator() (int *A, int la, int *B, int lb)
{
lena = la;
lenb = lb;
a = A;
b = B;
//initialise DP table
for(int i=0; i<lena; i++)
for(int j=0; j<lenb; j++)
dynLen[j] = -1;

return length(0, 0);
}

int length(int x, int y)
{
if (dynLen[x][y] != -1)
return dynLen[x][y];
if (x >= lena || y >= lenb)
return 0;

//algorithm is here...
if (a[x] == b[y])
return dynLen[x][y] = 1 + length(x+1, y+1);
else
return dynLen[x][y] = max(length(x, y+1), length(x+1, y));
}
} solve;

int main(int argc, char **argv)
{
for(int j=1;;j++)
{
int a[200], b[200];
int lena, lenb;
scanf("%d %d", &lena, &lenb);
if (lena==lenb && lena == 0)
exit(0);

for (int i=0; i<lena; i++)
scanf("%d", a+i);
for (int i=0; i<lenb; i++)
scanf("%d", b+i);

if (j>1)
puts("");

printf("Twin Towers #%d\nNumber of Tiles : %d\n", j, solve(a, lena, b, lenb));
}
}
[/cpp]

I don't see why ... is there anything obvious I'm missing? Your help is really appreciated...

Posted: **Thu Sep 16, 2004 11:20 am**

Argh how silly am I

Should have done the bound check BEFORE the dynamic one hehehe... silly me.

Posted: **Wed Jul 06, 2005 10:42 pm**

I am wondering what's wrong with my program. I coded it rather quickly but then I kept getting WA. I checked multiple times. Also checked with test cases.

Would somebody be kind enough to see what's the bug in it and if possible kindly offer some test cases? Thanks...

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

int main(){
    int z=1, i, j, k, n, m;
    int c[2][100];
    int s1[100], s2[100];
    bool start = true;
    while ( scanf("%d %d",&n,&m) == 2 ){
        if ( n == 0 && m == 0 ) break;
        if ( start ) start = false ; else puts("");
        fill(s1,s1+100,0);
        fill(s2,s2+100,0);
        for ( i=0; i<n; i++ )
            scanf("%d",&s1[i]);
        for ( j=0; j<m; j++ )
            scanf("%d",&s2[j]);
        for ( j=0; j<=m; j++ )
            c[0][j] = 0;
        c[1][0] = 0;
        for ( i=1; i<=n; i++ ){
            for ( j=1; j<=m; j++ ){
                if ( s1[i-1] == s2[j-1] )
                    c[1][j] = c[0][j-1] + 1;
                else if ( c[0][j] >= c[1][j-1] )
                    c[1][j] = c[0][j];
                else
                    c[1][j] = c[1][j-1];
            }
            for ( k=1; k<=m; k++ )
                c[0][k] = c[1][k];
            c[1][0] = 0;
        }
        if ( n > 0 && m > 0)
            printf("Twin Towers #%d\nNumber of Tiles : %d\n",z++,c[1][m]);
        else
            printf("Twin Towers #%d\nNumber of Tiles : %d\n",z++,c[0][m]);
    }
    return 0;
}

Test case as follows :

Code: Select all

7 6
20 15 10 15 25 20 15
15 25 10 20 15 20
8 9
10 20 20 10 20 10 20 10
20 10 20 10 10 20 10 10 20
10 0
10 20 30 40 50 60 70 80 90 100

0 1
 
50
1 1
50
40
4 4
10 30 40 50
50 40 10 40
1 1
100
100
1 1
100
90
2 1
1 20
3
2 2
2 2
2 1
0 0

OUTPUT is as follows :

Code: Select all

Twin Towers #1
Number of Tiles : 4

Twin Towers #2
Number of Tiles : 6

Twin Towers #3
Number of Tiles : 0

Twin Towers #4
Number of Tiles : 0

Twin Towers #5
Number of Tiles : 0

Twin Towers #6
Number of Tiles : 2

Twin Towers #7
Number of Tiles : 1

Twin Towers #8
Number of Tiles : 0

Twin Towers #9
Number of Tiles : 0

Twin Towers #10
Number of Tiles : 1

Posted: **Fri Jun 01, 2007 5:18 pm**

Give me more cases.
I need more cases. \=皿=/

Posted: **Fri Jun 01, 2007 5:40 pm**

I think it's a straight forward LCS problem. Can't think of any critical case. So, you can post your code ( and use code tags ).

Posted: **Wed Jun 06, 2007 10:50 am**

[code]#include <string.h>
#include <stdio.h>
#include <stdlib.h>

int lcs( int[], int[]);
int len[101][101];
int lenth ,n_1, n_2, i, j;

int main()
{
int str1[101] ;
int str2[101] ;
int p = 0;
while(1)
{
p++;

scanf("%d %d",&n_1,&n_2);

if(n_1 == 0 && n_2 == 0)
break;

for(i=0;i<n_1;i++)
scanf("%d",&str1[i]);

for(i=0;i<n_2;i++)
scanf("%d",&str2[i]);

lenth = lcs(str1,str2);

printf("Twin Towers #%d\n",p);
printf("Number of Tiles : %d\n",lenth);
printf("\n");
}

return 0;
}

int lcs(int a[], int b[])
{
int i, j;

for(i=0;i<=n_1;i++)
len[i][0] = 0;
for(j=0;j<=n_2;j++)
len[0][j] = 0;

len[0][0] = 0;

for(i=1;i<=n_2;i++)
for(j=1;j<=n_1;j++)
{
if(a[i-1] == b[j-1])
{
len[i][j] = len[i-1][j-1] + 1;

}
else
{
if(len[i][j-1] >= len[i-1][j])
{
len[i][j] = len[i][j-1];

}
else
{
len[i][j] = len[i-1][j];

}
}
}
return len[n_2][n_1];
}[/code]

Posted: **Wed Jun 06, 2007 11:30 am**

Function lcs() is not fully correct. Change the follwoing parts.

Code: Select all

int lcs(int a[], int b[]) 
{
    ...

    for(i=1;i<=n_1;i++)
        for(j=1;j<=n_2;j++)
    ...

    return len[n_1][n_2];
}

Hope it helps. And don't forget to remove your code.

Posted: **Sun Dec 16, 2007 1:45 pm**

Can anyone tell why is CE in this prog?

#include<stdio.h>

int c[110][110];

int test_case = 1;

int m, n;

int i, j;

void LCScount(int x[], int y[])
{
for(i=0; i<=m; i++)
c[0] = 0;

for(j=0; j<=n; j++)
c[0][j] = 0;

for(i=1; i<=m ; i++)
for(j=1; j<=n; j++)
{
if(x[i-1] == y[j-1])
c[j] = c[i-1][j-1] + 1;

else if( c[i-1][j] >= c[j-1])
c[j] = c[i-1][j];

else
c[j] = c[j-1];
}

printf("Number of Tiles : %d\n", c[m][n]);
}

int main()
{
//freopen("in.txt", "r", stdin);

int x[100], y[100];

while(1)
{
scanf("%d %d", &m, &n);

if(m==0 && n==0)
return;

for(i=0; i<m; i++)
scanf("%d", &x);

for(j=0; j<n; j++)
scanf("%d", &y[j]);

printf("Twin Towers #%d\n", test_case++);

LCScount(x,y);

printf("\n");
}
return 0;
}

Posted: **Tue Jun 23, 2009 8:57 pm**

The following gives WA. I tested over 1000 randomly generated inputs using UVA toolkit and my output matches perfectly. I'm stumped.

Code: Select all

removed after AC

Any ideas are welcome.

edit: caught the error when I compiled with -Wall -Wextra.

Posted: **Tue Feb 09, 2010 10:21 pm**

titid_gede wrote:i didnt see your code is wrong, and i submitted your code and AC without changing anything.

the description never told that
** n1<101.**
so
int a[101]
cant hold other values rather than first 101 values.
so it omits the other piles of the first tower..

i got accepted after correcting this..
hope this helps

Posted: **Mon Jul 04, 2011 9:32 pm**

I m getting WA!! But i dont know why?? Plzz anyone help me finding my bug....

Code: Select all

#include<stdio.h>
int main()
{
	freopen("Input.txt","r",stdin);

	int a[110],b[110],i,j,n1,n2,cas=1,c[110][110],n,m;

	while(1)
	{

		scanf("%d %d",&n1,&n2);

		if(n1==0&&n2==0)
			return 0;

		if(n1>n2)
		{
			n=n1;
			m=n2;
		}
		else
		{
			m=n2;
			n=n1;
		}

		for(i=0;i<m;i++)
		{
			scanf("%d",&a[i]);
		}

		for(i=0;i<n;i++)
		{
			scanf("%d",&b[i]);
		}

		for(i=1;i<m;i++)
			c[i][0]=0;

		for(i=0;i<n;i++)
			c[0][i]=0;

		for(i=1;i<m;i++)
		{
			for(j=1;j<n;j++)
			{
				if(a[i]==b[j])
				{
					c[i][j]=c[i-1][j-1]+1;
				}
				else if(c[i-1][j]>=c[i][j-1])
				{
					c[i][j]=c[i-1][j];
				}
				else
					c[i][j]=c[i][j-1];
			}
		}
		
		if(cas>1)
			printf("\n");

		printf("Twin Towers #%d",cas++);
		printf("\nNumber of Tiles : %d\n",c[m-1][n-1]);


	}
}

Posted: **Wed Apr 25, 2012 1:51 am**

We are asked to print an extra new line after each data set.

OJ Board

10066 - The Twin Towers

10066 WA

10066 The Twin Towers WA

Case.....I need more cases!!!

Where do I go wrong?

10066 - CE

Re: 10066 - The Twin Towers

Re:

Re: 10066 - The Twin Towers

Re: 10066 - The Twin Towers