We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Passes all test cases in C++. Was having issues with some test cases as I was using INT_MAX as the initial worst case despite using unsigned longs everywhere, when the test case's worst case was higher than that. Switching to ULONG_MAX worked.
classTrieNode{public:unordered_map<char,TrieNode*>children={};vector<pair<int,unsignedlong>>scores=vector<pair<int,unsignedlong>>();~TrieNode(){this->destroy_tree();}unsignedlongget_score(intfirst,intlast){unsignedlongscore=0;for(pair<int,unsignedlong>s:scores){if(s.first>last){// guaranteed increasing orderreturnscore;}if(s.first>=first){score+=s.second;}}returnscore;}TrieNode*get_child(charc){if(this->children.find(c)!=this->children.end()){returnthis->children[c];}returnnullptr;}TrieNode*add_child(charc){if(this->children.find(c)==this->children.end()){children[c]=newTrieNode();}returnthis->children[c];}private:voiddestroy_tree(){for(auto[c,child]:children){deletechild;}}};unsignedlongget_score(TrieNode*root,stringdna,intfirst,intlast){unsignedlongscore=0;for(size_ti=0;i<dna.size();++i){TrieNode*node=root;size_tj=i;while(node!=nullptr&&j<dna.size()){node=node->get_child(dna[j]);if(node!=nullptr){score+=node->get_score(first,last);}++j;}}returnscore;}intmain(){//// ... boilerplate, not sure why they didn't give a separate fn for this oneif(s==0||n==0){cout<<"0 0"<<endl;return0;}unsignedlongbest_score=0;unsignedlongworst_score=ULONG_MAX;for(ints_itr=0;s_itr<s;s_itr++){stringfirst_multiple_input_temp;getline(cin,first_multiple_input_temp);vector<string>first_multiple_input=split(rtrim(first_multiple_input_temp));intfirst=stoi(first_multiple_input[0]);intlast=stoi(first_multiple_input[1]);stringdna=first_multiple_input[2];unsignedlongscore=get_score(&root,dna,first,last);best_score=max(best_score,score);worst_score=min(worst_score,score);}cout<<worst_score<<" "<<best_score<<endl;return0;
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Determining DNA Health
You are viewing a single comment's thread. Return to all comments →
Passes all test cases in C++. Was having issues with some test cases as I was using
INT_MAX
as the initial worst case despite using unsigned longs everywhere, when the test case's worst case was higher than that. Switching toULONG_MAX
worked.