GeneticsProblem code: GENETICS |
All submissions for this problem are available.
Genetic engineering is fun. The scientists have gathered several DNAs and want to create something new out of those. Each DNAs can be represented as a sequence of bases A, G, T, C. Let DNA[a..b] be the subsequence of DNA starting from index a finishing in b inclusive, and DNA[a..] be the subsequence of DNA starting from index a to the end. Scientist can perform the following operations on the DNAs:
- cross operation – they take DNA1 and DNA2 and numbers k1 and k2. Then two new DNAs are created: DNA3 = DNA1[1..k1]+DNA2[k2+1..] and DNA4 = DNA2[1..k2]+DNA1[k1+1..].
- mutate operation – they take a DNA, number k and one of the bases. Then they replace the base in position k in DNA with that base.
- also they need to know certain characteristics of those DNAs. So they can perform count operation – they take DNA and numbers k1 and k2 (k1 <= k2). This operation should return the number of A, G, T, C bases in DNA[k1..k2].
The initial DNAs are numbered from 1 to n, where n is the amount of those DNAs. The new DNAs created in the cross operations are numbered with consecutive integers. You are to write a program to help scientists perform those operations.
Input
The first line of input file contains number n – the amount of initial DNAs. Each of the following n lines contains the description of each DNA. The next line contains number q – the amount of operations to perform. The next q lines contain the description of each operation in the following form:
- CROSS id1 id2 k1 k2
- MUTATE id k m
- COUNT id k1 k2
Constraints
1 <= n <= 20
1 <= q <= 30000
The length of each initial DNA does not exceed 30000. The length of any DNA formed in cross operation won’t exceed 2000000000. Total amount of different DNAs won’t exceed 10000. It is guaranteed that all operations are correct.
Output
For each count operation print four integers: the number of each of the bases in the given subsequence of the given DNA.
Example
Input: 2 CTCGC TGCGG 5 MUTATE 1 2 A COUNT 2 2 4 MUTATE 2 1 G CROSS 2 1 1 5 COUNT 4 3 6 Output: 0 2 0 1 0 2 0 2
| Author: | spooky |
| Tester: | innocentboy |
| Editorial | http://discuss.codechef.com/problems/GENETICS |
| Date Added: | 9-04-2010 |
| Time Limit: | 4 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
do the index of the sequences
do the index of the sequences start from 0 or 1
the description of the cross operation suggest 1 but if so then the line "COUNT 4 3 6" in the sample input be invalid
is there a mistake or am i missing something....
In cross operation id1 and
In cross operation id1 and id2 can be same ?
@chaitanya Thindex in
@chaitanya
Thindex in operations starts with 1. DNA with id=4 will be CACGCGCGG. So COUNT 4 3 6 gives us 2 G and 2 C.
@Oleg
yes
i don't know whats the
i don't know whats the problem when i try the example it works fine in my pc, but here it sayas runtime error could someone tell me what could i have done wrong
Please provide atleast two or
Please provide atleast two or three test cases for eash problem statement.
i have coded this with java.
i have coded this with java. working fine on my pc but here i am geeting run time error...someone plzz tell me d reason.
doubt in problem
doubt in problem statement
cross operation they take DNA1 and DNA2 and numbers k1 and k2. Then two new DNAs are created: DNA3 = DNA1[1..k1]+DNA2[k2+1..] and DNA4 = DNA2[1..k2]+DNA1[k1+1..].
if n=4 i.e. there are 4 DNA in input
and cross operation
cross 2 1 1 5
what will b no. 2 new created DNAs is it DNA5 and DNA6
or DNA3 and DNA4 get modified
Each DNA is given the next
Each DNA is given the next available number. 5 and 6 in that case.
I have coded my solution in C
I have coded my solution in C and it works absolutely fine in my PC. However, it shows runtime error when I try submitting it. Another strange thing is than it shows the runtime error as "OTHER" when I hover the mouse over the icon in "My Submissions" and when I try doioing the same in "Recent Activity", it shows "SIGSEGV". What does it imply? Somebody plz help.
The problem description
The problem description implies (but does not state) that "mutation" modifies an existing DNA rather than creating a new one. Is this correct?
Thanks.
@Brian Yes. MUTATE doesn't
@Brian
Yes. MUTATE doesn't create new DNA.
i am printing count whenever
i am printing count whenever that operation is encountered and i m getting TLE ...
does it mean that i m getting correct answer for test cases tested within time?
No, it just means you
No, it just means you exceeded the time limit. FAQ
Is it necessary that during
Is it necessary that during cross: 1< k1 and k2 <length of either DNA?
No, the sample input has an
No, the sample input has an example with k1=1.