Determining DNA Health
Determining DNA Health
+ 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; }
+ 0 comments thanks
+ 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.
+ 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
+ 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; }
Sort 236 Discussions, By:
Please Login in order to post a comment