Maximum Adjacent Pairs
Contest: Codeforces Global Round 18
Difficulty rating: 3300
Tags: constructive algorithms, graph matchings

You are given an array $$$a$$$ consisting of $$$n$$$ non-negative integers.

You have to replace each $$$0$$$ in $$$a$$$ with an integer from $$$1$$$ to $$$n$$$ (different elements equal to $$$0$$$ can be replaced by different integers).

The value of the array you obtain is the number of integers $$$k$$$ from $$$1$$$ to $$$n$$$ such that the following condition holds: there exist a pair of adjacent elements equal to $$$k$$$ (i. e. there exists some $$$i \in [1, n - 1]$$$ such that $$$a_i = a_{i + 1} = k$$$). If there are multiple such pairs for some integer $$$k$$$, this integer is counted in the value only once.

Your task is to obtain the array with the maximum possible value.

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — the number of elements in the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le \min(n, 600)$$$) — the elements of the array.

Output format:
Print $$$n$$$ integers not less than $$$1$$$ and not greater than $$$n$$$ — the array with the maximum possible value you can obtain.

If there are multiple answers, print any of them.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
4
1 1 0 2

Example output:
1 1 2 2

Example input:
5
0 0 0 0 0

Example output:
3 1 1 3 3

Editorial:
Let's consider each segment of zeroes in our sequence. Each of these segments has either odd or even length.
If a segment has length $$$2m + 1$$$ (it is odd), then it can be used to create $$$m$$$ pairs of neighboring elements, and an additional pair for either the number right before the segment, or for the number right after the segment.
If a segment has length $$$2m$$$ (it is even), then it can be used either to create $$$m$$$ pairs of neighboring elements, or $$$m-1$$$ pairs of any integers and two additional pairs for the elements that are on the borders of the segment. It's never optimal to match only one of the zeroes in an even segment with the element on the border, because we could just use the segment to create $$$m$$$ pairs instead.
Let's build an undirected graph which initially has $$$m = \max\limits_{i=1}^{n} a_i$$$ vertices (one for each integer from $$$1$$$ to $$$m$$$). Let's add the following edges and vertices to it:
• For each integer already having a pair of adjacent elements, add an auxiliary vertex and connect it with the vertex representing the integer.
• For each $$$0$$$-segment of even length, add an edge between vertices representing elements on the borders of this segment (we need at most one of these for each pair of elements on the border).
• For each $$$0$$$-segment of odd length, add an auxiliary vertex and connect it with vertices representing elements on the borders of this segment (we need at most two of these for each pair of elements on the border).
Let's find the maximum matching in this graph using some maximum matching algorithm (for example, Edmonds' blossom algorithm). Let the size of the maximum matching be $$$M$$$. It can be shown that the sum of $$$M$$$ and all values $$$\lfloor \frac{len}{2} \rfloor$$$ over all $$$0$$$-segments (where $$$len$$$ is the length of the segment) is equal to the maximum number of integers that can have a pair of neighboring elements: for each segment of even length, the edge representing it will either be in the matching (and the segment will create $$$\frac{len}{2} + 1$$$ pairs), or the edge won't belong to the matching (and the segment will create $$$\frac{len}{2}$$$ pairs). For each odd $$$0$$$-segment, we either match its vertex with a number on its border (so this segment creates $$$\frac{len - 1}{2} + 1$$$ pairs), or won't match its vertex (so this segment creates $$$\frac{len - 1}{2}$$$ pairs). The numbers already having a pair of neighboring elements will be processed by the vertices connected only to them, so they get $$$+1$$$ to the size of the matching "for free" and can't be matched with anything else (or will be matched, but won't add $$$+1$$$ for free). The maximum matching can enforce the constraint that each number is counted in the answer only once.
How fast will this solution work? Unfortunately, it can be too slow. The resulting graph can have up to $$$O(n)$$$ edges and up to $$$600^2$$$ vertices, so the standard implementation of Edmonds is not sufficient. But there are many different heuristics you can use in this problem to speed up the solution. We used the following one:
Split all vertices into two "parts", the first part will contain the vertices representing the numbers, and the second part will contain all of the other vertices. The edges can connect only vertices from the first part and the vertices from different parts, and there are only up to $$$600$$$ vertices in the first part.
Let's ignore the edges between the vertices in the first part and find the maximum matching in this graph using Kuhn's algorithm. Then, we claim that if we find the maximum general matching starting from this bipartite matching and improving it, the augmenting paths cannot both start and end in the vertices of the second part (since the number of matched vertices in the second part cannot exceed the maximum bipartite matching). Then we can search for augmenting paths only starting in vertices of the first part in Edmonds (so we need only $$$600$$$ phases of Edmonds).
Furthermore, we can speed up each phase of Edmonds as follows: if the current size of the matching is $$$M$$$, then we'll visit no more than $$$2M+2$$$ vertices while searching for an augmenting path; and if we contract each blossom in linear time of its size, each phase will work in $$$O(M^2)$$$, where $$$M$$$ is the current size of the matching (and it cannot me greater than $$$600$$$).