Problem J
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.
Input
The input consists of:
-
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.
-
$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.
Output
Output the minimum total number of times the ice cream machines need to be cleaned in order to serve all $n$ customers.
Scoring
|
Group |
Points |
Constraints |
|
1 |
7 |
$N \leq 1\, 000$, $M \leq 10$, $K = 1$ |
|
2 |
12 |
$N \leq 1\, 000$, $M \leq 10$, $K \leq 2$ |
|
3 |
22 |
$N \leq 1\, 000$, $M \leq 10$, $K \leq 5$ |
|
4 |
11 |
$N \leq 1\, 000$, $M \leq 200$, $K \leq 100$ |
|
5 |
14 |
$N \leq 2 \cdot 10^5$, $M \leq 500$, $K \leq 100$ |
|
6 |
13 |
$N \leq 2 \cdot 10^5$, $M \leq 2 \cdot 10^5$, $K \leq 100$ |
|
7 |
21 |
$N \leq 2 \cdot 10^5$, $M \leq 2 \cdot 10^5$, $K \leq 2 \cdot 10^5$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
8 3 1 2 3 3 1 2 1 1 3 |
6 |
| Sample Input 2 | Sample Output 2 |
|---|---|
8 3 2 2 3 3 1 2 1 1 3 |
4 |
