Блог пользователя nitin12384

Автор nitin12384, история, 20 месяцев назад, По-английски

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
  • Проголосовать: не нравится

»
20 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Hint: What does the end string look like?

  • »
    »
    20 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      20 месяцев назад, # ^ |
        Проголосовать: нравится +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).

  • »
    »
    20 месяцев назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      20 месяцев назад, # ^ |
      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

    • »
      »
      »
      20 месяцев назад, # ^ |
      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