https://codeforces.net/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.net/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.net/contest/49/submission/223125
Hint: What does the end string look like?
okay. End string will either be 0101010.... or 10101010....
Yep, and the solution is just to calc the minimum amount of different elements between your string and one of sol strings(010, 101).
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.
I'm not sure, but it looks like a proof for this solution a bit harder, I will write it here a bit later
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