PRECIOUS STONES UNOFFICIAL EDITORIAL
Code:KOL16F
Link: KOL16F Problem - CodeChef
Problem Statement: You need to attend q queries. In each query you will be given a string consisting of only ‘A’ and ‘R’. Beautyfactor B of the string is defined as maximum number of stones of same type. And also jth character is consecutive to (j+1)%n th character that is string is circular. You need to change 1 character i.e. if ith character is ‘A’ you can change it to ‘R’ and vice versa. Your task is to minimize B as much as possible by the change.
Difficulty:Easy
Solution:
Seeing the question you might feel its very easy. But there are a lot of corner cases to tackle. So lets start with the general case. Its clear that to minimize B by the change you need to find the existing B and make the change at the middle reducing it to B/2. So ans will be max(B/2,max2) where max2 is the second largest beautyfactor of the existing string. Example, suppose the string is AAARR so clearly values of eligible beautyfactors 3 and 2. Initially B=3. Now to minimize B we can reduce B by changing the middle A. The string becomes ARARR. So beautyfactor becomes 2. Again consider string AAAAAARR.The existing B is 6. To minimize B we can change the string to AARAAARR. So B becomes 3. Now lets deal with the corner cases. First consider when there is single character. Then even after changing B stays 1 i.e. if string was ‘A’ changing it would make ‘R’, whose B is also 1. Now consider if all the characters are same that is AAAAAA and length of string >1. Then wherever we make the change we are left with B=l-1 where l=length of string. AARAAA,RAAAAAA are possible solutions. So answer for B=l and l>1 is l-1. Now let us consider the case when existing B is 1. Then there are 2 possible cases. First if l=2 i.e. string is AR then by one change we can make B=2 that is RR. No other solution is possible. Now if l>2 then string is something like ARARAR. Notice that if you change any character B becomes 3. For example if we change first R to A string becomes AAARAR. Again if we change first A to R string becomes RRARAR with str[5]=str[0]=str[1]. So B=3. Now consider where existing B is 2. There are 2 cases possible. Firstly there exists any combination like …AARA… or …ARRA… That means beautyfactor[j]=2 and beautyfactor[j+1]=1 or vice versa. So here if we change one character B remains 2, in the examples after change string becomes …ARRA… and …AARA… respectively. Now if there is no such combination then B becomes 3 after changing. Example AARR if we change one A to R then B becomes 3 like, ARRR or RARR.
Here is the link to my code: CodeChef: Practical coding for everyone
Hope this helps.