Painting the Array II (Codeforces 1479B2)
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):
import re
import functools
import random
import sys
import os
import math
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
import threading
import bisect
BUFSIZE = 4096
inf = float('inf')

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))

def dfs(graph, u, visited):
    queue = deque()
    queue.append(u)
    visited[u] = True
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if not visited[v]:
                visited[v] = True
                queue.append(v)

def dedup(arr):
    n = len(arr)
    (lo, ans) = (0, 0)
    while lo < n:
        hi = lo + 1
        while hi < n and arr[hi] == arr[lo]:
            hi += 1
        ans += 1
        lo = hi
    return ans - 1

def solve():
    n = II()
    arr = LII()
    locations = defaultdict(lambda : [n])
    for idx in range(n - 1, -1, -1):
        locations[arr[idx]].append(idx)
    locations[0].append(n + 1)
    (f, s) = ([0], [0])
    for (idx, val) in enumerate(arr):
        locations[val].pop()
        if val == f[-1]:
            f.append(val)
        elif val == s[-1]:
            s.append(val)
        elif locations[f[-1]][-1] <= locations[s[-1]][-1]:
            s.append(val)
        else:
            f.append(val)
    print(dedup(f) + dedup(s))
solve()

Solution (Python):
import sys
from collections import defaultdict

def main():
    n = int(sys.stdin.readline())
    a = sys.stdin.readline().split()
    data = []
    prev = {}
    result = 0
    current = [{'val': -1, 'prev': -1}, {'val': -1, 'prev': -1}]
    for (key, val) in enumerate(a):
        data.append({'val': val, 'prev': prev[val] if val in prev else -1})
        prev[val] = key
    for el in reversed(data):
        if el['val'] == current[0]['val']:
            current[0] = el
            continue
        if el['val'] == current[1]['val']:
            current[1] = el
            continue
        result += 1
        if current[0]['prev'] < current[1]['prev']:
            current[0] = el
        else:
            current[1] = el
    print(result)
    return
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def process(A):
    n = len(A)
    S = set([])
    curr = 0
    for i in range(n):
        if i == 0 or A[i - 1] != A[i]:
            if A[i] in S:
                S = set([A[i], A[i - 1]])
            else:
                S.add(A[i])
                curr += 1
    return curr
n = int(input())
A = [int(x) for x in input().split()]
print(process(A))