Need Help in an old problem which doesnt have editorial.

https://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://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://codeforces.com/contest/49/submission/223125

• 7 hours ago, # ^ | okay. End string will either be 0101010.... or 10101010....

  • 7 hours ago, # ^ | Yep, and the solution is just to calc the minimum amount of different elements between your string and one of sol strings(010, 101).

• 7 hours ago, # ^ | 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.

  • 7 hours 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

  • 6 hours 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