Блог пользователя bully....maguire

Автор bully....maguire, 5 лет назад, По-английски

https://codeforces.net/contest/1269/problem/D

In editorial it is given that answer is min(black colors , white colors) .But why it cannot be less than that ? Also what is the problem with algorithm when histogram is not given in sorted order (i.e decreasing height) ?

Also one request to editorial writers . You guys are doing great job,thanks, but if you write more simple explanation it will help beginners and people in general a lot ! (I am not saying that editorial of this contest is not good).

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

Editorial showed a algorithm to build $$$min(\text{black cells}, \text{white cells})$$$ dominos. The proof for the algorithm uses the fact that the histogram is sorted, so two equal rows are always adjacent.

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

Without affecting the answer, we add '0' at the end of the histogram.

We define two operations:

  1. If the difference between neighbour two bars $$$ \geq 2 $$$, then delete vertical dominos to reduce the difference.
    Example: 8 7 3 1 -> 8 7 1 1 -> 8 1 1 1 -> 2 1 1 1
  2. Choose the rightmost two neighbour bars that have the same height. Delete the horizontal domino on the top.
    Example: 3 2 2 1 -> 3 1 1 1 -> 3 1 0 0

Repeatedly do the operation (1) and (2) until you can't. Note if no neighbour difference $$$ \geq 2 $$$ or $$$ = 0 $$$, then all neighbour difference $$$ = 1 $$$, which is "basic diagram" stated at the editorial. We then can just choose all dominos vertically on the "basic diagram".