bully....maguire's blog

How to prove that answer cannot be less than minimum of two colors in div2 — D 609
By bully....maguire, 5 years ago, In English

https://codeforces.me/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).

  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
5 years ago, # |
  Vote: I like it -19 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply