TSOC '16 Contest 1 #6 - Joey and Biology

View as PDF
Submit solution
Points: 12 (partial)
Time limit: 1.0s
Memory limit: 512M
Authors:
omaewamoushindeiru, msa789, bobhob314, PaulOlteanu, kobortor, gah111
Problem types

Joey is a purportedly professional programmer. However, his IQ is below average, so we wish to confirm that he is actually human. Max the biologist isolated one DNA strand coding for the same gene from both Joey and a test organism (one per test case). Now we wish to quantify how different Joey's DNA is from the test organism's. Test organisms include raccoons, larvae, and phytoplankton.

The difference between two strands of DNA is quantified as the following: The minimum total amount of edits that need to be made to either/both strands to make them equal. An edit can be one of the following: deleting one, two or three consecutive base pairs from a strand, adding one, two or three consecutive base pairs, or changing a base pair to a different one.

Input Specification

On the first line, two integers N and M (1 \le N, M \le 1000).

On the second line, a string N letters long composed of the characters A, T, C and G representing Joey's DNA.

On the third line, a string M letters long composed of the characters A, T, C and G representing the animal's DNA.

Output Specification

A single integer, the quantifiable difference between the two strands of DNA.

Scoring

It is guaranteed that 30\% of the score will consist of test cases where N=M. (Not sure how that would help you, though.)

It is also guaranteed that 20\% of the score (possibly overlapping with the previous condition) will consist of test cases where N, M \le 10.

Sample Input

4 6
ATCG
ATCGCG

Sample Output

1

Explanation

One can delete a CG from the test organism to make the strings equal, which is only one edit.

Biology Lesson

awef

Since we only took one strand of DNA, a base pair refers to only one character provided in the input. This is because DNA is double-stranded and complementary, such that knowing the coding of one strand gives you the other strand's coding also (A-T C-G generally). Therefore, in the sample input, the DNA strands are 4 base pairs and 6 base pairs in length respectively.

Comments


  • 1
    pblpbl  commented on April 13, 2020, 11:25 p.m.

    why does this need recursion just wondering


    • 2
      Dan13llljws  commented on April 13, 2020, 11:52 p.m.

      It is one way of solving this problem since you can do dp with recursion as well.