Painting the Array I
Contest: Codeforces Round 700 (Div. 1)
Difficulty rating: 1900
Tags: constructive algorithms, data structures, dp, greedy, implementation

The only difference between the two versions is that this version asks the maximal possible answer.

Homer likes arrays a lot. Today he is painting an array $$$a_1, a_2, \dots, a_n$$$ with two kinds of colors, white and black. A painting assignment for $$$a_1, a_2, \dots, a_n$$$ is described by an array $$$b_1, b_2, \dots, b_n$$$ that $$$b_i$$$ indicates the color of $$$a_i$$$ ($$$0$$$ for white and $$$1$$$ for black).

According to a painting assignment $$$b_1, b_2, \dots, b_n$$$, the array $$$a$$$ is split into two new arrays $$$a^{(0)}$$$ and $$$a^{(1)}$$$, where $$$a^{(0)}$$$ is the sub-sequence of all white elements in $$$a$$$ and $$$a^{(1)}$$$ is the sub-sequence of all black elements in $$$a$$$. For example, if $$$a = [1,2,3,4,5,6]$$$ and $$$b = [0,1,0,1,0,0]$$$, then $$$a^{(0)} = [1,3,5,6]$$$ and $$$a^{(1)} = [2,4]$$$.

The number of segments in an array $$$c_1, c_2, \dots, c_k$$$, denoted $$$\mathit{seg}(c)$$$, is the number of elements if we merge all adjacent elements with the same value in $$$c$$$. For example, the number of segments in $$$[1,1,2,2,3,3,3,2]$$$ is $$$4$$$, because the array will become $$$[1,2,3,2]$$$ after merging adjacent elements with the same value. Especially, the number of segments in an empty array is $$$0$$$.

Homer wants to find a painting assignment $$$b$$$, according to which the number of segments in both $$$a^{(0)}$$$ and $$$a^{(1)}$$$, i.e. $$$\mathit{seg}(a^{(0)})+\mathit{seg}(a^{(1)})$$$, is as large as possible. Find this number.

Input format:
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

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

Output format:
Output a single integer, indicating the maximal possible total number of segments.

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

Note:
In the first example, we can choose $$$a^{(0)} = [1,2,3,3]$$$, $$$a^{(1)} = [1,2,3]$$$ and $$$\mathit{seg}(a^{(0)}) = \mathit{seg}(a^{(1)}) = 3$$$. So the answer is $$$3+3 = 6$$$.

In the second example, we can choose $$$a^{(0)} = [1,2,3,4,5,6,7]$$$ and $$$a^{(1)}$$$ is empty. We can see that $$$\mathit{seg}(a^{(0)}) = 7$$$ and $$$\mathit{seg}(a^{(1)}) = 0$$$. So the answer is $$$7+0 = 7$$$.

Example input:
7
1 1 2 2 3 3 3

Example output:
6

Example input:
7
1 2 3 4 5 6 7

Example output:
7

Editorial:
Formally, for every sequence $$$a_1, a_2, \dots, a_n$$$, and we assume that $$$a_1, a_2, \dots, a_n$$$ are positive integers, the number of segments in $$$a$$$ is defined to be $$$$$$ \mathit{seg}(a) = \sum_{i=1}^n [ a_{i-1} \neq a_{i} ], $$$$$$ where $$$a_0 = 0$$$, and $$$[\text{Boolean expression}] = 1$$$ if the Boolean expression is true and $$$0$$$ otherwise.
Let's restate the problem as
Problem. Given a sequence $$$a_1, a_2, \dots, a_n$$$, divide it into two disjoint subsequences $$$s$$$ and $$$t$$$ such that $$$\mathit{seg}(s)+\mathit{seg}(t)$$$ is as large as possible.
Solution. We will construct two disjoint subsequences by scanning through the sequence $$$a_1, a_2, \dots, a_n$$$.
Initial setting: $$$s$$$ and $$$t$$$ are two empty sequences, and $$$a_1, a_2, \dots, a_n$$$ remains not scanned.
Move on: Suppose the last elements of $$$s$$$ and $$$t$$$ are $$$x$$$ and $$$y$$$, respectively, and $$$x = 0$$$ (resp. $$$y = 0$$$) if $$$s$$$ (resp. $$$t$$$) is empty. Let $$$z$$$ be the current element scanning through $$$a_1, a_2, \dots, a_n$$$. Our greedy strategy is described in two cases:
• Greedy Strategy I: If $$$z$$$ equals to one of $$$x$$$ and $$$y$$$, then assign $$$z$$$ to the opposite subsequence. That is, if $$$z = x$$$, then append $$$z$$$ after $$$y$$$; and if $$$z = y$$$, then append $$$z$$$ after $$$x$$$. In particular, if $$$z$$$ equals to both $$$x$$$ and $$$y$$$, the assignment could be arbitrary.
• Greedy Strategy II: If $$$z$$$ differs from both $$$x$$$ and $$$y$$$, then append $$$z$$$ after the one with the nearest next same value. That is, let $$$\mathit{next}(x)$$$ denote the next position where $$$x$$$ appears in $$$a_1, a_2, \dots, a_n$$$ after $$$z$$$, then append $$$z$$$ after $$$x$$$ if $$$\mathit{next}(x) < \mathit{next}(y)$$$, and after $$$y$$$ otherwise.
The greedy strategy is intuitive, and with this strategy, an $$$O(n)$$$ algorithm is immediately obtained. However, its proof turns out to be complicated. We append its proof for completeness.
An Intuitive Proof
Consider any optimal assignment $$$b_1, b_2, \dots, b_n$$$, we will show that our strategy is not worse than it. Let $$$a[l \dots r] = a_l, a_{l+1}, \dots, a_r$$$ be the subarray of $$$a$$$.
Now suppose we are at some position $$$p$$$, where the optimal assignment conflicts with our strategy. We assume that $$$s = (a[1\dots p])^{(0)} = s' x$$$ ends with $$$x$$$, and $$$t = (a[1\dots p])^{(1)} = t' y$$$ ends with $$$y$$$, and $$$a_{p+1} = z$$$.
Greedy Strategy I: If $$$b$$$ conflicts with Greedy Strategy I, then we must have $$$x \neq y$$$ and without loss of generality, we assume that $$$x = z$$$. Greedy Strategy I suggests we append $$$z$$$ after $$$y$$$ but $$$b$$$ suggests we append $$$z$$$ after $$$x$$$. Suppose $$$b$$$ results in the two subarrays $$$\begin{aligned} & s'xzs^{\prime \prime} \\ & t'yt^{\prime \prime} \end{aligned}$$$, while there is indeed another optimal assignment that agrees with our strategy and results in $$$\begin{aligned} & s'xt^{\prime \prime} \\ & t'yzs^{\prime \prime} \end{aligned}$$$.
Greedy Strategy II: If $$$b$$$ conflicts with Greedy Strategy II, then we must have $$$x$$$, $$$y$$$ and $$$z$$$ are distinct and without loss of generality, we assume that the next occurrence of $$$x$$$ goes in front of that of $$$y$$$. Greedy Strategy II suggests we append $$$z$$$ after $$$x$$$ but $$$b$$$ suggests we append $$$z$$$ after $$$y$$$. Suppose $$$b$$$ results in the two subarrays $$$\begin{aligned} & s'xs^{\prime \prime} \\ & t'yzt^{\prime \prime} \end{aligned}$$$. Consider two cases.
Case 1. If $$$s^{\prime \prime}$$$ does not start with $$$y$$$, then there is another optimal assignment that agrees with our strategy and results in $$$\begin{aligned} & s'xzt^{\prime \prime} \\ & t'ys^{\prime \prime} \end{aligned}$$$.
Case 2. If $$$s^{\prime \prime}$$$ starts with $$$y$$$, i.e. $$$s^{\prime \prime} = y s_1$$$, then since the first occurrence of $$$x$$$ is in front of that of $$$y$$$, we have that $$$x$$$ must be in $$$t^{\prime \prime}$$$, and assume that $$$t^{\prime \prime} = t_1 x t_2$$$. The result of $$$b$$$ is restated as $$$\begin{aligned} & s'x y s_1 \\ & t'yzt_1 x t_2 \end{aligned}$$$. We find that there is another optimal assignment that agrees with our strategy and results in $$$\begin{aligned} & s'xz t_1 y s_1 \\ & t'yx t_2 \end{aligned}$$$ (Note that $$$t_1$$$ does not contain any $$$x$$$ or $$$y$$$ in it).
A Formal Proof
The number of alternations in a sequence $$$a$$$ starting with $$$x$$$ is defined to be $$$$$$ \mathit{seg}_x(a) = \sum_{i=1}^n [ a_{i-1} \neq a_{i} ], $$$$$$ where $$$a_0 = x$$$. We note that $$$\mathit{seg}_0(a) = \mathit{seg}(a)$$$.
Let $$$f_{x,y}(a)$$$ denote the maximal possible sum of numbers of alternations in the two disjoint subsequences $$$s$$$ and $$$t$$$ of $$$a$$$, i.e. $$$$$$ f_{x, y}(a) = \max_{s, t} \{\mathit{seg}_x(s)+\mathit{seg}_y(t)\}, $$$$$$ where $$$s$$$ and $$$t$$$ ranges over all possible pairs of disjoint subsequences of $$$a$$$. It is obvious that the order of $$$x$$$ and $$$y$$$ does not matter, i.e. $$$f_{x,y}(a) = f_{y,x}(a)$$$. We note that our goal is to compute $$$f_{0,0}(a)$$$.
Let $$$\mathit{next}(x)$$$ denote the least index $$$k$$$ such that $$$a_k = x$$$, i.e. $$$\mathit{next}(x) = \min\{k \in \mathbb{N}: a_k = x\}$$$. In case no such index $$$k$$$ exists, $$$\mathit{next}(x)$$$ is defined to be $$$\infty$$$.
In fact, our problem can be solved by DP regardless of the time complexity.
Proposition 1 (Dynamic Programming). For $$$n \geq 1$$$ and every $$$x, y \in \mathbb{N}$$$, $$$$$$ f_{x,y}(a_1, a_2, \dots, a_n) = \max \{ f_{a_1, y} (a_2, \dots, a_n) + [a_1 \neq x], f_{x, a_1} (a_2, \dots, a_n) + [a_1 \neq y] \}. $$$$$$ In particular, for empty sequence $$$\epsilon$$$, we have $$$f_{x,y}(\epsilon) = 0.$$$
We can obtain some immediate properties of $$$f_{x, y}(a)$$$ by the above DP recurrence.
Proposition 2. For every $$$x, y \in \mathbb{N}$$$, $$$f_{x,0}(a) \geq f_{x,y}(a) \geq f_{x,x}(a)$$$. Moreover, if $$$\mathit{next}(y) = \infty$$$, then $$$f_{x,0}(a) = f_{x,y}(a)$$$.
After some observations, we have
Proposition 3. For every $$$x, y, z \in \mathbb{N}$$$ and sequence $$$a$$$, $$$f_{z,x}(a)+1 \geq f_{z,y}(a)$$$.
Proof: By induction on the length $$$n$$$ of sequence $$$a$$$.
Basis. It is trivial for the case $$$n = 0$$$ since the left hand side is always $$$1$$$ and the right hand side is always $$$0$$$.
Induction. Suppose true for the case $$$n = k (k \geq 0)$$$, i.e. $$$$$$ f_{z,x}(a)+1 \geq f_{z,y}(a) $$$$$$ holds for every sequence $$$a$$$ of length $$$k$$$. Now consider a sequence $$$a_1, a_2, \dots, a_{k+1}$$$ of length $$$k+1$$$.
Case 1. $$$x = y$$$. It is trivial that $$$f_{z,x}(a)+1 \geq f_{z,x}(a)$$$.
Case 2. $$$z = x \neq y$$$. We should prove that $$$f_{x,x}(a)+1 \geq f_{x,y}(a)$$$. By Proposition 1, we need to prove that $$$$$$ \begin{cases} f_{a_1,x}(a_2,\dots,a_{k+1})+[a_1 \neq x]+1 \geq f_{a_1,y}(a_2,\dots,a_{k+1})+[a_1 \neq x], \\ f_{a_1,x}(a_2,\dots,a_{k+1})+[a_1 \neq x]+1 \geq f_{x,a_1}(a_2,\dots,a_{k+1})+[a_1 \neq y]. \end{cases} $$$$$$ The second inequality is obvious. The first inequality becomes $$$$$$ f_{a_1,x}(a_2,\dots,a_{k+1})+1 \geq f_{a_1,y}(a_2,\dots,a_{k+1}), $$$$$$ which holds by induction.
Case 3. $$$x \neq y = z$$$. We should prove that $$$f_{x,y}(a)+1 \geq f_{x,x}(a)$$$. By Proposition 1, we only need to prove that $$$$$$ f_{x,a_1}(a_2,\dots,a_{k+1})+[a_1 \neq y]+1 \geq f_{a_1,x}(a_2,\dots,a_{k+1})+[a_1 \neq x], $$$$$$ which is obvious.
Case 4. $$$x \neq y, z \neq x$$$ and $$$z \neq y$$$. By Proposition 1, $$$f_{z,x}(a)+1 \geq f_{z,y}(a)$$$ is equivalent to $$$$$$ \begin{aligned} & \max\{ f_{a_1, x}(a_2,\dots,a_{k+1})+[a_1 \neq z], f_{z, a_1}(a_2,\dots,a_{k+1})+[a_1 \neq x] \} + 1 \\ & \quad \geq \max\{ f_{a_1, y}(a_2,\dots,a_{k+1})+[a_1 \neq z], f_{z, a_1}(a_2,\dots,a_{k+1})+[a_1 \neq y] \}. \end{aligned} $$$$$$
Case 4.1. $$$a_1 = z$$$. The left hand side becomes $$$$$$ \max\{ f_{z, x}(a_2,\dots,a_{k+1}), f_{z, z}(a_2,\dots,a_{k+1})+1 \} + 1 = f_{z, z}(a_2,\dots,a_{k+1})+2 $$$$$$ by induction that $$$f_{z,z}(a_2,\dots,a_{k+1})+1 \geq f_{z,x}(a_2,\dots,a_{k+1})$$$. The right hand side becomes $$$$$$ \max\{ f_{z, y}(a_2,\dots,a_{k+1}), f_{z, z}(a_2,\dots,a_{k+1})+1 \} = f_{z, z}(a_2,\dots,a_{k+1})+1 $$$$$$ by induction that $$$f_{z,z}(a_2,\dots,a_{k+1})+1 \geq f_{z,y}(a_2,\dots,a_{k+1})$$$. The inequality holds immediately.
Case 4.2. $$$a_1 = x$$$. The left hand side becomes $$$$$$ \max\{ f_{x, x}(a_2,\dots,a_{k+1})+1, f_{z, x}(a_2,\dots,a_{k+1}) \} + 1 = f_{x,x}(a_2,\dots,a_{k+1})+2 $$$$$$ by induction that $$$f_{x,x}(a_2,\dots,a_{k+1})+1 \geq f_{z,x}(a_2,\dots,a_{k+1})$$$. The right hand side becomes $$$$$$ \max\{ f_{x, y}(a_2,\dots,a_{k+1})+1, f_{z, x}(a_2,\dots,a_{k+1})+1 \}. $$$$$$ By induction that $$$f_{x,x}(a_2,\dots,a_{k+1})+1 \geq f_{x, y}(a_2,\dots,a_{k+1})+1$$$ and $$$f_{x,x}(a_2,\dots,a_{k+1})+1 \geq f_{x, z}(a_2,\dots,a_{k+1})+1$$$, the inequality holds.
Case 4.3. $$$a_1 = y$$$. The left hand side becomes $$$$$$ \max\{ f_{y, x}(a_2,\dots,a_{k+1})+1, f_{z, y}(a_2,\dots,a_{k+1})+1 \} + 1. $$$$$$ The right hand side becomes $$$$$$ \max\{ f_{y, y}(a_2,\dots,a_{k+1}), f_{z, y}(a_2,\dots,a_{k+1})+1 \} = f_{z, y}(a_2,\dots,a_{k+1})+1 $$$$$$ by induction that $$$f_{y,y}(a_2,\dots,a_{k+1})+1 \geq f_{z, y}(a_2,\dots,a_{k+1})+1$$$. The inequality immediately holds as $$$f_{z,y}(a_2,\dots,a_{k+1})$$$ appears in both sides (and can be eliminated together).
Case 4.4. $$$a_1 \notin \{x,y,z\}$$$. The left hand side becomes $$$$$$ \max\{ f_{a_1, x}(a_2,\dots,a_{k+1})+1, f_{z, a_1}(a_2,\dots,a_{k+1})+1 \} + 1. $$$$$$ The right hand side becomes $$$$$$ \max\{ f_{a_1, y}(a_2,\dots,a_{k+1})+1, f_{z, a_1}(a_2,\dots,a_{k+1})+1 \}. $$$$$$ By induction that $$$f_{a_1,x}(a_2,\dots,a_{k+1})+1 \geq \max\{f_{a_1,y}(a_2,\dots,a_{k+1}),f_{a_1,z}(a_2,\dots,a_{k+1})\}$$$, the inequality holds.
The inequality holds for all cases. Therefore, the inequality holds for $$$n = k+1$$$.
Conclusion. The inequality holds for every $$$n \geq 0$$$. $$$\Box$$$
Proposition 4. Suppose $$$a_1, a_2, \dots, a_n$$$ is a sequence. For every distinct $$$x, y, z \in \mathbb{N}$$$, i.e. $$$x \neq y, y \neq z$$$ and $$$z \neq x$$$, if $$$\mathit{next}(x) < \mathit{next}(y)$$$, then $$$f_{z,y}(a) \geq f_{z,x}(a)$$$.
Proof: By induction on the length $$$n$$$ of sequence $$$a$$$.
Basis. It is trivial for the case $$$n = 0$$$ since the both hand sides are $$$0$$$.
Induction. Suppose true for the case $$$n = k (k \geq 0)$$$, i.e. $$$$$$ f_{z,y}(a) \geq f_{z,x}(a). $$$$$$ holds for every sequence $$$a$$$ of length $$$k$$$. Now consider a sequence $$$a_1, a_2, \dots, a_{k+1}$$$ of length $$$k+1$$$.
Case 1. $$$a_1 = z$$$. By Proposition 1 and 3, the left hand side becomes $$$$$$ \max\{ f_{z, y}(a_2,\dots,a_{k+1}), f_{z, z}(a_2,\dots,a_{k+1})+1 \} = f_{z, z}(a_2,\dots,a_{k+1})+1, $$$$$$ and the right hand side becomes $$$$$$ \max\{ f_{z, x}(a_2,\dots,a_{k+1}), f_{z, z}(a_2,\dots,a_{k+1})+1 \} = f_{z, z}(a_2,\dots,a_{k+1})+1 $$$$$$ The inequality holds immediately.
Case 2. $$$a_1 = x$$$. By Proposition 1, the left hand side becomes $$$$$$ \max\{ f_{x, y}(a_2,\dots,a_{k+1})+1, f_{z, x}(a_2,\dots,a_{k+1})+1 \}, $$$$$$ and the right hand side becomes $$$$$$ \max\{ f_{x, x}(a_2,\dots,a_{k+1})+1, f_{z, x}(a_2,\dots,a_{k+1}) \}. $$$$$$ By Proposition 2, we have $$$$$$ f_{z, x}(a_2,\dots,a_{k+1}) \geq f_{x, x}(a_2,\dots,a_{k+1}), $$$$$$ and therefore, the inequality holds.
Case 3. $$$a_1 = y$$$. This is impossible because $$$\mathit{next}(x) < \mathit{next}(y)$$$, i.e. there is an element of value $$$x$$$ in front of the first element of value $$$y$$$.
Case 4. $$$a_1 \notin \{x,y,z\}$$$. The left hand side becomes $$$$$$ \max\{ f_{a_1, y}(a_2,\dots,a_{k+1})+1, f_{a_1, z}(a_2,\dots,a_{k+1})+1 \}. $$$$$$ The right hand side becomes $$$$$$ \max\{ f_{a_1, x}(a_2,\dots,a_{k+1})+1, f_{a_1, z}(a_2,\dots,a_{k+1})+1 \}. $$$$$$
Case 4.1. If $$$\mathit{next}(y) > \mathit{next}(z)$$$, then by induction we have $$$$$$ f_{a_1, y}(a_2,\dots,a_{k+1}) \geq f_{a_1, z}(a_2,\dots,a_{k+1}), $$$$$$ and (because $$$\mathit{next}(y) > \mathit{next}(x)$$$, ) $$$$$$ f_{a_1, y}(a_2,\dots,a_{k+1}) \geq f_{a_1, x}(a_2,\dots,a_{k+1}). $$$$$$ The inequality holds.
Case 4.2. If $$$\mathit{next}(y) < \mathit{next}(z)$$$, then by induction we have $$$$$$ f_{a_1, z}(a_2,\dots,a_{k+1}) \geq f_{a_1, y}(a_2,\dots,a_{k+1}), $$$$$$ and (because $$$\mathit{next}(z) > \mathit{next}(y) > \mathit{next}(x)$$$, ) $$$$$$ f_{a_1, z}(a_2,\dots,a_{k+1}) \geq f_{a_1, x}(a_2,\dots,a_{k+1}). $$$$$$ The inequality holds.
The inequality holds for all cases. Therefore, the inequality holds for $$$n = k+1$$$.
Conclusion. The inequality holds for every $$$n \geq 0$$$.
Proposition 5 (Greedy Strategy I). Suppose $$$a_1, a_2, \dots, a_n$$$ is a sequence. For every $$$x, y \in \mathbb{N}$$$, if $$$a_1 = x$$$, then $$$$$$ f_{x,y}(a_1,\dots,a_n) = f_{x,x}(a_2,\dots,a_n)+1. $$$$$$
Proof: By Proposition 1, we have $$$$$$ f_{x,y}(a_1,\dots,a_n) = \max \{ f_{x, y} (a_2, \dots, a_n), f_{x, x} (a_2, \dots, a_n) + 1 \}. $$$$$$ By Proposition 3, we have $$$$$$ f_{x,x}(a_2, \dots, a_n) + 1 \geq f_{x, y} (a_2, \dots, a_n). $$$$$$ Combining with the both above yields the proof. $$$\Box$$$
Proposition 6 (Greedy Strategy II). Suppose $$$a_1, a_2, \dots, a_n$$$ is a sequence. For every $$$x, y \in \mathbb{N}$$$ with $$$x \neq y$$$, if $$$a_1 \notin \{x,y\}$$$, then $$$$$$ f_{x,y}(a_1,\dots,a_n) = \begin{cases} f_{a_1,y}(a_2,\dots,a_n)+1 & \mathit{next}(x) < \mathit{next}(y), \\ f_{x,a_1}(a_2,\dots,a_n)+1 & \text{otherwise}. \end{cases} $$$$$$ Proof: If $$$\mathit{next}(x) < \mathit{next}(y)$$$, by Proposition 4, we have $$$$$$ f_{a_1,y}(a_2,\dots,a_n) \geq f_{x,a_1}(a_2,\dots,a_n). $$$$$$ Therefore, by Proposition 1, we have $$$f_{x,y}(a_1,\dots,a_n) = f_{a_1,y}(a_2,\dots,a_n)+1$$$.
The same statement holds for $$$\mathit{next}(x) > \mathit{next}(y)$$$. $$$\Box$$$