Unable to solve QRK04 Problem

What is the approach to solve the problem QRK04 ?
Problem link : www.codechef.com/QCDJ2016/problems/QRK04

1 Like

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]: https://www.codechef.com/viewsolution/12121579