i attempted a problem http://www.spoj.pl/problems/ABCD/
my logic is scan the input string and record the count of A, B, C, D in array of size 4 now sort the count array.... in the output array ....at first position put an element from count array whose count is less than n and not equal to element above them... then for other positions put element from the count array whose count is less(minimum) than n and they are not equal to previous element and element above them... it is working fine for most of the cases but i was able to figure out the cases where it failed input - BCDBCD output - ABACAH which is wrong it should be ABADAC or ADACAB..... i am getting a run time error on submission.... Please help me in correcting my logic to reach to the correct solution..... My Code is as follows - #include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<map> using namespace std; //problem four colours ABCD bool myfunc(pair<char,int> i,pair<char,int> j) { return (i.second < j.second); } int main() { int n; scanf("%d",&n); //now up and down array should have 2n colours and each colour should be present n times vector< pair<char,int> > count(4); //count array will store the frequency of each colour int i,j; char k,down[100000]; string up; count[0].first='A'; count[1].first='B'; count[2].first='C'; count[3].first='D'; count[0].second=count[1].second=count[2].second=count[3].second=0; cin >> up; //string up is scanned //get the count of each colour in up string for(i=0;i<2*n;i++) { count[up[i]-'A'].second+=1; } /* for(j=0;j<4;j++) printf("%c\t%d\t",count[j].first,count[j].second); printf("\n");*/ //now scan the above string and construct the down string together for(i=0;i<2*n;i++) { sort(count.begin(),count.end(),myfunc); /*for(j=0;j<4;j++) printf("%c\t%d\t",count[j].first,count[j].second); printf("\n");*/ if(i==0) { //this is the case when we have first element to fill k='A'; while(count[k-'A'].second>=n||count[k-'A'].first==up[i]) k++; down[i]=count[k-'A'].first; count[k-'A'].second+=1; } else { k='A'; while(count[k-'A'].second>=n||count[k-'A'].first==up[i]||count[k-'A'].first==down[i-1]) k++; down[i]=count[k-'A'].first; count[k-'A'].second+=1; } /*printf("Hi\n"); for(j=0;j<4;j++) printf("%c\t%d\t",count[j].first,count[j].second); printf("\n");*/ } down[2*n]='\0'; cout<<down; //system("pause"); return 0; } -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad -- 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.