Elearning CodePath – CTP Online Judge

Đoạn Dây Đèn Đủ Màu Ngắn Nhất

MAU

🟢 Hard #Two Pointers #Combinatorics #Sliding Window #Interval

### 📌 Thông tin chung

---
### 📝 Định nghĩa Đoạn Dây Đèn Đủ Màu

Dây đèn nhấp nháy có $N$ đèn. Mỗi đèn có một màu, thuộc một trong $M$ màu đã biết (mã hóa từ $1$ đến $M$).

**Đoạn dây đèn đủ màu** là đoạn dây đèn với các đèn liên tiếp ($A[i \dots j]$) và có đủ $M$ màu (tức là tập hợp các màu trong đoạn phải chứa $\{1, 2, \dots, M\}$).

---
### 📝 Bài toán

Cho biết các giá trị $N, M$ và dãy màu $A = (A_1, A_2, \dots, A_N)$. Tìm đoạn dây đèn đủ màu mà có số đèn ít nhất (độ dài đoạn ngắn nhất).

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ tệp văn bản `MAU.INP` gồm 2 dòng:

* Dòng 1: Chứa 2 số nguyên dương $N$ (số đèn) và $M$ (số màu).
* Dòng 2: Chứa $N$ số nguyên dương $A_1, A_2, \dots, A_N$ ($1 \le A_i \le M$).

---
### 📤 Định dạng Đầu ra

Đưa ra tệp văn bản `MAU.OUT` một số nguyên duy nhất là độ dài đoạn dây đèn đủ màu ngắn nhất. (Trường hợp không thỏa mãn thì ghi ra số 0).

---
### ✨ Ví dụ

| MAU.INP | MAU.OUT | Giải thích |
| :---: | :---: | :--- |
| `7 3` <br> `1 2 2 1 1 3 3` | `4` | Dãy đèn màu ở vị trí 3, 4, 5, 6 là `2 1 1 3`. Chứa đủ 3 màu $\{1, 2, 3\}$. Độ dài là 4. |

---

### Ràng buộc:
* 50% số điểm: $N, M \le 10^3$.
* 50% số điểm: $N, M \le 10^7$.

✅ Đã AC: 2 / 26 submissions