c++ - Topcoder Div 2 algorithm -
hi trying solve topcoder problem incompletebst given here: http://community.topcoder.com/stat?c=problem_statement&pm=6713&rd=9999
my approach : first validate if input bst
1. number associated current node 2. keep dividing 2 until quotient appears in input list quotient parent/ancestor of current node 3. check if current node left/right child of ancestor isvalidchild() function this. i) converts both of numbers binary representation ii) 0 in binary rep indicates left child , 1 indicates right child iii) @ point of difference in binary rep check if next el 0 (left) or right(1) iv) if left associated character should <= cur,else > cur 4) if bst getthevalues() the code given below
class incompletebst { public: vector<int> binaryrep(unsigned long long num) { cout<<"\nbinart rep start\n"; vector<int> vbinary; while(num > 0) { vbinary.insert(vbinary.begin(),num%2); num/=2; } //vbinary.insert(vbinary.begin(),num); cout<<"\nbinary rep end\n"; return vbinary; } bool isvalidchild(unordered_map<unsigned long long ,char>& map, unordered_map<unsigned long long,char>::iterator childitr,unordered_map<unsigned long long,char>::iterator parentitr) { cout<<"\nisvalidchild start\n"; if(childitr == map.end()) cout<<"\nchild itr null\n"; if(parentitr == map.end()) cout <<"\nparent itr null\n"; vector<int> vchild = binaryrep(childitr->first); vector<int> vparent = binaryrep(parentitr->first); int i; for(i =0;i<vparent.size();i++) { if(vchild[i] != vparent[i]) break; } if(vchild[i] == 1 && childitr->second > parentitr->second) { cout <<"\nisvalidchild if end \n"; return true; } else if(vchild[i] == 0 && childitr->second < parentitr->second) { cout <<"\nisvalidchild else if end\n"; return true; } else { cout<<"\nisvalidchild else end\n"; return false; } } bool isbst(unordered_map<unsigned long long,char>& map) { cout<<"\nisbst start"; unordered_map<unsigned long long,char>::iterator it; for(it = map.begin(); != map.end(); it++) { if(it->first != 1 && it->second != '?') { unsigned long long num = it->first; unordered_map<unsigned long long,char>::iterator resultitr; cout<<"\nfinding parent itr for"<<num<<endl; while(num > 1) { num /= 2; resultitr = map.find(num); if(resultitr != map.end()) { if(resultitr->second == '?') continue; else break; } } if (it->second != '?' && resultitr->second != '?' && !isvalidchild(map,it,resultitr)) { cout<<"\nisbst end if\n"; return false; } } } cout<< "\nisbst end\n"; return true; } string getvalues(unordered_map<unsigned long long,char>& map,unsigned long long missingnum) { cout<<"\ngetvaluesstart\n"; unsigned long long tmp = missingnum; unordered_map<unsigned long long,char>::iterator it; while(tmp>1) { tmp/=2; = map.find(tmp); if(it != map.end()) break; } vector<int> vchild = binaryrep(missingnum); vector<int> vparent = binaryrep(it->first); int i; for( =0;i<vparent.size();i++) { if(vchild[i] != vparent[i]) break; } string strresult=""; if(vchild[i] == 1) { for(char ch = it->second+1;ch<='z';ch++) strresult += ch; }else { for(char ch = 'a'; ch<=it->second;ch++) strresult += ch; } cout<<"\ngetvaluesend\n"; return strresult; } string missingvalues(vector<string> tree) { cout<< "\n missing values start \n"; unordered_map<unsigned long long,char> map; int sz = tree.size(); unsigned long long missingnum = 0; for(int i=0; i<sz; i++) { vector<string> vtokens; split(tree[i],' ',vtokens); unsigned long long num = stoull(vtokens[1]); map.insert(make_pair(num,vtokens[0][0])); if(vtokens[0] == "?") missingnum = num; } if( !isbst(map)) { return ""; } return getvalues(map,missingnum); } void split(const std::string &s, char delim, std::vector<std::string> &elems) { std::stringstream ss(s); std::string item; while (std::getline(ss, item, delim)) { elems.push_back(item); } } }; this approach giving me wrong answer. can please me fix this
Comments
Post a Comment