k1r1t0's blog

By k1r1t0, history, 17 months ago, In English
Problem A
Problem B
Problem C
Problem D
Problem E
  • Vote: I like it
  • +30
  • Vote: I do not like it

| Write comment?
»
17 months ago, # |
  Vote: I like it +5 Vote: I do not like it

anyone explain me C can't understand editorial

  • »
    »
    17 months ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    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).

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      if count of 0 is less than count of 1 at position i then wont we flip strings with 0 at i?

»
17 months ago, # |
Rev. 4   Vote: I like it +5 Vote: I do not like it

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.

»
17 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I had a very simple dp solution for C

code
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      17 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      $$$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.