4

Need Help in an old problem which doesnt have editorial.

 2 years ago
source link: http://codeforces.com/blog/entry/105906
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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, # |

Hint: What does the end string look like?

  • 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

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK