(Challenge) Bacteria Synthesis

All submissions for this problem are available.
### Read problem statements in [Bengali](http://www.codechef.com/download/translated/AUG19/bengali/SYNBAC.pdf), [Hindi](http://www.codechef.com/download/translated/AUG19/hindi/SYNBAC.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/AUG19/mandarin/SYNBAC.pdf), [Russian](http://www.codechef.com/download/translated/AUG19/russian/SYNBAC.pdf), and [Vietnamese](http://www.codechef.com/download/translated/AUG19/vietnamese/SYNBAC.pdf) as well. Chef Ada always prepares delicious and nutritious dishes. Her secret is to use genetic engineering of bacteria to synthesise proteins. A protein is denoted by a string of uppercase English characters 'A''T'; each character represents an amino acid. The genome of Ada's bacteria is also denoted by a string with length $N$. Each character of this string is 'A', 'C', 'T' or 'G', representing a nucleotide. The nucleotides are also numbered $1$ through $4$ in the same order 'A', 'C', 'T', 'G'. Let's denote the number of a nucleotide $x$ by $n(x)$. You are given the starting genome $G$ of Ada's bacteria; at any point, all bacteria must have the same genome. You may perform operations of the following types (in any order, any number of times):  `1 L R`: Reverse the substring between the $L$th and $R$th character inclusive ($1 \le L \le R \le N$), i.e. for each $L \le i \lt L+Ri \le R$, swap the $i$th and $L+Ri$th nucleotide of the current genome. The cost of this operation is $K + \mathrm{min}\,(L1, RL, NR)$ chefcoins.  `2 i Y`: Mutate, i.e. change the $i$th nucleotide of the current genome ($1 \le i \le N$) to the nucleotide $Y$. The cost of this operation is $A + \mathrm{min}\,(i, N+1i) \cdot B_{n(X), n(Y)}$ chefcoins, where $X$ denotes the $i$th nucleotide before this mutation. Each amino acid is encoded by one or more *codons* ― a codon is a string of three nucleotides. Each codon encodes exactly one amino acid. Note that there are $4^3$ different codons and only $20$ amino acids. For each codon, you are given the amino acid it encodes. A bacteria can produce a protein $P$ with length $L$ amino acids if its genome contains a substring of $3 \cdot L$ nucleotides that can be *translated* to $P$, i.e. split into a sequence of $L$ consecutive substrings $Z_1, Z_2, \ldots, Z_L$ with lengths $3$ such that for each $i$ ($1 \le i \le L$), $Z_i$ is a codon for the $i$th amino acid (character) of $P$. For example, let's suppose that codons "ATA" and "TAT" are translated to amino acids 'R' and 'S' respectively. Then, a bacteria with a genome "ATATATA" can produce only the following proteins (the codons used to produce them are marked by brackets):  "[ATA]TATA" to "R"  "A[TAT]ATA" to "S"  "[ATA][TAT]A" to "RS"  "A[TAT][ATA]" to "SR" For her next dish, Ada needs $M$ proteins $P_1, P_2, \ldots, P_M$. Her bacteria do not have to produce all proteins, since they can be bought on the market; for each valid $i$, the cost of the protein $P_i$ is $C_i$ chefcoins. However, Ada wants the final bacteria to be able to synthesise at least $50$ of the required proteins. As her apprentice, your task is to perform some (possibly zero) genetic operations on the initial genome and decide which proteins should be produced from the resulting genome; all other proteins are bought on the market. Your goal is to minimise the total cost (in chefcoins). ### Input  The first line of the input contains four spaceseparated integers $N$, $M$, $K$ and $A$.  $M$ lines follow. For each $i$ ($1 \le i \le M$), the $i$th of these lines contains a string $P_i$, followed by a space and an integer $C_i$.  The next line contains a single string $G$ with length $N$.  Each of the next four lines contains four spaceseparated integers. For each $i$ and $j$ ($1 \le i, j \le 4$), the $j$th integer on the $i$th line is $B_{i, j}$.  Each of the next $64$ lines contains a single string with length $4$. The first three characters of this string denote a unique codon and the last character denotes the amino acid which it encodes. ### Output  First, print a line containing two spaceseparated integers $Q$ ($0 \le Q \le 10^5$) and $U$ ($50 \le U \le M$) ― the number of operations you want to perform and the number of required proteins the final bacteria will produce.  Then, print $Q$ lines. Each of these lines should contain the description of an operation you want to perform, in the format given above.  Finally, print $U$ lines. Each of these lines should contain two spaceseparated integers $i$ and $L$ denoting that the protein $P_i$ can be generated by the substring which starts with the $L$th character in the final genome. You will receive a Wrong Answer veredict if you print the same $i$ twice. ### Constraints  $N = 2^{15}$  $1 \le M \le 2^{12}$  $K = 2^{13}$  $A = 2^{13}$  $0 \le B_{i, j} \le 2^2$ for each valid $i, j$  $2^{27} \le C_i \le 2^{28}$ for each valid $i$ ### Example Input ``` 9 3 8192 8192 AB 134217728 BC 134217728 ABC 134217728 ACCATGGAA 0 1 2 3 1 2 3 0 2 3 0 1 3 0 1 2 ACGA TACB GTAC ... [61 codons more] ... ``` ### Example Output ``` 2 3 1 3 6 2 8 T 1 1 2 4 3 1 ``` ### Explanation  The initial genome is "ACCATGGAA".  In the first operation, the substring "CATG" is reversed: "AC[CATG]GAA" becomes "ACGTACGAA".  In the second operation, the $8$th nucleotide ('A') is replaced by 'T': "ACGTACG[A]A" becomes "ACGTACGTA". Some of the proteins which can be synthesised from the final genome are:  "AB" from "[ACG][TAC]GTA"  "BC" from "ACG[TAC][GTA]"  "ABC" from "[ACG][TAC][GTA]" ### Scoring The score of a test file is the cost of obtaining all required proteins, i.e. the number of chefcoins you need to pay. The score of a submission is the sum of costs of all test files. Your goal is to minimise the score of your submission. There are twelve test files. During the contest, the displayed score will account for exactly four test files, i.e. your score reflects your submission's performance on approximately 33.33% (4/12) of the test files; However, if your program gets a nonAC verdict on any test file, your submission's verdict will be nonAC. In other words, an AC verdict denotes that your program runs successfully on all the test files. After the end of the contest, your score will be changed to include the sum of your program's scores over the other 8 test files. ### Test Generation All translations codon > amino acid are generated independently from each other. For each codon, the amino acid it encodes is chosen uniformly randomly. $B_{x, y}$ is randomly chosen between $0$ and $2^2$ (inclusive). To generate the genome $G$, first, a genome $T$ with length $N$ is generated; each nucleotide of this genome is chosen uniformly randomly. Next, each of the proteins $P_1, P_2, \ldots, P_M$ is generated as follows:  Choose the length $l$ of the protein uniformly randomly between $L_p$ and $R_p$ inclusive.  Choose a substring $S_p$ in the genome uniformly randomly among all substrings with length $3l$.  Translate $S_p$ to get the protein $P_i$.  Choose the cost $C_i$ uniformly randomly between $2^{27}$ and $2^{28}$ inclusive. Then, the genome $T$ is modified by performing the following operations in this order:  Mutations: $N_M$ different nucleotides are chosen uniformly randomly. Each of them is changed to a uniformly random (possibly the same) nucleotide, independently from all other changed nucleotides.  Reversals: $N_R$ times, a substring of the current genome is chosen uniformly randomly and reversed. The resulting string after these $N_M+N_R$ operations is the genome $G$. Finally, here is how the remaining parameters are chosen:  $M$ can be either $2^{10}$ or $2^{12}$.  $L_p$ and $R_p$ can be either $100$ and $200$ respectively, or $200$ and $300$ respectively.  $N_M$ and $N_R$ can be either $0$ and $2^{12}$ espectively, $2^{12}2^7$ and $2^7$ respectively, or $2^{9}$ and $2^{12}2^9$ respectively. There is one test file for each combination of the parameters $M$, $L_p$, $R_p$, $N_M$ and $N_R$.Author:  alei 
Editorial  https://discuss.codechef.com/problems/SYNBAC 
Tags  alei, aug19, challenge, vijju123 
Date Added:  22072019 
Time Limit:   5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions