## Joey and Biology

View as PDF

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 512M

Authors:
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

On the first line, two integers and .

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

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

#### Output

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

#### Scoring

It is guaranteed that of the score will consist of test cases where . (Not sure how that would help you, though.)

It is also guaranteed that of the score (possibly overlapping with the previous condition) will consist of test cases where .

#### 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

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.