Awkwardness Minimization Problem Code: AWKMINI

Please help me solving this question i am unable to solve it.Problem link .No editorial available for this problem.

please somebody help me with this problem

please help.

just easy look at suffix sum method to solve and solve it greedily I will post answer if I will be able to solve it completely by the evening.

1 Like

Waiting for you. Please elaborate you answer.Thanks you.

I have solved this problem by using two methods. Link to solutions are:

  1. CodeChef: Practical coding for everyone
  2. CodeChef: Practical coding for everyone

Idea is same behind both of them. I have counted total number of boys and girls and then select one with less in number place them in alternate order and rest of them side by side.
e.g. If I have 3 boys and 7 girls than arrangement will be:
gggbgbgbgg or ggbgbgbggg

2 Likes

Ok!. I got it. Thanks bro.

1 Like

sorry I was late in responding what you need to do is that arrange boys and girls greedily . that is first try to arrange each boy adjacent to each girl in bgbgbg fashion then with the remaining one arrange the remaining boys(assume boys>=girls) half to the front and half to the back OK.THIS WAS GREEDY APPROACH when you get this final optimal arrange ment find the answer with the suffix array or a variable which will keep all suffix sum of indices of boys and number of boys present there and also same for girls then you can do for a girl
ans+=fabs(sum of boy suffix indices-total boys suffix*current girl index).
and finally you can print the answer

my solution

2 Likes

Thanks bro