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

The only difference between the two versions is that this version asks the minimal 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 small 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 minimal 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,1,2,2]$$$, $$$a^{(1)} = [2,3]$$$ and $$$\mathit{seg}(a^{(0)}) = \mathit{seg}(a^{(1)}) = 2$$$. So the answer is $$$2+2 = 4$$$.

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

Example input:
6
1 2 3 1 2 2

Example output:
4

Example input:
7
1 2 1 2 1 2 1

Example output:
2

Editorial:
There are two approaches from different perspectives.
DP Approach
The first observation is that merging adjacent elements with the same value will not influence the answer. Therefore, without loss of generality, we may assume that there are no adjacent elements with the same value, i.e. $$$a_{i} \neq a_{i+1}$$$ for every $$$1 \leq i < n$$$.
We can solve this problem by a DP approach. Let $$$f(i)$$$ denote the minimal possible number of segments for sub-array $$$a_1, a_2, \dots, a_i$$$ over all assignments $$$b_1, b_2, \dots, b_i$$$ with $$$b_i \neq b_{i-1}$$$, where $$$b_{0} = -1$$$ for convenience. To obtain the answer, we enumerate the last position $$$1 \leq i \leq n$$$ such that $$$b_{i-1} \neq b_i$$$, and append all elements $$$a_{i+1}, a_{i+2}, \dots, a_n$$$ to the end of $$$a_i$$$, which implies an arrangement with $$$f(i)+n-i$$$ segments. The minimal number of segments will be the minimum among $$$f(i)+n-i$$$ over all $$$1 \leq i \leq n$$$.
It is straightforward to see that $$$f(0) = 0$$$ and $$$f(1) = 1$$$.
For $$$2 \leq i \leq n$$$, $$$f(i)$$$ can be computed by enumerating every possible position $$$1 \leq j < i$$$ such that $$$b_{j-1} \neq b_j = b_{j+1} = \dots = b_{i-1} \neq b_i$$$. That is, $$$a_j, a_{j+1}, \dots, a_{i-1}$$$ are assigned to the same sub-sequence, and $$$a_{j-1}$$$ and $$$a_i$$$ are assigned to the other sub-sequence. Since no adjacent elements has the same value (by our assumption), there are $$$(i-j)$$$ segments in $$$a_j, a_{j+1}, \dots, a_{i-1}$$$ (we note that the first segment, i.e. the segment of $$$a_j$$$, is counted in $$$f(j)$$$). Moreover, there will be zero or one new segment when concatenating $$$a_{j-1}$$$ and $$$a_{i}$$$ depending on whether $$$a_{j-1} = a_i$$$ or not. Hence, for every $$$2 \leq j \leq n$$$, we have $$$$$$ f(i) = \min_{1 \leq j < i} \{ f(j) + (i-j-1) + [a_{j-1} \neq a_i] \}, $$$$$$ where $$$[\text{Boolean expression}] = 1$$$ if the Boolean expression is true and $$$0$$$ otherwise. Here, we obtain an $$$O(n^2)$$$ DP solution.
To optimize the DP recurrence, we fix $$$i$$$, and let $$$g(j) = f(j) + (i-j-1) + [a_{j-1} \neq a_i]$$$, then $$$f(i) = \max_{1\leq j < i}\{g(j)\}$$$. We can observe that
Lemma 1. For $$$2 \leq i \leq n$$$, we have $$$$$$f(i) = \min\{ g(i-1), g(j^*) \},$$$$$$ where $$$j^* = \max\{1 \leq j < i : a_{j-1} = a_i\}$$$, $$$\max \emptyset = 0$$$, and $$$g(0) = +\infty$$$.
This lemma is very intuitive, which means we need only to consider two cases: one is to just append $$$a_i$$$ after $$$a_{i-1}$$$ in the same sub-sequence, and the other is to append $$$a_i$$$ after the closest $$$a_{j}$$$ with the same value, i.e. $$$a_i = a_j$$$, and then assign the elements between them (not inclusive) to the other sub-sequence. With this observation, we immediately obtain an $$$O(n)$$$ DP solution.
The proof is appended below for completeness.
Proof: For every $$$1 \leq j < i$$$, we have $$$$$$ f(i) \leq g(j) = f(j) + (i-j-1) + [a_{j-1} \neq a_i] \leq f(j) + i - j, $$$$$$ which implies that $$$f(i) - i \leq f(j) - j$$$ for every $$$1 \leq j \leq i \leq n$$$.
Now we consider $$$g(j)$$$ for every $$$1 \leq j < i$$$ in two cases.
1. $$$a_{j-1} \neq a_i$$$. We have $$$$$$\begin{aligned} g(j) & = f(j) + (i-j-1) + 1 \\ & = f(j)-j+i \\ & \geq f(i-1)-(i-1) + i \\ & = f(i-1)+1 \\ & \geq g(i-1).\end{aligned}$$$$$$
2. $$$a_{j-1} = a_i$$$. Suppose there are two different positions $$$j_1$$$ and $$$j_2$$$ such that $$$1 \leq j_1 < j_2 < i$$$ and $$$a_{j_1-1} = a_{j_2-2} = a_i$$$, then $$$$$$\begin{aligned} g(j_1) & = f(j_1) + (i-j_1-1) \\ & = f(j_1) -j_1 +i-1 \\ & \geq f(j_2)-j_2+i-1 \\ & = g(j_2). \end{aligned}$$$$$$
Greedy Approach
Consider we have a computer whose cache has only two registers. Let's suppose the array $$$a$$$ is a sequence of memory access to the computer. The problem is then converted to a more intuitive one that asks the optimal cache replacement.
Suppose the current two registers contains two memory accesses $$$x$$$ and $$$y$$$, and the current requirement memory access is $$$z$$$.
The greedy strategy is simple: If $$$z$$$ matches one of $$$x$$$ and $$$y$$$, just do nothing. Otherwise, the register that contains the memory access whose next occurrence is farther than the other will be replaced by $$$z$$$.
This strategy is know as Bélády's algorithm or farthest-in-the-future cache/page replacement policy (see here for more information). The complexity is $$$O(n)$$$ since we only need to preprocess every element's next occurrence.