Painting the Array II (Codeforces 1480D2)
Tags: Greedy, data structures

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: 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: Output a single integer, indicating the minimal possible total number of segments.

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$$$.

Sample Inputs:
6
1 2 3 1 2 2

7
1 2 1 2 1 2 1

Sample Outputs:
4

2

Solution (Python):
n = int(input())
aa = [int(x) for x in input().split()]
choices = set()
i = 0
segcount = 0
(c1, c0) = (-1, -1)
state = None
while i < n:
    a = aa[i]
    if len(choices) < 2:
        if a in choices:
            pass
        else:
            choices.add(a)
            segcount += 1
    elif a in choices:
        if state == a:
            pass
        elif i >= 1 and aa[i] == aa[i - 1]:
            pass
        else:
            choices.clear()
            choices.add(a)
            choices.add(aa[i - 1])
            state = a
    else:
        choices.add(a)
        segcount += 1
        state = None
    i += 1
print(segcount)

Solution (Python):
def compact(array):
    result = []
    array.append(-1)
    for i in range(len(array) - 1):
        if array[i] != array[i + 1]:
            result.append(array[i])
    return result
n = int(input())
a = list(map(int, input().split()))
data = compact(a)
result = 0
last_group = -1
between = []
last = {}
for (i, el) in enumerate(data):
    if el not in last:
        result += 1
    else:
        piece = data[last[el] + 1:i]
        if len(set(piece)) != len(piece):
            result += 1
        else:
            prev = last[data[i - 1]]
            last = {data[i - 1]: prev}
    last[el] = i
print(result)

Solution (Python):
n = int(input())
a1 = list(map(int, input().split()))
sto1 = [[int(100000.0 + 5)] for i in range(n + 1)]
for i in range(n - 1, -1, -1):
    sto1[a1[i]].append(i)
(tmp1, tmp2, ans1) = (0, 0, 0)
for i in range(n):
    if a1[i] == tmp1:
        sto1[a1[i]].pop()
    elif a1[i] == tmp2:
        sto1[a1[i]].pop()
    elif sto1[tmp1][-1] < sto1[tmp2][-1]:
        tmp2 = a1[i]
        ans1 += 1
        sto1[a1[i]].pop()
    else:
        tmp1 = a1[i]
        ans1 += 1
        sto1[a1[i]].pop()
print(ans1)