nitin12384's blog

Need Help in an old problem which doesnt have editorial.
By nitin12384, history, 2 years ago, In English

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

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hint: What does the end string look like?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    okay. End string will either be 0101010.... or 10101010....

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Yep, and the solution is just to calc the minimum amount of different elements between your string and one of sol strings(010, 101).

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it +4 Vote: I do not like it

      I'm not sure, but it looks like a proof for this solution a bit harder, I will write it here a bit later

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 9   Vote: I like it +3 Vote: I do not like it

      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

      → Reply