Garland
Contest: Codeforces Round 612 (Div. 1)
Difficulty rating: 1800
Tags: dp, greedy, sortings

Vadim loves decorating the Christmas tree, so he got a beautiful garland as a present. It consists of $$$n$$$ light bulbs in a single row. Each bulb has a number from $$$1$$$ to $$$n$$$ (in arbitrary order), such that all the numbers are distinct. While Vadim was solving problems, his home Carp removed some light bulbs from the garland. Now Vadim wants to put them back on.

Vadim wants to put all bulb back on the garland. Vadim defines complexity of a garland to be the number of pairs of adjacent bulbs with numbers with different parity (remainder of the division by $$$2$$$). For example, the complexity of 1 4 2 3 5 is $$$2$$$ and the complexity of 1 3 5 7 6 4 2 is $$$1$$$.

No one likes complexity, so Vadim wants to minimize the number of such pairs. Find the way to put all bulbs back on the garland, such that the complexity is as small as possible.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of light bulbs on the garland.

The second line contains $$$n$$$ integers $$$p_1,\ p_2,\ \ldots,\ p_n$$$ ($$$0 \le p_i \le n$$$) — the number on the $$$i$$$-th bulb, or $$$0$$$ if it was removed.

Output format:
Output a single number — the minimum complexity of the garland.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, one should place light bulbs as 1 5 4 2 3. In that case, the complexity would be equal to 2, because only $$$(5, 4)$$$ and $$$(2, 3)$$$ are the pairs of adjacent bulbs that have different parity.

In the second case, one of the correct answers is 1 7 3 5 6 4 2.

Example input:
5
0 5 0 2 3

Example output:
2

Example input:
7
1 0 0 5 0 0 2

Example output:
1

Editorial:
The problem can be solved using a greedy algorithm. Notice that the only information we need is parity of numbers on bulbs. So let's replace numbers by their remainders modulo $$$2$$$. Than complexity of garland will be the number of pairs of adjacent numbers that are different. Let's call such pairs as bad.
Divide garland into segments of removed bulbs. Let's call number before segment as left border and number after segment as right border. If there's no number before/after the segment than the segment doesn't have left/right border.
Notice that when filling a segment, one should place the same numbers in a row (if any). If the segment has different borders then the optimal way is to place all zeroes near zero-border and all ones near one-border. If the segment has the same borders and we place both numbers in the segment that there will be at least two bad pairs and we will achieve it by placing all zeroes and then all ones. Similarly one could prove cases with the absence of one or two borders.
If the segment has both borders and they are different then this segment always will increase the complexity by $$$1$$$. If the segment has both borders and they are different then this segment will increase the complexity by $$$0$$$ or $$$2$$$. $$$0$$$ will be in case we fill segment by numbers of the same parity as its borders. Otherwise, it will be $$$2$$$.
If the segment doesn't have at least one of borders, it will increase the complexity by $$$0$$$ if all numbers have the same parity as its border (if any) and $$$1$$$ otherwise.
So in order to minimize the complexity of garland, first of all, we should fill segments with the same borders by the numbers of the same parity. Obviously we should consider such segments in increasing length order.
Then we should fill segments with only one border such that complexity won't increase.
After that, we can place the remaining numbers arbitrary (but inside one segment we should place the same numbers in a row). Because for all remaining segments number of bad pairs is fixed.
Time complexity is $$$O(n \log n)$$$.
Also, this problem could be solved using dynamic programming.