Connection Status:
Competition Arena > Enzymes

Enzymes

SRM 130 · 2003-01-25 · by chogyonim

SRM 130 · 2003-01-25 · by chogyonim
Class Name: Enzymes
Return Type: int
Method Name: split
Arg Types: (vector<string>, string)
Problem Statement

Problem Statement

*** WARNING: Do not leave the competition room while you are competing. If you have a question, use "admins: question" in the chat area. ***

Biologists often use enzymes to break proteins they are studying into pieces. A protein is a chain of amino acids. A protein will be represented as a String of capital letters, each letter representing an amino acid. For example, "GGCCDDEFFA" and "CCDDEE" are two examples of proteins.

Each enzyme will be represented by a String of non-repeating capital letters. When used, the enzyme will break a protein after all amino acids that are identified in this String. For example, "CDE" is an enzyme that breaks proteins after occurrences of "C", "D", or "E" in the protein representation. If we apply "CDE" to "GGCCDDEFFA" we would get "GGC", "C", "D", "D", "E", "FFA" since the enzymes breaks the protein after all of the specified letters.

Create a class Enzymes that contains a method split which takes as arguments a String[] enzymes representing the enzymes at your disposal and String protein representing the protein to be broken. The method returns the total number of unique fragments that can be produced by using any combination of the given enzymes in any order.

Valid amino acids are: "ACDEFGHIKLMNPQRSTVWY".

Notes

  • Proteins are directional. Therefore a enzyme can only cleave after a specific amino acid, and not before. For example, the enzyme "C" can cleave the protein "ACE" into "AC" and "E", but not into "A" and "CE".
  • Once applied, an enzyme completely breaks a protein after all specified amino acids.

Constraints

  • enzymes will contain between 1 and 10 elements, inclusive.
  • each element of enzymes will have between 1 and 20 characters, inclusive.
  • each element of enzymes will only contain capital letters representing valid amino acids, with no repetition of letters. Valid amino acids are "ACDEFGHIKLMNPQRSTVWY".
  • protein will have between 1 and 50 characters, inclusive.
  • each character of protein will be a capital letter which represents a valid amino acid. Valid amino acids are "ACDEFGHIKLMNPQRSTVWY".
  • At least one character in each element of enzymes will be a character other than the last in protein
Examples
0)
{"WYFLM","KR"}
"AACDDYNQQNMEREY"
Returns: 6

Using only the first enzyme, we would break the protein at 3 locations. However, one of these is after the last amino acid of the protein, so no new fragment would be created (remember also that we don't count the original protein fragment). This gives us 3 (new) fragments. Using the second enzyme we break at only one amino acid, giving us 2 fragments. Using both enzymes we break at all 3 of the previous points, giving us 4 fragments. However, 3 of these fragments (the initial "AACDDY", "NQQNM", and the final "EY") are repeated, so the total count is 6: "AACDDY", "NQQNM", "EREY", "AACDDYNQQNMER", "EY", AND "ER".

1)
{"GMNPAC","AC","NP","GM","A","C","N","P","G","M"}
"ACCACCDDEDFGHPPQPRPCCFGGPTVWYYTSPQRMNLKIGHFEDAC"
Returns: 49
2)
{"AFKRSTY","ADEFHILNQRT","ADGHIQRS","CDHIMNQRV","CDEFHQ",
 "AGHINRSTWY","ACDEFHILNPQR","ACDGILPRSV","DFKMNQRSTVY"}
"LDVQMTLTRSIQQLYAKII"
Returns: 38
3)
{"CEFIKLPQRVY","DFGKPRST","AHMPRST","CDIKLMPSVWY"}
"FYHKQAYDHLWRHMM"
Returns: 32

The 32 fragments are: "AY", "HMM", "LWR", "HLWR", "YDH", "YHK", "KQA", "QAYD", "WR", "Y", "RHM", "W", "FYH", "FY", "R", "Q", "QA", "YH", "M", "L", "YD", "K", "QAY", "DHL", "H", "F", "HM", "HL", "D", "DH", "HK", and "A".

4)
{"EFHILNPQSTW","AEHIPVWY","AFHIKMNRTVW","CFHLPQRVWY","CIKMQSTW","ACDHIQRT","ACDFHILNT"}
"TVAYQQA"
Returns: 12

Submissions are judged against all 17 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Enzymes with a public method int split(vector<string> enzymes, string protein) · 17 test cases · 2 s / 256 MB per case

Submitting as anonymous