What is the approach to solve the problem QRK04 ?
Problem link : CodeChef: Practical coding for everyone
Below is the key idea to solve it.
If we have only one pair (i,i) then it can be separated in 1 reversal.
If we have more than 1 :
Consider 2 pairs (i,i) and (j,j).
There are 2 cases here:
i) If i!=j:
With 1 reversal we can make them separate.
Ex : iijj => ijij
ii) If i==j:
The 2 pairs are (i,i) and (i,i). With 1 reversal they cannot be separated.
Ex: iiabcii => iaibcii or ibaicii or icbaiii or iiabcii etc…
So, we cannot make them separate with one reversal.
For these cases we need atleast 2 reversals to make them separate.
From the above 2 conditions it is clear that,
Count no.of distinct pairs, and no.of equal pairs(for all i).
answer = max( ceil[no.of distinct pairs/2], max[no.of equal pairs for all i])
Don’t forget to keep this condition.
if (#[frequency of any i > ceil[arraylength/2]])
answer = -1
I have attempted a similar solution where I remove two distinct pairs for one reversal. When we can only remove similar pairs I remove one pair for one reversal. My solution is getting WA can somebody check my
[1]
[1]: https://www.codechef.com/viewsolution/12121579