[Codility] Lesson5 - Prefix Sums: Genomic Range Query

Problem

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] = 6

The 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:

vector<int> solution(string &S, vector<int> &P, vector<int> &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 a vector 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] = 6

the 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, 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.

app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/

GenomicRangeQuery coding task - Learn to Code - Codility

How to solve

- 정보

뉴클레오티드 A, C, G, T 로 이루어진 DNA 서열이 있다. 

각 impact factor는 1, 2, 3, 4 

 

- 구해야 하는것?

주어진 DNA의 특정 부분에 포함된 뉴클레오티드의 최소 impact factor?

 

- 예시

S = CAGCCTA 의 impact factor = (2, 1, 3, 2, 2, 4, 1)

P = {2, 5, 0}, Q={4, 5, 6} 일때, 

P[0]~q[0] 인 2~4 구간의 impact factor는 {3, 2, 2} 최소 impact factor는 2

P[1]~q[1] 인 5~5 구간의 impact factor는 {4} 최소 impact factor는 4

P[2]~q[2] 인 0~6 구간의 impact factor는 {2, 1, 3, 2, 2, 4, 1} 최소 impact factor는 1

순서대로 {2, 4, 1} return 

 

- 풀이

처음에는 P[i] ~ Q[i] 구간의 문자열을 하나하나 확인하였는데, time out 이 났다ㅠㅠ

 

이 문제는 문자별로 prefix sum을 구해놓고 풀어야 한다. 

특정 구간에서 prefix sum의 차를 계산한 값이 > 0 이면 그 문자가 구간에 존재하는 것이고,

각 문자별로 확인 한 다음 최소 값을 return 하면 된다.  

 

Solution(c++)

// you can use includes, for example:
#include <bits/stdc++.h>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
    // write your code in C++14 (g++ 6.2.0)
    int len_S = S.length(); //string 길이
    int len_P = P.size();
    int len_Q = Q.size();
    int cum_A = 0, cum_C = 0, cum_G = 0, cum_T = 0; 

    vector<int> impact_A(len_S, 0);
    vector<int> impact_C(len_S, 0);
    vector<int> impact_G(len_S, 0);
    vector<int> impact_T(len_S, 0);

    vector<int> res;

    for(int i=0; i<len_S; i++){
        if(S[i] == 'A'){
            cum_A += 1; //1
        }else if(S[i] == 'C'){
            cum_C += 1; //2
        }else if(S[i] == 'G'){
            cum_G += 1; // 3
        }else if(S[i] == 'T'){
            cum_T += 1; // 4
        }
        impact_A[i] = cum_A;
        impact_C[i] = cum_C;
        impact_G[i] = cum_G;
        impact_T[i] = cum_T;
    }

    for(int i=0; i<len_P; i++){
        int left = P[i];
        int right = Q[i];
        int min_val = 5;
        if((impact_A[right] - impact_A[left-1]) >0){
            min_val = min(1 , min_val);
        }else if((impact_C[right] - impact_C[left-1]) >0){
            min_val = min(2 , min_val);
        }else if((impact_G[right] - impact_G[left-1]) >0){
            min_val = min(3 , min_val);
        }else if((impact_T[right] - impact_T[left-1]) >0){
            min_val = min(4 , min_val);
        }
        res.push_back(min_val);
    }
    return res;
}

Test Result

app.codility.com/demo/results/trainingKDQQG2-V7K/

Test results - Codility