TWO POINTS
THUẬT TOÁN HAI CON TRỎ - SLIDING WINDOW
Bài 1. Cặp số có tổng bằng S
Nguồn tham khảo/ý tưởng: Inspired by common Two Sum / Sum of Two Values using two pointers (CSES/USACO Guide, GeeksforGeeks).
Cho dãy số nguyên A gồm N phần tử và một số nguyên S. Hãy kiểm tra xem có tồn tại hai vị trí i, j khác nhau sao cho:
A[i] + A[j] = S
Nếu tồn tại in ra YES, ngược lại in ra NO.
Dữ liệu vào:
- Dòng 1: hai số nguyên N, S.
- Dòng 2: N số nguyên A[i].
Dữ liệu ra:
- In YES nếu tồn tại một cặp thỏa mãn, ngược lại in NO.
Ràng buộc:
- Subtask 1: 1 ≤ N ≤ 50, |A[i]|, |S| ≤ 1000.
- Subtask 2: 1 ≤ N ≤ 200000, |A[i]|, |S| ≤ 10^9.
Gợi ý thuật toán:
- Sắp xếp mảng.
- Dùng hai con trỏ l = 0, r = N - 1.
- Nếu A[l] + A[r] < S thì tăng l.
- Nếu A[l] + A[r] > S thì giảm r.
- Nếu bằng S thì có đáp án. Độ phức tạp: O(N log N).
Bài 2. Đếm số cặp có tổng nhỏ hơn S
Nguồn tham khảo/ý tưởng: Inspired by pair-counting two pointers problems from GeeksforGeeks/CodeChef practice.
Cho dãy số nguyên A gồm N phần tử và số nguyên S. Hãy đếm số cặp chỉ số (i, j) sao cho:
1 ≤ i < j ≤ N và A[i] + A[j] < S
Dữ liệu vào:
- Dòng 1: hai số nguyên N, S.
- Dòng 2: N số nguyên A[i].
Dữ liệu ra:
- Một số nguyên là số cặp thỏa mãn.
Ràng buộc:
- Subtask 1: 1 ≤ N ≤ 100, |A[i]|, |S| ≤ 1000.
- Subtask 2: 1 ≤ N ≤ 200000, |A[i]|, |S| ≤ 10^9.
Gợi ý thuật toán:
- Sắp xếp mảng tăng dần.
- Đặt l = 0, r = N - 1.
- Nếu A[l] + A[r] < S, khi đó với A[l], tất cả vị trí từ l+1 đến r đều ghép được, cộng thêm r-l và tăng l.
- Ngược lại giảm r. Độ phức tạp: O(N log N).
Bài 3. Đếm đoạn con có tổng bằng X
Nguồn tham khảo/ý tưởng: Inspired by CSES Subarray Sums I and two-pointer/sliding-window explanations.
Cho dãy A gồm N số nguyên dương và số nguyên dương X. Hãy đếm số đoạn con liên tiếp có tổng đúng bằng X.
Dữ liệu vào:
- Dòng 1: hai số nguyên N, X.
- Dòng 2: N số nguyên dương A[i].
Dữ liệu ra:
- Một số nguyên là số đoạn con liên tiếp có tổng bằng X.
Ràng buộc:
- Subtask 1: 1 ≤ N ≤ 100, 1 ≤ A[i], X ≤ 1000.
- Subtask 2: 1 ≤ N ≤ 200000, 1 ≤ A[i], X ≤ 10^9.
Gợi ý thuật toán:
- Vì A[i] dương, có thể dùng cửa sổ trượt.
- Tăng con trỏ phải để thêm phần tử vào tổng.
- Khi tổng lớn hơn X thì tăng con trỏ trái để bỏ bớt phần tử.
- Khi tổng bằng X thì cộng đáp án. Độ phức tạp: O(N).
Bài 4. Đoạn con dài nhất có tổng không vượt quá S
Nguồn tham khảo/ý tưởng: Inspired by sliding-window/two-pointer subarray optimization examples.
Cho dãy A gồm N số nguyên dương và số nguyên dương S. Tìm độ dài lớn nhất của một đoạn con liên tiếp có tổng không vượt quá S.
Dữ liệu vào:
- Dòng 1: hai số nguyên N, S.
- Dòng 2: N số nguyên dương A[i].
Dữ liệu ra:
- Một số nguyên là độ dài lớn nhất tìm được.
- Nếu không có phần tử nào có thể chọn, in 0.
Ràng buộc:
- Subtask 1: 1 ≤ N ≤ 100, 1 ≤ A[i], S ≤ 1000.
- Subtask 2: 1 ≤ N ≤ 200000, 1 ≤ A[i], S ≤ 10^9.
Gợi ý thuật toán:
- Dùng hai con trỏ l, r biểu diễn cửa sổ [l..r].
- Khi thêm A[r] làm tổng vượt S thì tăng l đến khi tổng hợp lệ.
- Cập nhật đáp án bằng r-l+1. Độ phức tạp: O(N).
Bài 5. Chọn hai cột chứa nhiều nước nhất
Nguồn tham khảo/ý tưởng: Inspired by Container With Most Water two-pointer problem (LeetCode/GeeksforGeeks/AlgoMonster).
Có N cột thẳng đứng, cột thứ i có chiều cao H[i]. Chọn hai cột i và j, i < j, để tạo thành một “bình chứa nước”. Lượng nước chứa được là:
min(H[i], H[j]) × (j - i)
Hãy tìm lượng nước lớn nhất có thể chứa.
Dữ liệu vào:
- Dòng 1: số nguyên N.
- Dòng 2: N số nguyên dương H[i].
Dữ liệu ra:
- Một số nguyên là lượng nước lớn nhất.
Ràng buộc:
- Subtask 1: 2 ≤ N ≤ 100, 1 ≤ H[i] ≤ 1000.
- Subtask 2: 2 ≤ N ≤ 200000, 1 ≤ H[i] ≤ 10^9.
Gợi ý thuật toán:
- Đặt l = 0, r = N - 1.
- Tính diện tích với hai cột hiện tại.
- Muốn có cơ hội tăng diện tích, di chuyển con trỏ đang đứng ở cột thấp hơn.
- Lặp đến khi l = r.
Độ phức tạp: O(N).
Danh sách bài tập
| STT | Mã bài | Tên bài | Kỹ thuật chính |
|---|---|---|---|
| 1 | BAI01_SUBSUMX |
Đếm đoạn con có tổng bằng X | Hai con trỏ, tổng cửa sổ |
| 2 | BAI02_MINLEN_SUM |
Đoạn con ngắn nhất có tổng ít nhất S | Sliding window tối ưu độ dài |
| 3 | BAI03_ATMOST_K_DISTINCT |
Đếm đoạn con có không quá K giá trị khác nhau | Two pointers + tần suất |
| 4 | BAI04_DOI_K_KY_TU |
Đoạn con dài nhất sau khi đổi tối đa K ký tự | Sliding window trên xâu |
| 5 | BAI05_BA_DIEM |
Ba điểm trên một đường thẳng | Two pointers + tổ hợp |
| 6 | BAI06_WINDOW_MEDIAN |
Cửa sổ trượt tìm trung vị | Sliding window + multiset |
| 7 | BAI07_WINDOW_COST |
Chi phí biến cửa sổ thành bằng nhau | Median + tổng hai nửa |
| 8 | BAI08_MEX_FIXED |
Đếm đoạn con có MEX cố định | Frequency + tách đoạn + two pointers |
1. Đếm đoạn con có tổng bằng X
Mã bài: BAI01_SUBSUMX
Đề bài
Cho dãy a gồm n số nguyên dương và số nguyên X. Hãy đếm số đoạn con liên tiếp có tổng đúng bằng X.
Dữ liệu vào
- Dòng 1:
n X - Dòng 2:
nsố nguyên dươnga[i]
Dữ liệu ra
In ra số đoạn con có tổng bằng X.
Chia subtask
| Subtask | Ràng buộc | Hướng giải |
|---|---|---|
| Sub 1 | n <= 100 |
Duyệt mọi đoạn O(n^2). |
| Sub 2 | n <= 5000 |
Dùng tổng tiền tố hoặc tối ưu nhẹ. |
| Sub 3 | n <= 200000, a[i] > 0 |
Hai con trỏ O(n). |
Ý tưởng thuật toán
Vì mọi a[i] đều dương, khi tăng r thì tổng cửa sổ tăng, khi tăng l thì tổng giảm. Duy trì cửa sổ [l..r] và biến sum.
- Nếu
sum > Xthì tănglđể giảm tổng. - Nếu
sum == Xthì tăng đáp án.
Ví dụ
Input
8 10
2 3 5 5 1 9 1 10
Output
4
2. Đoạn con ngắn nhất có tổng ít nhất S
Mã bài: BAI02_MINLEN_SUM
Đề bài
Cho dãy a gồm n số nguyên dương và số nguyên S. Tìm độ dài nhỏ nhất của đoạn con liên tiếp có tổng lớn hơn hoặc bằng S. Nếu không có, in -1.
Dữ liệu vào
- Dòng 1:
n S - Dòng 2:
nsố nguyên dươnga[i]
Dữ liệu ra
In ra độ dài nhỏ nhất, hoặc -1 nếu không tồn tại.
Chia subtask
| Subtask | Ràng buộc | Hướng giải |
|---|---|---|
| Sub 1 | n <= 100 |
Duyệt mọi đoạn. |
| Sub 2 | n <= 5000 |
Tổng tiền tố. |
| Sub 3 | n <= 200000 |
Sliding window O(n). |
Ý tưởng thuật toán
Mở rộng r để tổng đạt ít nhất S. Khi sum >= S, cập nhật đáp án rồi tăng l để thử rút ngắn đoạn. Vì a[i] dương nên việc bỏ a[l] làm tổng không tăng.
Ví dụ
Input
6 11
1 2 3 4 5 6
Output
2
3. Đếm đoạn con có không quá K giá trị khác nhau
Mã bài: BAI03_ATMOST_K_DISTINCT
Đề bài
Cho dãy a gồm n số nguyên và số K. Hãy đếm số đoạn con liên tiếp có không quá K giá trị khác nhau.
Dữ liệu vào
- Dòng 1:
n K - Dòng 2:
nsố nguyêna[i]
Dữ liệu ra
In ra số đoạn con thỏa mãn.
Chia subtask
| Subtask | Ràng buộc | Hướng giải |
|---|---|---|
| Sub 1 | n <= 100 |
Duyệt mọi đoạn và đếm distinct. |
| Sub 2 | n <= 5000 |
Duyệt + set/tần suất. |
| Sub 3 | n <= 200000 |
Two pointers + map/unordered_map. |
Ý tưởng thuật toán
Dùng bảng tần suất cho cửa sổ [l..r]. Khi số lượng giá trị khác nhau vượt K, tăng l đến khi hợp lệ.
Với mỗi r, tất cả đoạn kết thúc tại r và bắt đầu từ l..r đều hợp lệ, nên cộng thêm:
r - l + 1
Ví dụ
Input
5 2
1 2 1 3 4
Output
10
4. Đoạn con dài nhất sau khi đổi tối đa K ký tự
Mã bài: BAI04_DOI_K_KY_TU
Đề bài
Cho xâu s độ dài n chỉ gồm hai ký tự a và b. Bạn được đổi tối đa K ký tự. Tìm độ dài lớn nhất của đoạn con liên tiếp có thể biến thành toàn một ký tự.
Dữ liệu vào
- Dòng 1:
n K - Dòng 2: xâu
s
Dữ liệu ra
In ra độ dài lớn nhất.
Chia subtask
| Subtask | Ràng buộc | Hướng giải |
|---|---|---|
| Sub 1 | n <= 100 |
Duyệt mọi đoạn. |
| Sub 2 | n <= 5000 |
Duyệt đoạn và đếm số ký tự cần đổi. |
| Sub 3 | n <= 200000 |
Sliding window hai lần. |
Ý tưởng thuật toán
Tính độ dài lớn nhất có thể biến thành toàn a, sau đó tính tương tự với toàn b.
Với một ký tự mục tiêu, trong cửa sổ chỉ cho phép tối đa K ký tự khác mục tiêu. Nếu vượt quá K, tăng l.
Ví dụ
Input
7 2
abbaaba
Output
5
5. Ba điểm trên một đường thẳng
Mã bài: BAI05_BA_DIEM
Đề bài
Cho n điểm trên trục số có tọa độ tăng dần và số D. Đếm số bộ ba chỉ số i < j < k sao cho:
x[k] - x[i] <= D
Dữ liệu vào
- Dòng 1:
n D - Dòng 2:
ntọa độ tăng dần
Dữ liệu ra
In ra số bộ ba thỏa mãn.
Chia subtask
| Subtask | Ràng buộc | Hướng giải |
|---|---|---|
| Sub 1 | n <= 100 |
Ba vòng lặp. |
| Sub 2 | n <= 5000 |
Hai vòng lặp hoặc chặt nhị phân. |
| Sub 3 | n <= 200000 |
Two pointers O(n). |
Ý tưởng thuật toán
Với mỗi r, tăng l đến khi:
x[r] - x[l] <= D
Khi đó có:
m = r - l
điểm đứng trước r nằm trong đoạn hợp lệ. Số cách chọn hai điểm còn lại là:
C(m, 2) = m * (m - 1) / 2
Ví dụ
Input
5 3
1 2 3 5 8
Output
1
6. Cửa sổ trượt tìm trung vị
Mã bài: BAI06_WINDOW_MEDIAN
Đề bài
Cho dãy a gồm n số nguyên và số K. Với mỗi đoạn con liên tiếp độ dài K, in ra trung vị của đoạn. Nếu K chẵn, lấy trung vị dưới.
Dữ liệu vào
- Dòng 1:
n K - Dòng 2:
nsố nguyêna[i]
Dữ liệu ra
In ra n - K + 1 số, là trung vị của từng cửa sổ.
Chia subtask
| Subtask | Ràng buộc | Hướng giải |
|---|---|---|
| Sub 1 | n <= 100 |
Sắp xếp từng cửa sổ. |
| Sub 2 | n <= 5000 |
Cập nhật cửa sổ bằng vector/multiset. |
| Sub 3 | n <= 200000 |
Hai multiset, O(n log K). |
Ý tưởng thuật toán
Duy trì hai multiset:
low: chứa nửa nhỏ.high: chứa nửa lớn.
Cân bằng sao cho low có đúng (K + 1) / 2 phần tử. Trung vị là phần tử lớn nhất của low.
Ví dụ
Input
8 3
2 4 3 5 8 1 2 1
Output
3 4 5 5 2 1
7. Chi phí biến các phần tử trong cửa sổ thành bằng nhau
Mã bài: BAI07_WINDOW_COST
Đề bài
Cho dãy a gồm n số nguyên và số K. Với mỗi cửa sổ độ dài K, tính chi phí nhỏ nhất để biến mọi phần tử trong cửa sổ thành cùng một giá trị.
Dữ liệu vào
- Dòng 1:
n K - Dòng 2:
nsố nguyêna[i]
Dữ liệu ra
In ra n - K + 1 chi phí tương ứng.
Chia subtask
| Subtask | Ràng buộc | Hướng giải |
|---|---|---|
| Sub 1 | n <= 100 |
Sắp xếp từng cửa sổ và tính trực tiếp. |
| Sub 2 | n <= 5000 |
Tối ưu bằng cấu trúc dữ liệu đơn giản. |
| Sub 3 | n <= 200000 |
Hai multiset + tổng hai nửa. |
Ý tưởng thuật toán
Giá trị tối ưu là trung vị. Nếu m là trung vị, chi phí bằng tổng:
|a[i] - m|
trong cửa sổ.
Duy trì low, high cùng sumLow, sumHigh để tính nhanh:
cost = m * |low| - sumLow + sumHigh - m * |high|
Ví dụ
Input
8 3
2 4 3 5 8 1 2 1
Output
2 2 5 7 6 1
8. Đếm đoạn con có MEX cố định
Mã bài: BAI08_MEX_FIXED
Đề bài
MEX của một tập số là số nguyên không âm nhỏ nhất không xuất hiện trong tập. Cho dãy a gồm n số nguyên không âm và số M. Đếm số đoạn con liên tiếp có MEX bằng M.
Dữ liệu vào
- Dòng 1:
n M - Dòng 2:
nsố nguyên không âma[i]
Dữ liệu ra
In ra số đoạn con có MEX bằng M.
Chia subtask
| Subtask | Ràng buộc | Hướng giải |
|---|---|---|
| Sub 1 | n <= 100 |
Duyệt mọi đoạn, tính MEX. |
| Sub 2 | n <= 5000 |
Duyệt + tần suất. |
| Sub 3 | n <= 200000 |
Tách theo vị trí M + two pointers. |
Ý tưởng thuật toán
Đoạn có MEX bằng M khi:
- Chứa đủ các giá trị
0, 1, ..., M - 1. - Không chứa giá trị
M.
Vì không được chứa M, ta chia dãy thành các đoạn con không có M. Trên từng đoạn, dùng hai con trỏ để đếm số đoạn chứa đủ các giá trị 0..M-1.
Ví dụ
Input
6 2
0 1 2 0 1 3
Output
4