Edit DistanceProblem code: CF02 |
All submissions for this problem are available.
Run-length encoding(RLE) is a very simple and easy form of data compression in which consecutive occurrences of the same characters are replaced by a single character followed by its frequency. As an example, the string S aabbbbdaa would be encoded to a2b4d1a2.
Thus encoded string is described as an ordered sequence of pairs (a, i), each consisting of an alphabet symbol a and an integer i. Each pair corresponds to a run in S consisting of i consecutive occurrences of a.
In this problem, we are interested in finding the minimum number of mutation(s) needed to transform first string given in encoded form into second string i.e. edit distance when only two operation are allowed
- Add any character at any position(insertion)
- Remove any character from any position(deletion)
The cost of inserting a character is 1 and cost of deleting a character is 2.
Input
The input file contains several test cases. The first line of the input denotes the number of test cases, T (1 T 100) to follow. Each test case begins on a new line and consists of an integer L1, a blankspace and a run length encoded string S1 and then on a new line, an integer L2, a blankspace and a run length encoded string S2.
L1 and L2 denote the number of runs in strings S1 and S2 respectively. 1<=L1,L2<=100.
S1 and S2 consists of alphabets [a-z] followed by number of consecutive occurrences of that character.
You can safely assume that the total length of any of the strings will not exceed 3000 characters.
Output
For each test case, output the edit distance from S1 to S2 in a new line.
Example
Input: 2 2 a3b2 1 b3 3 a1b1a1 1 a2 Output: 7 2
| Author: | manthan |
| Date Added: | 26-03-2010 |
| Time Limit: | 2 sec |
| Source Limit: | 50000 Bytes |
| Languages: | C, CLOJ, CPP 4.0.0-8, CPP 4.3.2, F#, GO, PERL6, PYTH 3.1.2, TEXT |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
"You can safely assume that
"You can safely assume that the total length of any of the strings will not exceed 3000 characters."
Is this sentence about the original string, or the encoded string?
Will there be input like c6c6
Will there be input like c6c6 ?
The length constraint is
No. There is no such input in
What is the maximum length of
What is the maximum length of a run, for e.g. if input is of form aX
what is maximum value of integer X?
@screw_it: As the original
@screw_it: As the original string (not the encoded string) can be of maximum 3000 characters, X can maximum be 3000, if number of run is 1
Is the second test case right
Is the second test case right ???
Yes, by deleting the 'b'
Yes, by deleting the 'b'
is the run length positive?
is the run length positive?
@Musketiri: Yes run lengths
@Musketiri: Yes run lengths are always positive (>0).
Is it possible to submit
Is it possible to submit solution in JAVA
Current ranking is available
Current ranking is available at http://www.codechef.com/teams/list/MANTH10/
@sam6230i: No only C/CPP
@sam6230i: No only C/CPP codes are allowed for the contest.
Hi, can we know why our team
Hi, can we know why our team is not elligible, I have registered our team at the CodeFest website before the start of contest and also my current team ID is our team name at your website.
Thanks
@ThreeKhan : Eligible team
@ThreeKhan : Eligible team section shows invalid data. All teams registered on Codechef wenbsite and listed at http://www.codechef.com/teams/list/MANTH10/ are eligible for prizes if they form a team for Manthan at Codefest website with same team members. The team names can be different.