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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
