icecreammachines (NOINordic contest)
Time limit: 1 seconds | Memory limit: 1024 MB | Task type: batch
Algorithms: greedy, data structures, simulation, set, map

\problemname{Ice Cream Machines}
Arnar, being a true Icelander, loves ice cream and today is just the perfect
weather to go grab some of this delicious treat. He heads out into the blizzard
to his favourite ice cream store. When he arrives he is surprised to see an
unusually short queue ahead of him; he is only the $n$th person waiting to
order!

Arnar knows this ice cream store well. They offer $m$ different flavours, and
they have $k$ ice cream machines. However, each machine can only serve one
flavour at a time, and machines need to be cleaned before they can be loaded
with a different flavour. Since cleaning a machine takes some time and Arnar is
in a hurry, he wonders if he can help the store operator determine the optimal
machine to clean every time a new flavour is needed to serve a customer, in
order to minimise the total number of times the machines need to be cleaned.

Fortunately, Iceland is a small place and Arnar knows every single person in
the queue and the flavour of ice cream they want. The store strictly enforces
a no-cutting policy, so they will serve customers in the order they arrived.
Can you help Arnar figure out the minimum number of times the ice cream
machines need to be cleaned to serve everyone in the queue, including himself?

Initially all the ice cream machines are empty and need to be cleaned before
they are loaded with their first flavour. Once an ice cream machine has been
loaded with a particular flavour, it can be used to serve any number of
customers that want that particular flavour, until the machine is cleaned and
loaded with a different flavour. A machine that is not used at all does not
need to be cleaned.

\section*{Input}
The input consists of:
\begin{itemize}
  \item One line with three integers $n$, $m$, and $k$, the number of
    customers waiting in the queue, the number of available flavours, and the
    number of ice cream machines.
  \item $n$ lines, the $i$th of which contains an integer $c_i$, where $1 \leq c_i
    \leq m$, the flavour that the $i$th customer in the queue wants.
\end{itemize}

\section*{Output}
Output the minimum total number of times the ice cream machines need to be
cleaned in order to serve all $n$ customers.

\section*{Scoring}
\begin{tabular}{|l|l|l|}
    \hline
    Group & Points & Constraints \\ \hline
    1     &  7   & $N \leq 1\,000$,          $M \leq 10$, $K = 1$ \\ \hline % simulation O(n) probably
    2     &  12  & $N \leq 1\,000$,          $M \leq 10$, $K \leq 2$ \\ \hline % DP with two machines O(n * m**2) probably
    3     &  22  & $N \leq 1\,000$,          $M \leq 10$, $K \leq 5$ \\ \hline % DP with complex state O(n * m * (m choose k)) or O(n * m * 2**m)
    4     &  11  & $N \leq 1\,000$,         $M \leq 200$, $K \leq 100$ \\ \hline % O(n**2 * k) or O(n * m * k) by pigeonhole principle
    5     &  14  & $N \leq 2 \cdot 10^5$, $M \leq 500$, $K \leq 100$ \\ \hline % O(n * m + n * k)
    6     &  13  & $N \leq 2 \cdot 10^5$, $M \leq 2 \cdot 10^5$, $K \leq 100$ \\ \hline % O(n * k)
    7     &  21  & $N \leq 2 \cdot 10^5$, $M \leq 2 \cdot 10^5$, $K \leq 2 \cdot 10^5$ \\ \hline % O(n log n)
\end{tabular}



Starter code:

Grader code:

Setup script:

Evaluation script: