Discussion on Determining DNA Health Challenge

Sort 236 Discussions, By:

6 days ago+ 0 comments

can some suggesset how this can be optimized?

int TotalHealthOfUnhealthiest (int first, int last, string d, 
                                                                vector<string> genes, vector<int> health)
{
        int result = 0, hvalue, start, end, sub;

        for(int i = first; i <= last; i++)
        {
                string str = genes[i];

                start = 0;
                end = str.size();

                while(d.size() >= end)
                {
                        string dsub = "";
                        sub = start;

                        while(sub < end)
                        {
                                dsub += d[sub];
                                sub++;
                        }

                        if(str == dsub)
                        {
                                result += health[i];
                        }

                        start++;
                        end++;
                } 
        }

        return result;
}

2 weeks ago+ 0 comments

thanks

1 month ago+ 0 comments

History, Suryakant Tripathi Nirala was a renowned Hindi poet, novelist, essayist, and story writer. He was born on February 21, 1896, in a small village in Uttar Pradesh, India, and died on March 15, 1961, in Allahabad, India.

2 months ago+ 0 comments

NFTs have gained popularity in recent years as a new way for artists, musicians, and other content creators to monetize their work. With NFTs, creators can sell their digital works as unique, one-of-a-kind assets, which can be owned and traded by buyers. WE LIST NFT PROJECTS TO FACILITATE THE USER TO SEARCH FOR NEW PROJECTS

2 months ago+ 0 comments

Fast C++ version.

O(n) complexity where n=length of DNA string. ie, performs only 1 lookup / comparison per character in DNA string. When a valid gene sequence is found, a further O(log m) where m=number of duplicate gene entries, to locate the first gene that falls within the [start, end] range. Finally, O(p) to enumerate each gene that falls within the [start, end] range.

int main() {
    int ngenes, ndna;
    string tmp;

    cin >> ngenes;
    struct sHealth {
        int    index;
        int    val;
    };
    struct sGene {
        string            seq;
        vector<sHealth>    health;
        sGene() = default;
        sGene(const string &s) : seq{s} {}
    };
    struct sLut { int gi; int v[26]; };
    vector<sGene> genes {{""}};
    vector<sLut> lut(26);

    {
        vector<int> ndx(ngenes);
        unordered_map<string,int> map;

        for (int i=0; i<ngenes; i++) {
            cin >> tmp;
            auto t = map.emplace(tmp, genes.size());
            if (t.second) genes.emplace_back(tmp);
            ndx[i] = t.first->second;

            sLut *L = &lut[tmp[0]-97];
            for (int j=1, l=tmp.length(); ; j++) {
                if (j == l) { L->gi = ndx[i]; break; }
                int ch = tmp[j]-97;
                if (L->v[ch]) L = &lut[L->v[ch]]; else {
                    L->v[ch] = lut.size();
                    lut.emplace_back();
                    L = &lut.back();
                }
            }
        }

        for (int i=0, h; i<ngenes; i++) {
            cin >> h;
            genes[ndx[i]].health.push_back({i, h});
        }
    }

    cin >> ndna;
    int64_t hsum=0, htop=0, hlow=INT64_MAX;

    for (int i=0, first, last; i<ndna; i++) {
        string dna;
        cin >> first >> last >> dna;

        for (int p=hsum=0, e=dna.length(), j, n; p<e; p++) {
            sLut *L = &lut[dna[p]-97];
            for (j=p;;) {
                if (L->gi) {
                    const auto &G = genes[L->gi];
                    int l=0, s=G.health.size(), r=s, m;
                    do {
                        m = l + ((r-l) >> 1);
                        const auto &H = G.health[m];
                        if (first > H.index) { l=m+1; continue; }
                        if (first < H.index && m && first <= G.health[m-1].index) { r=m; continue; }
                        while (m < s && G.health[m].index <= last) hsum += G.health[m++].val;
                        break;
                    } while (r!=l);
                }

                if (++j >= e) break;
                n = L->v[dna[j]-97];
                if (n) L = &lut[n]; else break;
            }
        }
        htop = max(htop, hsum);
        hlow = min(hlow, hsum);
    }
    cout << hlow << " " << htop << "\n";
    
    return 0;
}

Load more conversations