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

Автор k1r1t0, история, 18 месяцев назад, По-английски
Problem A
Problem B
Problem C
Problem D
Problem E
Разбор задач TheForces Round #15 (Yummy-Forces)
  • Проголосовать: нравится
  • +30
  • Проголосовать: не нравится

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

anyone explain me C can't understand editorial

  • »
    »
    18 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    The approach is: To start from the last and greedily choose whether the final string (i.e. once the flips are done and all strings are the same) has a 0 or a 1 in this position. Now, say at position i from the beginning, if the count of 0 is less than the count 1 then we flip the strings that have 0 in this position. We also keep a note of all the strings we have flipped and how many times so that when we move positions lesser than i we know whether it is the same bit as given or whether it has been flipped.

    When the count of 0 and 1 is the same it does not matter which one we choose to have in the final string as it does not affect the subsequent count of 0 or 1. (i.e what we choose in position i, in this case, results in the same count for 0 and 1 in i-1 position).

»
18 месяцев назад, # |
Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

Can someone prove that the minimum weakness in $$$D$$$ will always be $$$\sqrt{n-1}$$$? I was able to guess this from dry running up to $$$n=5$$$ but wasn't sure about it.

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

I had a very simple dp solution for C

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

    please explain your dp state and transitions also. Will be helpful

    • »
      »
      »
      18 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      $$$dp[i][0]$$$ stores the min cost required to make every string equal uptill index $$$i$$$ with the character of $$$i^{th}$$$ index being 0.

      For the $$$(i+1)^{th}$$$ index we have 4 cases, I'll explain one of them, let's say the character chosen at the last index was 0 and for the current index you want to choose 1, then

      $$$dp[i+1][1] = dp[i][0] + 2 \times $$$(no of strings in which last character was 0 and current character is 0),

      because you want to retain the previous character and change the current character, which would require 2 flippings for each such string.