ChromosomalCrossover
TCO17 New 3B · 2017-03-31 · by cgy4ever
TCO17 New 3B · 2017-03-31 · by cgy4ever · Brute Force
Problem Statement
Problem Statement
In this problem we will use strings over the alphabet ACGT.
For simplicity, we will call them chromosomes.
We will consider a special genetic recombination called a chromosomal crossover. At the beginning of such a recombination we have two strings of the same length: X and Y. During the chromosomal crossover X and Y will swap their prefixes of the same length. Formally, there will be an integer k between 1 and the length of X, inclusive, with the following property: X will change into Y[0..k-1] + X[k..], and Y will change into X[0..k-1] + Y[k..]. For example, a chromosomal crossover with k = 3 will change the pair "CCCCC", "GGGGG" into the pair "GGGCC", "CCCGG".
Let lcs(X,Y) denote the length of the longest common substring of the strings X and Y. Note that the substring must be contiguous. For example, lcs("CAAA","AAAG") = 3, and lcs("CAC","CTC") = 1. For chromosomes X and Y the value lcs(X,Y) is called their similarity value.
You are given two chromosomes: two equally-longString s A and B.
You may perform an arbitrary number of chromosomal crossovers, one after another.
Compute and return the largest similarity value that can be obtained.
We will consider a special genetic recombination called a chromosomal crossover. At the beginning of such a recombination we have two strings of the same length: X and Y. During the chromosomal crossover X and Y will swap their prefixes of the same length. Formally, there will be an integer k between 1 and the length of X, inclusive, with the following property: X will change into Y[0..k-1] + X[k..], and Y will change into X[0..k-1] + Y[k..]. For example, a chromosomal crossover with k = 3 will change the pair "CCCCC", "GGGGG" into the pair "GGGCC", "CCCGG".
Let lcs(X,Y) denote the length of the longest common substring of the strings X and Y. Note that the substring must be contiguous. For example, lcs("CAAA","AAAG") = 3, and lcs("CAC","CTC") = 1. For chromosomes X and Y the value lcs(X,Y) is called their similarity value.
You are given two chromosomes: two equally-long
Constraints
- A will contain between 1 and 50 elements, inclusive.
- A and B will contain the same number of elements.
- Each character in A will be one of {'A', 'T', 'C', 'G'}.
- Each character in B will be one of {'A', 'T', 'C', 'G'}.
Examples
0)
"AAAAAA" "TCGTCG" Returns: 3
One optimal solution is to do just a single crossover with k = 3. This produces the chromosomes "TCGAAA" and "AAATCG". Their similarity value is 3 because of the common substring "AAA".
1)
"AAA" "CCC" Returns: 2
This time we need to do it twice, first we swap prefix of length 2: ("AAA", "CCC") -> ("CCA", "AAC"). Then we swap prefix of length 1: ("CCA", "AAC") -> ("ACA", "CAC").
2)
"ATCGATCGATCG" "ATCGATCGATCG" Returns: 12
This time we don't need to do anything.
3)
"AAAAATTTTTCCCCCGGGGG" "ACTTCATGTGCTAGCTGTAG" Returns: 4
4)
"A" "G" Returns: 0
Submissions are judged against all 112 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ChromosomalCrossover with a public method int maximalLength(string A, string B) · 112 test cases · 2 s / 256 MB per case