CHEFGP - Editorial::please provide an easy editorial

CHEFGP - Editorial::please provide an easy editorial

Refer to my editorial at following link

https://discuss.codechef.com/questions/114541/unofficial-editorials-october-long-challenge-part-2

Also , you can have a look at my editorial .

https://discuss.codechef.com/questions/114547/unoffcial-editorials-oct17

Expanation :
Let’s denote the number of ‘a’ in the input string as a and number of ‘b’ in the input string as b. Consider the case a >= b (else just swap the two variables and follow the same logic) only.

Let’s divide it into cases,

Case 1 : a = b, here just keep printing “ab” pair from 1 to count of a and you are done.

Case 2 : a > b, here also do the above step first. After that you will find all the b’s are now complete. Atleast one extra ‘a’ is remaining now, considering a is strictly greater than b. Now you have b number of “ab” pairs in your answer string and some reamining a’s left. Keep adding (x - 1) a’s in with each ‘a’ in the answer string till you come to the last ‘a’(which was present before the last ‘b’).

Your answer string would look like : (aaa…x times)b(aaa…x times)b…(aaa…x times)b
Now you are almost done. Till now you have not added any stars to your answer string because all the b’s are single and therefore do not require a star and the a’s have not yet formed a group which contains more than x number of a’s.
After the last ‘b’ of your answer string add the remaining a’s(if any) with stars(if needed) after each group of x number of a’s.

Your final answer would therefore look like : (aaa…x times)b(aaa…x times)b…(aaa…x times)b((aaa…x times)(aaa…x times)…*(aaa…x times)).

Case 3 : a < b, here just swap(a, b) and follow case 2 logic ! :smiley:

Here is the link to my Accepted code : https://www.codechef.com/viewsolution/15799385

Hope the above explanation is simple and clear to you. Please ask questions if you are unable to understand any part of it. I would be glad to help you.

HAPPY CODING! :slight_smile:

PS: Please do not forget to accept my answer if you like it :slight_smile:

1 Like

Another perspective of seeing @jaideeppyne 's explanation is this-

You must have done problems in combinatorics where you had to find number of ways of seating X people in middle of Y people? Consider people of 2 types, type A and type B.

We would consider the scenario as-

AXAXAXAXAXA…

Where X= Seat unoccupied, A= the person of type A. Its understood that it holds only when A>B , else we would consider arrangement BXBXBXBXBXBX…

Now, we have to fill the spaces in a way that A and B dont occur consecutively. Lets proceed taking AXAXAXAXA… as the example.

We see that its impossible for any 2 B to be consecutive, as we are seating them between 2 A’s. You will see that you can actually calculate the number of kiwis you need to give now! Given that we have to fill a space after every x apples, We can correspondingly find number of banana needed such that every one is happy. If this number is more than the bananas we have, then we have to buy kiwis.

Kiwis= Number of Bananas needed- Number of bananas we had.

If this turns out to be >0, then the arrangement is simple. After every x apples, fill in a banana and when they are exhausted, fill in kiwis.

If number of kiwis needed =0

Logic wise, its easy. After filling the in the necessary places with bananas, we can randomly choose and fill any space between 2 consecutive applies with Banana. This guarantees to work, since we are further reducing the number of consecutive fruits.

Implementation wise you might need to think on what to do, as such to avoid TLE (String copying, insertion in a string are all linear time operations. )