Elearning CodePath – CTP Online Judge

Minimum Length Subarray with Sum

GEN001

🟢 Hard #Binary Search #Two Pointers #Sliding Window

### 📌 Thông tin chung

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

Cho dãy số nguyên dương $A = (a_1, a_2, \dots, a_N)$ và một số nguyên dương $S$.

Một dãy con liên tiếp của dãy số có dạng $A[i..j] = (a_i, a_{i+1}, \dots, a_j)$, với $1 \le i \le j \le N$.

* **Tổng** của dãy con là $Sum(i, j) = \sum_{k=i}^{j} a_k$.
* **Độ dài** của dãy con là $j - i + 1$.

Yêu cầu: Tìm độ dài nhỏ nhất của dãy con liên tiếp $A[i..j]$ sao cho tổng của nó lớn hơn hoặc bằng $S$.
${Min Length} = \min \{ j - i + 1 \mid 1 \le i \le j \le N, \sum_{k=i}^{j} a_k \ge S \}$
Nếu không có dãy con nào thỏa mãn điều kiện tổng, kết quả là $0$.

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

Dữ liệu vào từ file `SUB.INP`:

* Dòng 1: Ghi hai số nguyên $N$ và $S$.
* Dòng 2: Ghi $N$ số nguyên $a_1, a_2, \dots, a_N$ cách nhau bởi dấu cách.

Giới hạn:
* $10 < N < 100,000$.
* $1 \le a_i \le 10,000$.
* $1 \le S < 100,000,000$.

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

Ghi ra file `SUB.OUT` một số nguyên duy nhất là độ dài nhỏ nhất tìm được. Nếu không có dãy con nào thỏa mãn, ghi $0$.

---
### 🏷 Phân Subtask

Do $N$ có thể lên đến $10^5$, thuật toán $O(N)$ là bắt buộc. Vì $a_i$ là số nguyên dương, kỹ thuật Cửa sổ trượt là áp dụng hoàn hảo.

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 1000$ | $40\%$ |
| 2 | $N \le 100,000$ | $60\%$ |

---

✅ Đã AC: 12 / 35 submissions