10066 - The Twin Towers

[little joey]

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.

[Pavel Nalivaiko]

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

[Minilek]

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 ?

[Dvorak]

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...

[Dvorak]

Argh how silly am I

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

[Lo_dxer]

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

[Waddle]

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

[Jan]

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

[Waddle]

[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]

[Jan]

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.

[farhan]

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

[pieguy]

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.

[iean]

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

[shaon_cse_cu08]

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]);


	}
}

[masum93]

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