## IOI '21 P4 - Mutating DNA

View as PDF

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

Problem type
Allowed languages
C++

Grace is a biologist working in a bioinformatics firm in Singapore. As part of her job, she analyses the DNA sequences of various organisms. A DNA sequence is defined as a string consisting of characters "A", "T", and "C". Note that in this task DNA sequences do not contain character "G".

We define a mutation to be an operation on a DNA sequence where two elements of the sequence are swapped. For example a single mutation can transform "ACTA" into "AATC" by swapping the highlighted characters "A" and "C".

The mutation distance between two sequences is the minimum number of mutations required to transform one sequence into the other, or if it is not possible to transform one sequence into the other by using mutations.

Grace is analysing two DNA sequences and , both consisting of elements with indices from to . Your task is to help Grace answer questions of the form: what is the mutation distance between the substring and the substring ? Here, a substring of a DNA sequence is defined to be a sequence of consecutive characters of , whose indices are to inclusive. In other words, is the sequence .

#### Implementation Details

You should implement the following procedures:

void init(string a, string b)

• , : strings of length , describing the two DNA sequences to be analysed.
• This procedure is called exactly once, before any calls to get_distance.
int get_distance(int x, int y)

• , : starting and ending indices of the substrings to be analysed.
• The procedure should return the mutation distance between substrings and .
• This procedure is called exactly times.

#### Example

Consider the following call:

init("ATACAT", "ACTATA")


Let's say the grader calls get_distance(1, 3). This call should return the mutation distance between and , that is, the sequences "TAC" and "CTA". "TAC" can be transformed into "CTA" via mutations: TAC CAT, followed by CAT CTA, and the transformation is impossible with fewer than mutations.

Therefore, this call should return .

Let's say the grader calls get_distance(4, 5). This call should return the mutation distance between sequences "AT" and "TA". "AT" can be transformed into "TA" through a single mutation, and clearly at least one mutation is required.

Therefore, this call should return .

Finally, let's say the grader calls get_distance(3, 5). Since there is no way for the sequence "CAT" to be transformed into "ATA" via any sequence of mutations, this call should return .

#### Constraints

• Each character of and is one of "A", "T", and "C".

1. ( points)
2. ( points) , each character of and is either "A" or "T".
3. ( points) each character of and is either "A" or "T".
4. ( points)
5. ( points) No additional constraints.

• line : for the -th call to get_distance.
• line : the return value of the -th call to get_distance.