@amol I got accepted using the similar approach. But i performed backtracking. In each step of backtracking i chose the next option as you done. So, there can be cases where this approach fails.
Runtime error may occur because, >> while(count[k-'A'].second>=n||count[k-'A'].first==up[i]||count[k-'A'].first >> ==down[i-1]) >> k++; The above code segment assumes that you will get one of the ABCD to fill the position. But in cases where none of these are possible you will end up with out of bounds error. On Aug 7, 1:23 am, Amol Sharma <amolsharm...@gmail.com> wrote: > 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.
