Czech Technical University in Prague
ICPC Foundation
Czech ACM Chapter
Central Europe Regional Contest 2019
Ponk Warshall
ponk.c, ponk.cpp, Ponk.java, ponk.py
Listening to the rock music permutes your nuclear DNA. This astonishing and unbelievable
fact was recently published in the Rock Nature Weekly, one of the top scientific journals on
the planet. Part of the research was to take DNA samples from volunteers, both before and
after the rock concerts season. The samples were processed and various genes isolated from the
samples. For each person, each gene was isolated twice: The variant before the rock season and
the variant after the season. These two variants were paired and in many cases one variant was
found to be some permutation of the other variant in the pair.
The next step in the research is to determine how the permutations happen. The prevalent
hypothesis suggests that a permutation is composed of a sequence of transpositions, so-called
swaps. A swap is an event (its chemistry is not fully understood yet) in which exactly two
nucleobases in the gene exchange their places in the gene. No other nucleobases in the gene
are affected by the swap. The positions of the two swapped nucleobases might be completely
arbitrary.
To predict and observe the movement of the molecules in the permutation process, the re-
searchers need to know the theoretical minimum number of swaps which can produce a par-
ticular permutation of nucleobases in a gene. We remind you that the nuclear DNA gene is a
sequence of nucleobases cytosine, guanine, adenine, and thymine, which are coded as C, G, A,
and T, respectively.
Input Specification
The input contains two text lines. Each line contains a string of N capital letters "A", "C", "G",
or "T", (1 ≤ N ≤ 106). The two strings represent one pair of a particular gene versions. The
first line represents the gene before the rock season, the second line represents the same gene
from the same person after the rock season. The number of occurrences of each nucleobase is
the same in both strings.
Output Specification
Output the minimum number of swaps that transform the first gene version into the second one.
Sample Input 1
Output for Sample Input 1
CGATA
2
ATAGC
Sample Input 2
Output for Sample Input 2
CTAGAGTCTA
7
TACCGTATAG
