10405 - Longest Common Subsequence

All about problems in Volume 104. 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
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Tue Jun 08, 2004 6:59 am

hi,
i think the problem is with my way of reading input cos i ran a lot of test cases and my algo seems fine...
Have you consider about empty lines?

Input :

Code: Select all

a


a
Output :

Code: Select all

0
0
I think your program can't handle such cases.

Hope it helps :wink:


Anggakusuma

paulidirac
New poster
Posts: 5
Joined: Mon Jun 07, 2004 9:00 pm

Post by paulidirac » Tue Jun 08, 2004 7:34 am

i tried with gets instead of cin...it can handle null strings...i also submit my program as C instead of C++...but now i get Runtime Error (SIGSEGV) after 0.316 seconds of execution.... wat's the error supposed to mean? thanx

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Tue Jun 08, 2004 8:54 am

Hi,
paulidirac wrote:i tried with gets instead of cin...it can handle null strings...i also submit my program as C instead of C++...but now i get Runtime Error (SIGSEGV) after 0.316 seconds of execution.... wat's the error supposed to mean? thanx
I'm suspicious with this fragment:

Code: Select all

for (i=0;i<blen;i++){ 
   last=pos[i]; 
   for (j=0;j<alen;j++){ 
      if (a[j]==b[i]){ 
         max=0; 
         for (k=i-1;k>=0;k--){ 
            for (l=pos[k];l<pos[k+1];l++){ 
               if (loc[l]<j && max<best[l]){ 
                  max=best[l]; 
               } 
            } 
         } 
         best[last]=max+1; 
         loc[last]=j; 
         last++; 
     } 
   } 
   pos[i+1]=last; 
}
Consider input:

Code: Select all

aaaa...(repeated 1000 times)
aaaa...(also repeated 1000 times)
Your program will work as follows:
- in the first step (i=0) -> last=0 , then j will be repeated 1000 times, and last will become 0+1000.
- next step (i=1) -> last=1000, and then j will be repeated 1000 times, and last will become 1000+1000.

In this situation, last will be greater than 1000, and will also exceed your maximum array bound (1002). This will cause runtime error.

Hope it helps :wink:


Anggakusuma

emka
New poster
Posts: 10
Joined: Sat Oct 19, 2002 7:20 am
Location: Singapore
Contact:

10405 - LCS: Any idea why my prog is WA ?

Post by emka » Fri Jun 11, 2004 11:18 am

Hi

Can anybody figure out the bugs within my code?
I got WA for this. Thanks :)

[cpp]
#include <iostream>
#include <string.h>

using namespace std;

int main(void){
int ar[2][1001], top = 1, bottom = 0;
char s1[1001], s2[1001];

while ( cin ){
cin.getline( s1, 1001 );
cin.getline( s2, 1001 );

//----------------------------------------------
//--------- code segment removed ---------------
//----------------------------------------------

}

return 0;
}[/cpp]
Last edited by emka on Mon Jun 14, 2004 6:57 am, edited 1 time in total.
-mk

paulidirac
New poster
Posts: 5
Joined: Mon Jun 07, 2004 9:00 pm

Post by paulidirac » Fri Jun 11, 2004 9:21 pm

hi,
thanx for the help...i thought i'd be saving on mem that way, but guess i couldn't..but it's very surprising that even after allocating a 1000 X 1000 array at compile time, the judge shows that my code runs in 64k.. is there some flaw in the judge memory monitoring?
thanx.

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Sat Jun 12, 2004 4:46 am

it's very surprising that even after allocating a 1000 X 1000 array at compile time, the judge shows that my code runs in 64k..
I don't know either. If your program runs fast, usually the memory will become only 64k. :o

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Sat Jun 12, 2004 5:26 am

You can change the way you read the input:
[cpp]while ( cin.getline( s1, 1001) ){
cin.getline( s2, 1001 );
...
}[/cpp]
Hope it helps :wink:

emka
New poster
Posts: 10
Joined: Sat Oct 19, 2002 7:20 am
Location: Singapore
Contact:

Post by emka » Mon Jun 14, 2004 6:58 am

Well done, got AC now!

Thanks a lot :wink:
-mk

[senu]
New poster
Posts: 6
Joined: Tue May 18, 2004 6:59 pm

Post by [senu] » Tue Jun 22, 2004 4:56 pm

stcheung wrote:What causes my program to be so slow? Or do others simply add some optimization tricks I wasn't aware of?

[cpp]#include <iostream>
#include <string>
[/cpp]
i like STL, but vectors/streams/strings etc are slower than pointers/printf/scanf/char *

[senu]
New poster
Posts: 6
Joined: Tue May 18, 2004 6:59 pm

Post by [senu] » Tue Jun 22, 2004 6:03 pm

i got WA, but im sure my solution is good. can You help me?

[cpp]#include <stdio.h>
#include <iostream>
#define MAX 1002
#define f(x)for(int i=0; i<=x; i++)
#define f2(x,y)for(int i=x; i<=y; i++)

using namespace std;

int i,k,j,l,m,n,qq,c,maxc;
int t[MAX+1][MAX+1];
char a[MAX], b[MAX];

int max(int a, int b){if(a>=b)return a; else return b;}

int lcs(char *A, char *B)
{
f(m) t[n+1]=0;
f(n) t[m+1]=0;
t[0][0]=0;

for(int i=m; i>=0; i--)
for(int j=n; j>=0; j--)
{
if(a=='\0' || b[j]=='\0') t[j]=0;
else if (a==b[j]) t[j]=t[i+1][j+1]+1;
else t[j]=max(t[i+1][j],t[j+1]);
}

return t[0][0];
}

int main()
{
while ( cin.getline( a, 1001) )
{
cin.getline( b, 1001 );

i=0; while (a!='\n' && a!='\0') i++; m=--i;
i=0; while (b[i]!='\n' && b[i]!='\0') i++; n=--i;

cout << lcs(a,b) << endl;
}


return 0;
}
[/cpp]

[senu]
New poster
Posts: 6
Joined: Tue May 18, 2004 6:59 pm

Post by [senu] » Tue Jun 22, 2004 6:16 pm

[cpp] --m=strlen(a);
--n=strlen(b);
[/cpp]

OK. I got AC, but i dont know why :PPP
Can You tell me?

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Post by jackie » Sat Jul 24, 2004 5:33 am

I use DP LCS algorithm and got AC.
here it's input and output hope it can help those who get WA

[cpp] while (gets(d1))
{
gets(d2);
m = strlen(d1);
n = strlen(d2);
if (m == 0 || n == 0)
break;
// do the LCS
printf("%d\n", lcs[m][n]);
}[/cpp]

thincal
New poster
Posts: 7
Joined: Thu Sep 23, 2004 7:45 am

Post by thincal » Mon Nov 01, 2004 6:40 pm

[cpp]
#include<iostream>
#include<string>
#include<stdio.h>
#include<algorithm>
using namespace std;
char a[1001],b[1001];
int L[1001][1001];

int main(){
int la,lb,i,j;
while(gets(a) && gets(b)){
la=strlen(a),lb=strlen(b);
for(i=la;i>=1;i--)a=a[i-1];
for(i=lb;i>=1;i--)b=b[i-1];
memset(L,0,sizeof(L));
for(i=1;i<=la;i++)
for(j=1;j<=lb;j++){
if(a==b[j])L[j]=L[i-1][j-1]+1;
else L[j]=max(L[i-1][j],L[j-1]);
}
cout<<L[la][lb]<<endl;
}
return 0;
}[/cpp]

sklitzz
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm

10405 Can anyone help me on this one

Post by sklitzz » Thu Feb 17, 2005 10:40 pm

I don't get, why do I get WA?

Code: Select all

#include <stdio.h>
#include <string.h>

#define MAX 1001

int lcs( char *s1, char *s2 )
{
	int i, j;
	int dp[MAX][MAX] = { 0 };
	int len1 = strlen( s1 ), len2 = strlen( s2 );
	
	for( i = 1; i <= len1; ++i )
		for( j = 1; j <= len2; ++j )
			if( s1[i-1] == s2[j-1] ) dp[i][j] = dp[i-1][j-1] + 1;
			else if( dp[i-1][j] >= dp[i][j-1] ) dp[i][j] = dp[i-1][j];
			else dp[i][j] = dp[i][j-1];
	return dp[len1][len2];
}

int main()
{
	char s1[MAX], s2[MAX];
	while( ( scanf( "%s", s1 ) !=EOF ) && ( scanf( "%s", s2 ) != EOF ) )
		printf( "%d\n", lcs( s1, s2 ) );
	return 0;
}

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Fri Feb 18, 2005 1:19 am

You should read them line by line instead. I think there might be spaces.. (don't remember.)

Try:

Code: Select all

while ( gets( s1 ) && gets( s2 ) )
instead..

Post Reply

Return to “Volume 104 (10400-10499)”