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

xlvector
New poster
Posts: 11
Joined: Thu Dec 29, 2005 8:30 am
Contact:

Thank you, I got AC

Post by xlvector »

I will not paste functions I am not call next time.
Thank you for your hint

WRJ
New poster
Posts: 11
Joined: Sun Mar 19, 2006 8:28 pm

Post by WRJ »

Thank you!
I've had problem with reading input, too ;)

linhomeyeu
New poster
Posts: 4
Joined: Tue May 30, 2006 4:51 pm

10405

Post by linhomeyeu »

WHY??

#include<stdio.h>
int main()
{
int aa,bb,i,j,k,h;
char a[1001],b[1001];
while(gets(a)!=NULL&&gets(b)!=NULL)
{
aa=strlen(a);bb=strlen(b);
for(i=0,k=0,h=-1;i<aa;i++)
for(j=h+1;j<bb;j++)
if(a==b[j])
{k++;h=j;break;}
printf("%d\n",k);
}
return 0;
}

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon »

Hi,

Your program fails on the following IO

Code: Select all

input:

cabc
abc

output:

3

linhomeyeu
New poster
Posts: 4
Joined: Tue May 30, 2006 4:51 pm

Post by linhomeyeu »

thanks, but my code is still WR......Why?

Code: Select all

#include<stdio.h>
int main()
{
    int aa,bb,i,j,k,h;
    void reverse(char*a,char*b);
    char a[1001],b[1001];
    while(gets(a)!=NULL&&gets(b)!=NULL)
    {
    aa=strlen(a);bb=strlen(b);
    if(aa>bb)
        reverse(a,b);
    aa=strlen(a);bb=strlen(b);
        for(i=0,k=0,h=-1;i<aa;i++)
          for(j=h+1;j<bb;j++)
        	if(a[i]==b[j])
    	      {k++;h=j;break;}
    printf("%d\n",k);
    }
    return 0;
}

void reverse(char*a,char*b)
{
    int i,aa,bb;
    char c[1001];
    aa=strlen(a);bb=strlen(b);
    for(i=0;i<aa;i++)
        c[i]=a[i];
    c[i]=0;
    for(i=0;i<bb;i++)
        a[i]=b[i];
    a[i]=0;
    for(i=0;i<aa;i++)
        b[i]=c[i];
    b[i]=0;
}

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon »

Hi,

Your program fails the following:

Code: Select all

input:
abcxxxxxxxx
abxxxxxxxxc

output:
10

linhomeyeu
New poster
Posts: 4
Joined: Tue May 30, 2006 4:51 pm

WR

Post by linhomeyeu »

Sorry, Daveon. I'm still WR.

Code: Select all

code is deleted
Last edited by linhomeyeu on Wed Jul 19, 2006 5:06 am, edited 1 time in total.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon »

Do you know of the DP solution to this Longest Common Subsequence problem?

If you just want to get AC, then you may look up this well known DP algorithm. However, if you are the one who likes to solve everything by yourself, then you'll have to prove that your algorithm is correct.

linhomeyeu
New poster
Posts: 4
Joined: Tue May 30, 2006 4:51 pm

Post by linhomeyeu »

daveon wrote:Do you know of the DP solution to this Longest Common Subsequence problem?

If you just want to get AC, then you may look up this well known DP algorithm. However, if you are the one who likes to solve everything by yourself, then you'll have to prove that your algorithm is correct.
I think I'm the second one. However, I have to thank for your forbearing answer.(I'm not a English-mother-language person, so my English may be awful. please do not care it.)

darkos32
New poster
Posts: 27
Joined: Tue Jul 25, 2006 8:10 am
Location: Indonesia
Contact:

10405 WA

Post by darkos32 »

hi,i dont use dp for this problems,i try to make another code,but why i got WA ?

Code: Select all

#include <stdio.h>
#include <string.h>
void main(){
	freopen("longest.in","r",stdin);
	freopen("longest.out","w",stdout);
	char a[1001] = "";char b[1001]="";
	while(gets(a)){
		gets(b);
		int ta = strlen(a);
		int tb = strlen(b);
		int max = 0;
		int i = 0;int j = 0;
		int tempi = ta;int tempj = tb;
		int maks = 0;
		while(i<ta){
			j = 0;
			while(j<tb){
				if(a[i]==b[j]){
					tempi = i+1;
					int tempjj = j+1;
					int byk = 1;
					//printf("%d %d - ",i,j);
					//printf("%c %c - ",a[i],b[j]);
					while(tempi<ta){
						tempj = tempjj;
						while(tempj<tb){
							if(a[tempi]==b[tempj]) {
								//printf("%d %d - ",tempi,tempj);
								//printf("%c %c - ",a[tempi],b[tempj]);
								byk++;
								tempjj=tempj+1;
								tempj+=tb;
							}
							tempj++;
						}
						//printf("%d - ",tempjj);
						tempi++;
					}
					//printf("\n");
					if(byk>maks) maks = byk;
				}
				j++;
			}
			i++;
		}
		printf("%d\n",maks);
	}
}
can anyone give me the testcase please ?
thanks.

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Post by andysoft »

Hello World :) !
I have solved this problem (ok, AC) on C using usual LCS algo. My C prog ran during 1.807 sec and I am 2867 / 2899 in ranking. But I cannot understand how did some people solve this prob in 0.004 sec??! Even on Pascal, which is in most cases slower than C/C++! Any idea?

Thanx for attention
Now I lay me down to sleep...
my profile

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind »

I don't know which one is faster? pascal or C?

But I know that bottom up approach is faster than top down approach, when you solve a DP problem.

My solution takes 0.027 sec.

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Post by andysoft »

Okay, I will try to implement bottom up as you have said.
0.027 is believable, but how did people get 0.004 seconds? Can it be cheating (knowing I/O for the prob) ?
Now I lay me down to sleep...
my profile

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind »

I just coded bottom up.. But didnt use any optimization in my code.
But a lot of optimization can be implemented.
Faster input output, faster calculation. I am not able to do all of that. :(

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Post by andysoft »

Can you please make a hint for me to feel the difference between bottom up and top down in this problem. o(n^2) solution of this kind:

Code: Select all

for i in sequence 1
  for j in sequence 2
    if s1[i]=s2[j] then
      ans[i][j] = ans[i-1][j-1] + 1; 
    else if .... and so on ...
is top-down? or bottom-up? :oops:
thanx in advance :)
Now I lay me down to sleep...
my profile

Post Reply

Return to “Volume 104 (10400-10499)”