Problem Description

There exist two secret strings $s_1,\ s_2$ composed of characters A, C, G, T. $s_1,\ s_2$ usually match more than 99% of the time, but they can also differ significantly. Let $l_1,\ l_2$ be the lengths of $s_1,\ s_2$ respectively. Given the result $ B $ from observations and operations on these two secret strings, infer the secret strings and output the most likely pair of strings $s_1,\ s_2$.

(1) Observations are made by repeating the following "observation trial" $ n $ times, resulting in $ n $ strings.

(2) Perform the following operations on the $ n $ strings obtained from the observation trials.

(2a) There exists an array $ r $ that the problem author considers similar to $s_1,\ s_2$. Pairwise align $ r $ with each of the $ n $ strings obtained from the observation trials (refer to Problem B for the definition of pairwise alignment).

(2b) Combine the results of the pairwise alignments (total $ n $ results) with $ r $ to form the result $ B $. All pairwise alignments included in result $ B $ are aligned in the same direction as array $ r $.

Observation Trial

(1) Select either $ s_1 $ or $ s_2 $ with a 50% probability, and denote the selected string as $ s_i $.

(2) For the selected string $ s_i $, determine the starting coordinate $ b $ uniformly at random within the range $(-l_i \le b \le l_i)$, and the ending coordinate $ e $ such that $ e - b $ follows a certain distribution. If $ e $ is less than or equal to 0, restart the observation trial from step (1).

(3) If $ b $ is less than or equal to 1, set $ b $ to 1. If $ e $ is greater than $ l_i $, set $ e $ to $ l_i $.

(4) Set $ t = s_i[b: e] $ (the substring of $ s_i $ from the $ b $-th to the $ e $-th character).

(5) With a 50% probability, replace $ t $ with its reverse complement (refer to Problem A for the definition of reverse complement). If replaced, set $ f = $<, otherwise set $ f = $> $. Note that the pairwise alignments included in result $ B $ are aligned in the same direction as $ r $, regardless of $ f $. However, $ B $ contains information indicating the original direction of each string (i.e., $ f $).

(6) Observe $ t $ and output $ f $ and the string. Errors may occur during string observation. Errors include substitutions where a character is replaced by another, and insertions or deletions where characters are added or removed. Refer to the Supplement on Observation Errors for details.

Input Format

Input is given from standard input in the following format:

$ g $ $ f_{1} $ $ r_{1} $ $ c_{1} $ $ f_{2} $ $ r_{2} $ $ c_{2} $ : $ f_{n} $ $ r_{n} $ $ c_{n} $ =

$ n $ observed DNA fragment sequences are given, but to save input data size, the sequences are provided in a compressed notation, given as differences from a standard DNA sequence. The first line of input $ g $ is the standard DNA sequence, a string of 1 to 101,000 characters.

Subsequent lines from the second line onwards describe the observed DNA fragment sequences. Each line starts with $ f_i $ indicating the direction of the DNA relative to the reference sequence. The direction is given as > for the same direction as $ g $ and < for the reverse complement direction of $ g $. The pairs $r_{i},\ c_{i}$ represent the observed DNA fragment sequences in compressed form, detailing differences from a part of $ g $. The input ends with a line containing only =.

Output Format

Output the two inferred secret sequences in two lines, one sequence per line. The sequences must only contain characters A, C, G, T. Ensure the second line ends with a newline.

Sample Input and Output

Sample Input #1

ACACAGCGGCGACC
> 0 3=1XT10=
< 0 14=
< 0 9=1D4=
< 0 14=
< 0 14=
< 0 9=1D4=
=

Sample Output #1

ACACAGCGGCGACCT
ACATAGCGGGACT

Sample Input #2

ACCGGTTGGCGTG
> 0 5=
< 1 8=
> 2 2=1XA3=1IC3=
< 4 5=1D2=
> 7 6=
=

Sample Output #2

ACCGGTTGGCGTG
ACCGGTTGGCGTG

Notes/Hints

Update History

• 28th September, 2021 (JST): With the end of the contest, test cases have been removed, and sample data distribution has ended. Problem D is now only available as a problem statement. Submissions will no longer be judged. The execution time limit during the contest was 30 seconds.
• 11th September, 2021 (JST): Added information necessary for downloading sample data.
• 10th September, 2021 (JST): Fixed the missing end symbol in Sample2. Corrected the error in the text where f = 0 should be f = >. Added an explanation for why the downloadable sample data contains - or X.
• 9th September, 2021 (JST): Added a note about the downloadable dataset.
• 9th September, 2021 (JST): Published the Japanese problem statement. The judge server is operational.

Additional Information (Reproduced from the Top Page)

• 2021/9/12: Prepared a local judge environment using Docker for Problem D. Available for download here (GitHub). Includes a program for parsing input and outputting a very basic solution.
• 2021/9/12: Prepared a document on how to use a BAM format viewer for Problem D. Downloadable here.

Story

You have obtained Oxford Nanopore Technologies' latest device, the PromethION, a machine that reads DNA. You attempt to analyze your own DNA sequence using this machine. However, PromethION does not read your DNA sequence from end to end with 100% accuracy. When you purify DNA for PromethION, it breaks into fragments. Therefore, each observation yields only a part of the DNA sequence. Additionally, observation errors make it difficult to accurately predict your DNA sequence from the set of fragment sequences. Your mission is to infer your true DNA sequence from the output data of PromethION. Your DNA sequence includes two strands inherited from your father and mother, and you want to predict both as accurately as possible.

Observation Error Supplement

Observation errors consist of three types: substitutions, insertions, and deletions. Refer to the problem statement for examples of each type.

Constraints

• $s_1,\ s_2$ are strings composed of characters A, C, G, T.
• $3 \leq l_1,\ l_2 \leq 101,000$.
• $n \le 200$.

Score

Let the output sequences be $o_1,\ o_2$. If swapping $o_1,\ o_2$ improves the score, swap them before calculating the score. Compare $ o_1 $ with $ s_1 $ and $ o_2 $ with $ s_2 $. Correct characters earn 0.01 points each, and incorrect characters (substitutions, deletions, or insertions) lose 0.99 points each. Mosaicization can be used to improve the score if it corrects a misprediction where the sequences swap midway. Mosaicization can only be used once and incurs a penalty of 7.5 points.

Sample Explanation 1

Input displayed in multiple alignment format where G represents the reference sequence:

G : ACACAGCGGCGACC
0 >: ACATAGCGGCGACC
1 <: ACACAGCGGCGACC
2 <: ACACAGCGG-GACC
3 <: ACACAGCGGCGACC
4 <: ACACAGCGGCGACC
5 <: ACACAGCGG-GACC

Sample Explanation 2

Input displayed in multiple alignment format:

R : ACCGGTTG-GCGTG
0 >: ACCGG
1 <: CCGGTTG-G
2 >: CGATTGCGCG
3 <: GTTG-G-GT
4 >: G-GCGTG

见题面 Input 部分

见题面 Output 部分