Elearning CodePath – CTP Online Judge

Đoạn Chậu Hoa Đủ Màu Ngắn Nhất

TP005

🟢 Hard #Two Pointers #Combinatorics #Sliding Window

### 📌 Thông tin chung

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

Có $N$ chậu hoa được đánh số $1, 2, \dots, N$. Có tổng cộng $M$ màu hoa khác nhau.
**Yêu cầu:** Tìm một đoạn chậu hoa liên tiếp $A[i \dots j]$ sao cho đoạn này chứa đủ $M$ màu hoa khác nhau và có số lượng chậu hoa ít nhất (độ dài đoạn $j - i + 1$ là nhỏ nhất).

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

Cho biết các giá trị $N, M$ và dãy màu hoa $A = (A_1, A_2, \dots, A_N)$. Hãy xác định độ dài đoạn con liên tiếp ngắn nhất chứa đủ $M$ màu hoa.

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

Đọc từ tệp `DUONGHOA.INP`:

* Dòng 1: Chứa 2 số nguyên dương $N$ (số chậu hoa) và $M$ (số màu cần có).
* Dòng 2: Chứa $N$ số nguyên dương $A_1, A_2, \dots, A_N$ (màu của chậu hoa thứ $i$, $1 \le A_i \le 10^6$).

Giới hạn:
* $N \le 10^6$.
* $M \le N$.
* $1 \le A_i \le 10^6$.

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

Ghi ra tệp `DUONGHOA.OUT` một số nguyên là số lượng chậu hoa có trong bức ảnh (độ dài đoạn ngắn nhất).

---
### ✨ Ví dụ

| DUONGHOA.INP | DUONGHOA.OUT |
| :---: | :---: |
| `8 3` <br> `1 1 2 2 1 1 3 3` | `4` |

**Giải thích Ví dụ:**

$N=8, M=3$. Dãy màu: $(1, 1, 2, 2, 1, 1, 3, 3)$.
Đoạn ngắn nhất chứa đủ 3 màu $\{1, 2, 3\}$ là đoạn từ vị trí 4 đến 7: $(2, 1, 1, 3)$.
* $i=4, j=7$: $A[4..7] = (2, 1, 1, 3)$. Độ dài $7 - 4 + 1 = 4$.
* Các màu có trong đoạn: $\{1, 2, 3\}$. Đủ 3 màu.

---

✅ Đã AC: 5 / 11 submissions