sameer_hack's blog

{{Problem C :- Barcode}}{{Codeforces Round 139 DIV 2}}
By sameer_hack, history, 6 years ago, In English

I am trying to solve this problem and I am not able to understand the editorial that why
dp[0][i]=min(dp[1][i-a]+sum-of-whites(i-a+1,i))
dp[1][i]=min(dp[0][i-a]+sum-of-blacks(i-a+1,i))
where a belongs to [x,y]
Editorial Link :- Editorial
Question Link :- Question

  • Vote: I like it
  • -6
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody from community can help with me this question ? Its been 7hrs and I dont know why people doesnt respond to question that may look small to you but its like mount Everest for me. :/

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

    dp[c][i] — minimal cost of painting the first i columns in NxM rectangle into a barcode the way its last stripe will be (c == 0 ? black : white).

    dp[0][i]=min(dp[1][i-a]+sum-of-whites(i-a+1,i))

    This line checks if it is optimal to paint last a lines in black.

    dp[1][i]=min(dp[0][i-a]+sum-of-blacks(i-a+1,i))

    And this line checks if it is optimal to paint last a lines in white.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain how the two recurrence relation is formed ?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, let's look on Nxi rectangle formed with the first i columns. What can we say about its last stripe? Either it's black or white and his width is ranged from x to y. Therefore, we handle 2 * (y — x + 1) variants. Let's imagine the last stripe in your subrectangle is white. It means that previous stripe's color has to be the different (black). Then, for each a x <= a <= y check the cost of oainting rectangle Nx(i-a) in stripes so it will end with the black stripe (dp[0][i-a])and add the cost of painting columns from i-a+1 to i in white (sum-of-whites(i-a+1,i)). Then we keep the best outcome.

        Same thing with the case, where the last stripe in rectangle Nxi is white, but with reverse colouring.

        → Reply