## 10066 - The Twin Towers

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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
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:
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

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
New poster
Posts: 2
Joined: Thu Sep 16, 2004 10:46 am
Argh how silly am I

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

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

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

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

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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

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

### Where do I go wrong?

[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
Contact:
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

### 10066 - CE

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

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:

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

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

### Re: 10066 - The Twin Towers

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

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

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

### Re: 10066 - The Twin Towers

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