Find3Cheaters
TCO04 Round 1 · 2004-09-07 · by AdminBrett
TCO04 Round 1 · 2004-09-07 · by AdminBrett · Dynamic Programming, String Manipulation
Problem Statement
Problem Statement
You have recently collected a programming assignment from your class, and suspect some people have cheated. An anonymous informant has let you know that the cheaters work in groups of 3. To quickly find the cheaters, you want a program that will find the shortest common supersequence of 3 different assignments. Three assignments will be given to you in three String s a, b, and c. Return the length of the shortest common supersequence of these 3 String s.
Given aString X, a subsequence of X is a String produced by removing some of the characters of X (possibly none). For example, (quotes for clarity) "topcoder", "toder", "oode", and "" are all subsequences of "topcoder". If Y is a subsequence of X then X is a supersequence of Y.
Given a
Constraints
- a will contain between 1 and 50 lowercase letters ('a'-'z') inclusive.
- b will contain between 1 and 50 lowercase letters ('a'-'z') inclusive.
- c will contain between 1 and 50 lowercase letters ('a'-'z') inclusive.
Examples
0)
"aagaaa" "ataatg" "ctggg" Returns: 11
"catagagaatg" is a supersequence of all 3 strings.
1)
"wowwowwow" "wowwowwow" "badbadbad" Returns: 18
"wowwowwowbadbadbad" is a supersequence of all 3.
2)
"a" "aaaaaaa" "aaaaaaaaaaaaaa" Returns: 14
3)
"abcdefghijklmnopqrstuvwxyz" "zyxwvutsrqponmlkjihgfedcba" "abcdefghijklmnzyxwvutsrqpo" Returns: 51
4)
"agtatagtatgtagtatgtatgatgagt" "adgatgatgdatddgatgdatgdatgat" "adatdgatdgtadgdgtdgatdgtadgt" Returns: 41
Submissions are judged against all 103 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Find3Cheaters with a public method int shortest(string a, string b, string c) · 103 test cases · 2 s / 256 MB per case