Rainbow Triples
Contest: Grakn Forces 2020
Difficulty rating: 3300
Tags: binary search, data structures, flows, greedy

You are given a sequence $$$a_1, a_2, \ldots, a_n$$$ of non-negative integers.

You need to find the largest number $$$m$$$ of triples $$$(i_1, j_1, k_1)$$$, $$$(i_2, j_2, k_2)$$$, ..., $$$(i_m, j_m, k_m)$$$ such that:

- $$$1 \leq i_p < j_p < k_p \leq n$$$ for each $$$p$$$ in $$$1, 2, \ldots, m$$$;
- $$$a_{i_p} = a_{k_p} = 0$$$, $$$a_{j_p} \neq 0$$$;
- all $$$a_{j_1}, a_{j_2}, \ldots, a_{j_m}$$$ are different;
- all $$$i_1, j_1, k_1, i_2, j_2, k_2, \ldots, i_m, j_m, k_m$$$ are different.

Input format:
The first line of input contains one integer $$$t$$$ ($$$1 \leq t \leq 500\,000$$$): the number of test cases.

The first line of each test case contains one integer $$$n$$$ ($$$1 \leq n \leq 500\,000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq n$$$).

The total sum of $$$n$$$ is at most $$$500\,000$$$.

Output format:
For each test case, print one integer $$$m$$$: the largest number of proper triples that you can find.

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

Note:
In the first two test cases, there are not enough elements even for a single triple, so the answer is $$$0$$$.

In the third test case we can select one triple $$$(1, 2, 3)$$$.

In the fourth test case we can select two triples $$$(1, 3, 5)$$$ and $$$(2, 4, 6)$$$.

In the fifth test case we can select one triple $$$(1, 2, 3)$$$. We can't select two triples $$$(1, 2, 3)$$$ and $$$(4, 5, 6)$$$, because $$$a_2 = a_5$$$.

Example input:
8
1
1
2
0 0
3
0 1 0
6
0 0 1 2 0 0
6
0 1 0 0 1 0
6
0 1 3 2 0 0
6
0 0 0 0 5 0
12
0 1 0 2 2 2 0 0 3 3 4 0

Example output:
0
0
1
2
1
1
1
2

Editorial:
Let's reformulate this problem: you should choose different $$$i$$$ with different $$$a_i > 0$$$, and for each of them choose one zero to the left and one zero to the right (i.e. for each chosen guy we can assume that we have two vertices in the bipartite graph, and we want to match the left of them with some zero to the left, and the right of them with some zero to the right).
Denote the number of zeroes as $$$z$$$.
Observation 1. The answer does not exceed $$$\frac{z}{2}$$$.
Observation 2. If the number of zeroes to the right of number is $$$\geq \frac{z}{2}$$$, then we will always be able to match it with some zeroes to the right (from Observation 2). You can also make a similar symmetrical observation.
Observation 3. Using observation 2, we can separate non-zero numbers into two groups, s.t. numbers on prefix can always be matched with zero to the right, and numbers on suffix can always be matched with zero to the left. Let's denote those sets as $$$L$$$ (prefix) and $$$R$$$ suffix.
Observation 4. For each colour only two numbers are interesting: the rightmost in $$$L$$$ and the leftmost in $$$R$$$. It is easy to show, for example, if you decided to take some colour but not in the rightmost in $$$L$$$ position, you can replace it by the rightmost position in $$$L$$$ (of course, corresponding zero to the left can be matched with the new position, as you moved it to the right, and you can still match it with some zero to the right). Symmetrical proof holds for $$$R$$$.
Observation 5. We derive the following problem: for each colour you want to either choose it in the $$$L$$$, choose it in the $$$R$$$, or not choose it all. And if you choose it in $$$L$$$, then you want to match it with some zeroes on the prefix. If you choose it in $$$R$$$, then you want to match it with some zeroes on the suffix. So we can replace each colour to the tuple $$$(l,r)$$$ which means that this colour can be matched with either some zero on the prefix of length $$$l$$$ of some zero on the suffix of length $$$r$$$. And our goal is to find the largest matching.
Observation 6. The maximum matching for this type of graph can be found easily: move $$$x$$$ backwards, and each time match $$$x$$$ with some unmatched pair $$$(l, r)$$$ such that $$$l \geq x$$$, and $$$r$$$ is minimum among them.
Observation 7. After you saw observation 6, you can optimize the solution with a priority queue. And don't remember that the real answer is the smaller value of $$$\frac{z}{2}$$$ and your matching size.
P.S. You can also formulate this problem as a matroid intersection, and find the answer using the minimax formula for the matroid intersection + segment tree.