The LCS Problem RevisitedProblem code: J2 |
All submissions for this problem are available.
The Longest Common Subsequence (LCS) problem is a well known problem in Computer Science. Every computer science students in Byteland knows this problem. Johnny does, too.
Recall that a subsequence of a string S is obtained by deleting some characters from S. Given two strings S and T, the LCS problem is the find the longest sequence that is a subsequence of both S and T.
Johnny has the habit of deriving harder problems from a familiar problem. This time, based on the LCS problem, he has thought up the following problem:
Given two strings S and T, how many distinct LCS of S and T are there?
Write a program to help Johnny solve this problem. Since the result may be very large, you only need to print the remainder of the result when dividing by 23102009.
Input
The first line contains t, the number of test cases (about 10). Then t test cases follow.
Each test case consists of two lines, the first line is the string S and the second line is the string T. You may assume that the strings consists of only lowercase characters and the length of the each string is at most 1000 characters.
Successive test cases at input are separated by a single blank line.
Output
For each test case, print a single line containing two numbers which are the length of the LCS and the remainder of the number of distinct LCS of S and T when dividing by 23102009.
Example
Input 2 acbd acbd vnvn vn Output 4 1 2 1 Output detailsThe only LCS in the first case is "acbd" and in the second case is "vn".
| Date: | 2009-10-15 |
| Time limit: | 3.5s |
| Source limit: | 50000 |
| Languages: | C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK TEXT JS |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions 
@ admins: From what i
@ admins: From what i understand of the problem the second case output should be 2 4 and not 2 1. Could you please check that.
2 1 seems correct to me..
2 1 seems correct to me.. there is only one common subsequence of length 2.
Sorry about the confusion.
Sorry about the confusion. Did not read that the LCS should be distinct.
I guess the empty string is
I guess the empty string is counted as 1 LCS, incase of none.. as in , "abcd" and "efgh"
@Anil Kishore: When the
Ya.. but shouldn't it be 0 0
Ya.. but shouldn't it be 0 0 , because.. empty string can be a answer always, but even for "abc" , "ade" answer is 0 1
what will be output for
what will be output for "abcd" and "a"
is it 1 1
or 1 2 /*cosidering null string also*/
Can there be more test cases.
Can there be more test cases. The test cases given in the problem are just too trivial. I have checked my code against a lot of test cases and seem to be getting the correct answer but everytime I submit the code, codechef says "wrong answer" :(
The example test cases are
The example test cases are enough for explaining the concept :)
@Admin I think Kunal's
@Admin
I think Kunal's question is valid.
Can you please clarify that ?
The null string has length 0,
The null string has length 0, not 1.
@Stephen Yeah, thanks.
@Stephen
Yeah, thanks. Realized that.
Please don't give away hints
Please don't give away hints or anything that will help others solve the problem, as you are setting yourself up for disqualification. Hopefully the admin can delete these comments before anyone else can see them.
I don't see how this helps
I don't see how this helps anybody solve the problem, but will delete the comments if you tell me how.
Admin, You'd have known by
Admin,
You'd have known by now, but still just wanted to point out. I get the following error when viewing some profiles:
warning: Division by zero in /var/www/html/codechefbeta/codechef/api/all_functions.php on line 43 :)
Admin, If an answer is
Admin,
If an answer is correct, I'd like to see the execution time along side the "correct answer" display. I've requested for this already but still find it hasn't been done :(
can some one give a good
can some one give a good input for this distinct LCS
Sure, after the contest
Sure, after the contest finishes ;)
@Yashwant We will try to
@Yashwant We will try to introduce this feature.
@admin although i have
@admin although i have declared a variable ,on submitting my solution it is giving that the variable is not declared in scope
can you plzz help me out
@gourav We cannot help out in
@gourav We cannot help out in such a way during the contest.
this is third problem where I
this is third problem where I have designed an algorithm, but was too time consuming. I dont know how you guys get it right so early?? specially this one. just the thought of 1000 char long string's subsequences give me chills.
anyway, now trying totally different approach.
They just use their evil
@admin Can you give some test
@admin
Can you give some test cases ? I am getting WA. :(
what should be the answer in
what should be the answer in case of abcd and efgh.is it (0 0 )or (0 1)
i need a single test case to
i need a single test case to check my soln.i am getting WA :(
How can the result be mor
How can the result be mor than 23102009
if the string len is not more than 1000.
@Giri u have to the no. of
@Giri
u have to the no. of distinct LCSs
@giri u have to find the
@giri
u have to find the distinct LCSs
@ravin I got that thing but
@ravin
I got that thing but can you tell give me an example in which the value can be more than the string length.
I am not able to find any such case..
Hope you got what i my confussion is
A tutorial for this problem
A tutorial for this problem can be found here: Tutorial for The LCS Problem Revisited