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 » Tue Jan 03, 2006 9:13 am

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 » Sun Mar 19, 2006 8:40 pm

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 » Tue May 30, 2006 4:55 pm

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 » Wed Jun 28, 2006 2:54 am

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 » Fri Jun 30, 2006 12:56 pm

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 » Sat Jul 01, 2006 6:01 pm

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 » Mon Jul 17, 2006 1:39 am

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 » Wed Jul 19, 2006 2:57 am

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 » Wed Jul 19, 2006 5:05 am

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 » Tue Nov 21, 2006 10:41 am

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 » Mon Aug 06, 2007 3:20 pm

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

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

Post by emotional blind » Mon Aug 06, 2007 4:29 pm

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 » Mon Aug 06, 2007 4:38 pm

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

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

Post by emotional blind » Mon Aug 06, 2007 4:43 pm

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 » Mon Aug 06, 2007 5:27 pm

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