10066 - The Twin Towers

All about problems in Volume 100. 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
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » 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.

Pavel Nalivaiko
New poster
Posts: 15
Joined: Sun Mar 07, 2004 7:47 pm
Location: Moscow, Russia

Post by Pavel Nalivaiko » 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 ;)

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Post by Minilek » 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 ?

Dvorak
New poster
Posts: 2
Joined: Thu Sep 16, 2004 10:46 am

10066 WA

Post by Dvorak » 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... :cry:

Dvorak
New poster
Posts: 2
Joined: Thu Sep 16, 2004 10:46 am

Post by Dvorak » Thu Sep 16, 2004 11:20 am

Argh how silly am I :oops:

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

Lo_dxer
New poster
Posts: 1
Joined: Wed Jul 06, 2005 10:31 pm

10066 The Twin Towers WA

Post by Lo_dxer » 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

Waddle
New poster
Posts: 22
Joined: Thu Jan 25, 2007 3:54 pm
Location: Taiwan
Contact:

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

Post by Waddle » Fri Jun 01, 2007 5:18 pm

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » 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 ).
Ami ekhono shopno dekhi...
HomePage

Waddle
New poster
Posts: 22
Joined: Thu Jan 25, 2007 3:54 pm
Location: Taiwan
Contact:

Where do I go wrong?

Post by Waddle » 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]

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » 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.
Ami ekhono shopno dekhi...
HomePage

farhan
New poster
Posts: 2
Joined: Fri Dec 07, 2007 7:59 pm
Location: Bangladesh

10066 - CE

Post by farhan » 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;
}

pieguy
New poster
Posts: 2
Joined: Tue Jun 23, 2009 8:39 pm

Re: 10066 - The Twin Towers

Post by pieguy » 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.

iean
New poster
Posts: 1
Joined: Mon Jan 25, 2010 7:11 pm

Re:

Post by iean » 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

User avatar
shaon_cse_cu08
New poster
Posts: 50
Joined: Tue May 25, 2010 9:10 am
Contact:

Re: 10066 - The Twin Towers

Post by shaon_cse_cu08 » Mon Jul 04, 2011 9:32 pm

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

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


	}
}
I'll keep holding on...Until the walls come tumbling down...And freedom is all around ..... :x

masum93
New poster
Posts: 7
Joined: Wed May 11, 2011 11:15 am

Re: 10066 - The Twin Towers

Post by masum93 » Wed Apr 25, 2012 1:51 am

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

Post Reply

Return to “Volume 100 (10000-10099)”