Tasks Details
medium
Find the minimal nucleotide from a range of sequence DNA.
Task Score
87%
Correctness
100%
Performance
66%
A DNA sequence can be represented as a string consisting of the letters A, C, G and T, which correspond to the types of successive nucleotides in the sequence. Each nucleotide has an impact factor, which is an integer. Nucleotides of types A, C, G and T have impact factors of 1, 2, 3 and 4, respectively. You are going to answer several queries of the form: What is the minimal impact factor of nucleotides contained in a particular part of the given DNA sequence?
The DNA sequence is given as a non-empty string S = S[0]S[1]...S[N-1] consisting of N characters. There are M queries, which are given in non-empty arrays P and Q, each consisting of M integers. The K-th query (0 ≤ K < M) requires you to find the minimal impact factor of nucleotides contained in the DNA sequence between positions P[K] and Q[K] (inclusive).
For example, consider string S = CAGCCTA and arrays P, Q such that:
P[0] = 2 Q[0] = 4 P[1] = 5 Q[1] = 5 P[2] = 0 Q[2] = 6The answers to these M = 3 queries are as follows:
- The part of the DNA between positions 2 and 4 contains nucleotides G and C (twice), whose impact factors are 3 and 2 respectively, so the answer is 2.
- The part between positions 5 and 5 contains a single nucleotide T, whose impact factor is 4, so the answer is 4.
- The part between positions 0 and 6 (the whole string) contains all nucleotides, in particular nucleotide A whose impact factor is 1, so the answer is 1.
Write a function:
def solution(S, P, Q)
that, given a non-empty string S consisting of N characters and two non-empty arrays P and Q consisting of M integers, returns an array consisting of M integers specifying the consecutive answers to all queries.
Result array should be returned as an array of integers.
For example, given the string S = CAGCCTA and arrays P, Q such that:
P[0] = 2 Q[0] = 4 P[1] = 5 Q[1] = 5 P[2] = 0 Q[2] = 6the function should return the values [2, 4, 1], as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- M is an integer within the range [1..50,000];
- each element of arrays P and Q is an integer within the range [0..N - 1];
- P[K] ≤ Q[K], where 0 ≤ K < M;
- string S consists only of upper-case English letters A, C, G, T.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 3 minutes
Notes
not defined yet
Code: 10:02:02 UTC,
java,
autosave
Code: 10:02:13 UTC,
py,
autosave
from copy import deepcopy
ip = {'A':1, 'C':2, 'G':3, 'T':4}
ip_rev = {1: 'A', 2: 'C', 3: 'G', 4: 'T'}
def solution(S, P, Q):
ret = []
N, M = len(S), len(P)
counter = [[0,0,0,0] for _ in range(N)]
for idx, c in enumerate(S):
counter[idx] = deepcopy(counter[idx-1])
counter[idx][ip[c]-1] += 1
# print(ip.values().index(0))
counter.insert(0, [0,0,0,0])
for idx in range(M):
start, end = P[idx], Q[idx]
if start == end:
ret.append(ip[S[start]])
else:
for i in range(4):
if counter[end][i] - counter[start][i] > 0:
# print(i)
ret.append(ip[ip_rev[i+1]])
break
return ret
Code: 10:02:38 UTC,
py,
verify,
result: Passed
from copy import deepcopy
ip = {'A':1, 'C':2, 'G':3, 'T':4}
ip_rev = {1: 'A', 2: 'C', 3: 'G', 4: 'T'}
def solution(S, P, Q):
ret = []
N, M = len(S), len(P)
counter = [[0,0,0,0] for _ in range(N)]
for idx, c in enumerate(S):
counter[idx] = deepcopy(counter[idx-1])
counter[idx][ip[c]-1] += 1
# print(ip.values().index(0))
counter.insert(0, [0,0,0,0])
for idx in range(M):
start, end = P[idx], Q[idx]
if start == end:
ret.append(ip[S[start]])
else:
for i in range(4):
if counter[end][i] - counter[start][i] > 0:
ret.append(i+1)
break
return ret
Analysis
Code: 10:02:50 UTC,
py,
autosave
from copy import deepcopy
ip = {'A':1, 'C':2, 'G':3, 'T':4}
ip_rev = {1: 'A', 2: 'C', 3: 'G', 4: 'T'}
def solution(S, P, Q):
ret = []
N, M = len(S), len(P)
counter = [[0,0,0,0] for _ in range(N)]
for idx, c in enumerate(S):
counter[idx] = deepcopy(counter[idx-1])
counter[idx][ip[c]-1] += 1
# print(ip.values().index(0))
counter.insert(0, [0,0,0,0])
for idx in range(M):
start, end = P[idx], Q[idx]
if start == end:
ret.append(ip[S[start]])
else:
for i in range(4):
if counter[end][i] - counter[start][i] > 0:
ret.append(i+1)
break
return ret
Code: 10:03:02 UTC,
py,
verify,
result: Passed
from copy import deepcopy
ip = {'A':1, 'C':2, 'G':3, 'T':4}
ip_rev = {1: 'A', 2: 'C', 3: 'G', 4: 'T'}
def solution(S, P, Q):
ret = []
N, M = len(S), len(P)
counter = [[0,0,0,0] for _ in range(N)]
for idx, c in enumerate(S):
counter[idx] = deepcopy(counter[idx-1])
counter[idx][ip[c]-1] += 1
# print(ip.values().index(0))
counter.insert(0, [0,0,0,0])
for idx in range(M):
start, end = P[idx], Q[idx]
if start == end:
ret.append(ip[S[start]])
else:
for i in range(4):
if counter[end][i] - counter[start][i] > 0:
ret.append(i+1)
break
return ret
User test case 1:
['AC', [0, 0, 1], [0, 1, 1]]
User test case 2:
['TC', [0, 0, 1], [0, 1, 1]]
Analysis
expand all
User tests
1.
0.036 s
OK
function result: [1, 1, 2]
function result: [1, 1, 2]
1.
0.040 s
OK
function result: [4, 4, 2]
function result: [4, 4, 2]
Code: 10:03:18 UTC,
py,
verify,
result: Failed
from copy import deepcopy
ip = {'A':1, 'C':2, 'G':3, 'T':4}
ip_rev = {1: 'A', 2: 'C', 3: 'G', 4: 'T'}
def solution(S, P, Q):
ret = []
N, M = len(S), len(P)
counter = [[0,0,0,0] for _ in range(N)]
for idx, c in enumerate(S):
counter[idx] = deepcopy(counter[idx-1])
counter[idx][ip[c]-1] += 1
# print(ip.values().index(0))
counter.insert(0, [0,0,0,0])
for idx in range(M):
start, end = P[idx]-1, Q[idx]
if start == end:
ret.append(ip[S[start]])
else:
for i in range(4):
if counter[end][i] - counter[start][i] > 0:
ret.append(i+1)
break
return ret
User test case 1:
['AC', [0, 0, 1], [0, 1, 1]]
User test case 2:
['TC', [0, 0, 1], [0, 1, 1]]
Analysis
expand all
Example tests
1.
0.040 s
WRONG ANSWER,
got [1, 2] expected [2, 4, 1]
Code: 10:03:29 UTC,
py,
autosave
from copy import deepcopy
ip = {'A':1, 'C':2, 'G':3, 'T':4}
ip_rev = {1: 'A', 2: 'C', 3: 'G', 4: 'T'}
def solution(S, P, Q):
ret = []
N, M = len(S), len(P)
counter = [[0,0,0,0] for _ in range(N)]
for idx, c in enumerate(S):
counter[idx] = deepcopy(counter[idx-1])
counter[idx][ip[c]-1] += 1
# print(ip.values().index(0))
counter.insert(0, [0,0,0,0])
for idx in range(M):
start, end = P[idx]-, Q[idx]
if start == end:
ret.append(ip[S[start]])
else:
for i in range(4):
if counter[end][i] - counter[start][i] > 0:
ret.append(i+1)
break
return ret
Code: 10:03:47 UTC,
py,
autosave
from copy import deepcopy
ip = {'A':1, 'C':2, 'G':3, 'T':4}
ip_rev = {1: 'A', 2: 'C', 3: 'G', 4: 'T'}
def solution(S, P, Q):
ret = []
N, M = len(S), len(P)
counter = [[0,0,0,0] for _ in range(N)]
for idx, c in enumerate(S):
counter[idx] = deepcopy(counter[idx-1])
counter[idx][ip[c]-1] += 1
# print(ip.values().index(0))
counter.insert(0, [0,0,0,0])
for idx in range(M):
start, end = P[idx]-1, Q[idx]
if start == end:
ret.append(ip[S[start]])
else:
for i in range(4):
if counter[end][i] - counter[start][i] > 0:
ret.append(i+1)
break
return ret
Code: 10:03:53 UTC,
py,
verify,
result: Passed
from copy import deepcopy
ip = {'A':1, 'C':2, 'G':3, 'T':4}
ip_rev = {1: 'A', 2: 'C', 3: 'G', 4: 'T'}
def solution(S, P, Q):
ret = []
N, M = len(S), len(P)
counter = [[0,0,0,0] for _ in range(N)]
for idx, c in enumerate(S):
counter[idx] = deepcopy(counter[idx-1])
counter[idx][ip[c]-1] += 1
# print(ip.values().index(0))
counter.append([0,0,0,0])
for idx in range(M):
start, end = P[idx]-1, Q[idx]
if start == end:
ret.append(ip[S[start]])
else:
for i in range(4):
if counter[end][i] - counter[start][i] > 0:
ret.append(i+1)
break
return ret
User test case 1:
['AC', [0, 0, 1], [0, 1, 1]]
User test case 2:
['TC', [0, 0, 1], [0, 1, 1]]
Analysis
expand all
User tests
1.
0.036 s
OK
function result: [1, 1, 2]
function result: [1, 1, 2]
1.
0.036 s
OK
function result: [4, 2, 2]
function result: [4, 2, 2]
Code: 10:04:04 UTC,
py,
verify,
result: Passed
from copy import deepcopy
ip = {'A':1, 'C':2, 'G':3, 'T':4}
ip_rev = {1: 'A', 2: 'C', 3: 'G', 4: 'T'}
def solution(S, P, Q):
ret = []
N, M = len(S), len(P)
counter = [[0,0,0,0] for _ in range(N)]
for idx, c in enumerate(S):
counter[idx] = deepcopy(counter[idx-1])
counter[idx][ip[c]-1] += 1
# print(ip.values().index(0))
counter.append([0,0,0,0])
for idx in range(M):
start, end = P[idx]-1, Q[idx]
if start == end:
ret.append(ip[S[start]])
else:
for i in range(4):
if counter[end][i] - counter[start][i] > 0:
ret.append(i+1)
break
return ret
User test case 1:
['AC', [0, 0, 1], [0, 1, 1]]
User test case 2:
['TC', [0, 0, 1], [0, 1, 1]]
Analysis
expand all
User tests
1.
0.036 s
OK
function result: [1, 1, 2]
function result: [1, 1, 2]
1.
0.036 s
OK
function result: [4, 2, 2]
function result: [4, 2, 2]
Code: 10:04:07 UTC,
py,
final,
score:
87
from copy import deepcopy
ip = {'A':1, 'C':2, 'G':3, 'T':4}
ip_rev = {1: 'A', 2: 'C', 3: 'G', 4: 'T'}
def solution(S, P, Q):
ret = []
N, M = len(S), len(P)
counter = [[0,0,0,0] for _ in range(N)]
for idx, c in enumerate(S):
counter[idx] = deepcopy(counter[idx-1])
counter[idx][ip[c]-1] += 1
# print(ip.values().index(0))
counter.append([0,0,0,0])
for idx in range(M):
start, end = P[idx]-1, Q[idx]
if start == end:
ret.append(ip[S[start]])
else:
for i in range(4):
if counter[end][i] - counter[start][i] > 0:
ret.append(i+1)
break
return retAnalysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N + M)
expand all
Correctness tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.040 s
OK
1.
0.040 s
OK
expand all
Performance tests
almost_all_same_letters
GGGGGG..??..GGGGGG..??..GGGGGG
GGGGGG..??..GGGGGG..??..GGGGGG
✘
TIMEOUT ERROR
running time: 0.748 sec., time limit: 0.432 sec.
running time: 0.748 sec., time limit: 0.432 sec.
1.
0.884 s
OK
2.
0.748 s
TIMEOUT ERROR,
running time: 0.748 sec., time limit: 0.432 sec.
1.
0.836 s
OK
1.
0.932 s
OK