### nitin12384's blog

By nitin12384, history, 22 months ago,

https://mirror.codeforces.com/problemset/problem/49/D

I managed to solve this problem with a very very complicated approach involving separating groups of consecutive characters which are same. Then separating the even-sized groups and then applying some DP on them.

My submission :

https://mirror.codeforces.com/contest/49/submission/167985059

I want to ask if anyone can tell me a simpler approach. I tried to find an editorial but there were none. I also couldn't make sense of some accepted submissions that I tried to look at.

Or if someone could make some sense of this solution. https://mirror.codeforces.com/contest/49/submission/223125

• +7

 » 22 months ago, # |   +1 Hint: What does the end string look like?
•  » » 22 months ago, # ^ |   +3 okay. End string will either be 0101010.... or 10101010....
•  » » » 22 months ago, # ^ |   +4 Yep, and the solution is just to calc the minimum amount of different elements between your string and one of sol strings(010, 101).
•  » » 22 months ago, # ^ |   +3 Okay. We would require exactly one operation to change one character. So I could basically check these two cases.Case 1 : convert it to 0101010101.... Case 2 : Convert it to 1010101010....And then take the minimum. Okay. That will be correct. Damn I am an idiot. Thanks. This seems to work.
•  » » » 22 months ago, # ^ | ← Rev. 2 →   +4 I'm not sure, but it looks like a proof for this solution a bit harder, I will write it here a bit later
•  » » » 22 months ago, # ^ | ← Rev. 9 →   +3 Proof: Initially we have the string S. Suppose the solution is string A. which is equal to 010101... Let's find the first element that is correct for Si != Ai, Si-1 = Ai, or Si != Ai, Si+1 = Ai.Obviously, in all cases except(current string is equal to ~ A, where ~ is an inversion of the string A). We can take the previous or next element and the current one to change them to the correct coloring.Why we can't do better than 1 element in 1 turn? It's because if we wanna change 2 wrong elements to the correct at once they will be different(no need to prove), so we always want to change at least 1 elements.Now we can just cout the min(solve(S, A), solve(S, B)). 167988794