The link to the problem is http://www.topcoder.com/stat?c=problem_statement&pm=10750&rd=14153
i applied kruskal to find the mst but my code fails for test case 2 *class* node{*public*: *int* start,end,weight;}; *bool* *operator* <(*const* node & first, *const* node & second){ *return* first.weight<second.weight;}*class* ActivateGame{*public*: vector<int>parent; vector<int>rank; *void* make_set(*int* i){ parent.push_back(i); rank.push_back(0);}*int* findset(*int* x){ *if*(parent[x]!=x) parent[x]=findset(parent[x]); *return* parent[x];}*bool* merge(*int* x,*int* y){ x=findset(x); y=findset(y); *if*(x!=y) { *if*(rank[y]>rank[x]) parent[x]=y; *else* { *if*(rank[x]==rank[y]) rank[x]++; parent[y]=x; } *return* *true*; } *else* *return* *false*;} *int* findMaxScore(vector <string> grid){ rank.clear();parent.clear(); map<char,int>m; *for*(*char* x='0';x<='9';x++) { m[x]=x-'0'; } *for*(*char* x='a';x<='z';x++) { m[x]=x-'a'+10; } *for*(*char* x='A';x<='Z';x++) { m[x]=x-'A'+36; } vector<node> v; *for*(*int* x=0;x<grid.size();x++) { *for*(*int* y=0;y<grid[x].size();y++) make_set(x*grid[0].size()+y); } *for*(*int* x=0;x<grid.size();x++) { *for*(*int* y=0;y<grid[0].size();y++) { *for*(*int* z=y+1;z<grid[0].size();z++) { node n1; n1.start=x*grid[0].size()+y; n1.end=x*grid[0].size()+z; n1.weight=abs(m[grid[x][y]]-m[grid[x][z]]); v.push_back(n1); } } } *for*(*int* x=0;x<grid[0].size();x++) { *for*(*int* y=0;y<grid.size();y++) { *for*(*int* z=y+1;z<grid.size();z++) { node n1; n1.start=y*grid[0].size()+x; n1.end=z*grid[0].size()+x; n1.weight=abs(m[grid[y][x]]-m[grid[z][x]]); v.push_back(n1); } } } sort(v.rbegin(),v.rend()); *for*(*int* x=0;x<v.size();x++) cout<<v[x].start<<" "<<v[x].end<<" "<<v[x].weight<<"\n"; *long* *long* *int* ans=0; *for*(*int* x=0;x<v.size();x++) { *if*(findset(v[x].start)!=findset(v[x].end)) { merge(v[x].start,v[x].end); ans+=v[x].weight;cout<<v[x].start<<" "<<v[x].end<<" "<<v[x].weight<<" "<<findset(v[x].start)<<" "<<findset(v[x].end)<<"\n"; } } *return* ans;} }; -- Anuj Kumar Third Year Undergraduate, Dept. of Computer Science and Engineering NIT Durgapur -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.