Dãy dài nhất
Đề bài
Cho dãy số nguyên $A = (a_0, a_1, \ldots, a_{n-1})$. Hãy tìm một dãy con dài nhất gồm các phần tử liên tiếp trong dãy $A$ sao cho chênh lệch giữa phần tử lớn nhất và nhỏ nhất của dãy đó không vượt quá $\Delta$.
Dữ liệu:
- Dòng đầu tiên chứa hai số nguyên $n, \Delta$ $(1 \le n \le 10^6;\ 0 \le \Delta \le 2 \times 10^9)$.
- Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ $(\forall i: |a_i| \le 10^9)$.
Kết quả: một số nguyên duy nhất là độ dài dãy con tìm được.
Giới hạn: thời gian 0.5 giây, bộ nhớ 256 MB.
Subtask:
- 40% điểm đầu tiên có $n \le 10^4$.
- 40% điểm tiếp theo có $n \le 10^5$.
- 20% điểm còn lại không có giới hạn gì thêm.
10 6
10 5 4 3 2 1 9 8 7 65Giải thích ví dụ: với $\Delta = 6$, đoạn 5 4 3 2 1 (vị trí 1 → 5) có max − min $= 5 - 1 = 4 \le 6$, dài 5. Đoạn 9 8 7 6 cũng hợp lệ nhưng chỉ dài 4. Không có đoạn nào dài 6 thoả mãn (ví dụ thêm số 10 vào đầu thì $10 - 1 = 9 > 6$, thêm số 9 vào cuối thì $9 - 1 = 8 > 6$), nên đáp án là 5.
Lời mở đầu
Đây là một bài "cửa sổ trượt" kinh điển: tìm đoạn liên tiếp dài nhất thoả một điều kiện về max và min. Cái khó là khi cửa sổ trượt, ta phải biết ngay max và min hiện tại của cửa sổ, kể cả khi vừa bỏ đi phần tử bên trái. Mình sẽ đi từ cách vét cạn dễ hiểu nhất, rồi dùng multiset (đúng chủ đề Map/Set), và cuối cùng là hàng đợi đơn điệu để chạy kịp $n = 10^6$ trong 0.5 giây.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test. Mình gom các test có cùng đặc điểm thành nhóm:
| Test | n | Δ | Giá trị ai | Đáp án |
|---|---|---|---|---|
| 1–20 | 5 – 10 | 0 – 10 | -20 … 20 | 1 – 5 |
| 21–40 | 10.000 | 14.130.946 – 99.971.761 | -999.879.395 … 999.872.037 | 5.000 – 5.003 |
| 41–80 | 100.000 | 11.436.515 – 97.220.927 | -999.996.662 … 999.994.354 | 50.000 – 50.002 |
| 81–95 | 1.000.000 | 26.803.454 – 95.938.713 | -999.999.865 … 999.998.620 | 500.000 – 500.006 |
| 96–100 | 1.000.000 | 2.000.000.000 | -999.996.109 … 999.998.740 | 1.000.000 |
Một vài điều mình rút ra khi soi bộ test:
- Test 1–20 rất nhỏ ($n \le 10$, $|a_i| \le 20$), có cả trường hợp $\Delta = 0$ (khi đó dãy con hợp lệ phải gồm các số bằng nhau).
- Từ test 21 trở đi, nửa đầu dãy gồm các số nhỏ ($|a_i| \le 10^6$), nửa sau là các số ngẫu nhiên tới $\pm 10^9$. Vì thế đáp án luôn xấp xỉ $n/2$: dãy con dài nhất nằm gọn trong nửa đầu. Đây cũng là kiểu test "giết" cách vét cạn, vì với mỗi $l$ ở nửa đầu ta phải kéo $r$ đi rất xa.
- Test 96–100 có $\Delta = 2 \cdot 10^9$: mọi chênh lệch đều $\le 2 \cdot 10^9$ nên đáp án là cả dãy ($10^6$). Chênh lệch lớn nhất có thể là $10^9 - (-10^9) = 2 \cdot 10^9$, vẫn vừa kiểu
int(tối đa khoảng $2{,}147 \cdot 10^9$) nhưng sát nút, nên mình dùnglong longcho an toàn.
Bảng subtask theo đề, mình đã đối chiếu với kích thước thật của từng test:
| Subtask | Điều kiện | Các test | Cách ăn được |
|---|---|---|---|
| 1 (40%) | $n \le 10^4$ | 1 – 40 | Cách 1, 2, 3 |
| 2 (40%) | $n \le 10^5$ | 41 – 80 | Cách 2, 3 |
| 3 (20%) | $n \le 10^6$ | 81 – 100 | Cách 3 |
Ý tưởngĐoạn hợp lệ thì mọi đoạn con của nó cũng hợp lệ
Gọi đoạn $[l, r]$ là hợp lệ nếu $\max - \min \le \Delta$. Có một nhận xét rất quan trọng:
Hệ quả: khi $r$ tăng dần, vị trí $l$ nhỏ nhất để $[l, r]$ hợp lệ không bao giờ lùi lại. Vậy ta dùng hai con trỏ:
- Lần lượt đưa $a[r]$ vào cửa sổ ($r = 0, 1, \ldots, n-1$).
- Trong khi $\max - \min > \Delta$ thì bỏ $a[l]$ ra khỏi cửa sổ và tăng $l$.
- Lúc này $[l, r]$ là đoạn hợp lệ dài nhất kết thúc tại $r$, cập nhật đáp án bằng $r - l + 1$.
Mỗi phần tử vào cửa sổ 1 lần và ra tối đa 1 lần, nên chỉ có $O(n)$ thao tác thêm/bớt. Câu hỏi còn lại là: lấy max, min của cửa sổ nhanh bằng cách nào? Đó chính là chỗ khác nhau giữa cách 2 (multiset) và cách 3 (deque). Em nhập dữ liệu rồi bấm Tiếp để xem cửa sổ trượt (hàng dưới là cửa sổ đã sắp xếp, giống như cái multiset trong cách 2):
Cách 1Vét cạn mọi điểm đầu – O(n²)
Cách dễ nghĩ nhất: thử mọi điểm đầu $l$, rồi kéo dài $r$ sang phải, vừa đi vừa cập nhật mx, mn. Khi mx - mn > d thì dừng ngay vì kéo dài thêm cũng không thể hết vượt (nhận xét ở trên).
mx,mnđược khởi tạo bằnga[l]cho mỗi điểm đầu mới, rồi cập nhật dần khi thêma[r].- Lệnh
breaklà "cắt tỉa" quan trọng: không có nó thì luôn chạy đủ $n^2/2$ bước kể cả khi đáp án nhỏ.
Kết quả chạy thật: bản C++ đúng 40/100 test (Subtask 1: 40/40, Subtask 2: 0/40, Subtask 3: 0/20). Cả 40 test của subtask 1 đều chạy dưới 0.03 giây; từ test 41 trở đi bị quá thời gian. Dù có break, ở các test lớn nửa đầu dãy gồm toàn số nhỏ nên với mỗi $l$ ở nửa đầu, $r$ phải chạy tới khoảng $n/2$, tổng cộng cỡ $n^2/8$ bước: $n = 10^5$ đã là hơn $10^9$ bước.
Cách 2Hai con trỏ + multiset – O(n log n)
Áp dụng ý tưởng hai con trỏ. Để biết max, min của cửa sổ, ta bỏ mọi phần tử của cửa sổ vào một multiset: nó luôn tự sắp xếp tăng dần, nên *s.begin() là min, *s.rbegin() là max. Phải dùng multiset vì cửa sổ có thể chứa nhiều số bằng nhau.
s.erase(s.find(a[l])): chỉ xoá một bản sao củaa[l]. Nếu viếts.erase(a[l])thì multiset sẽ xoá tất cả các phần tử bằnga[l]– lỗi rất hay gặp!- Vòng
whileluôn dừng: khi cửa sổ chỉ còn 1 phần tử thì max − min $= 0 \le \Delta$. - Bản Python không có sẵn multiset nên mình dùng 2 heap (heap max và heap min) lưu cặp (giá trị, chỉ số), phần tử nào có chỉ số $< l$ ở đỉnh heap thì bỏ đi ("xoá trễ").
Kết quả chạy thật: bản C++ đúng 80/100 test (Subtask 1: 40/40, Subtask 2: 40/40, Subtask 3: 0/20). Subtask 2 chạy tối đa 0.06 giây (thời gian CPU), nhưng với $n = 10^6$ thì multiset phải cấp phát $10^6$ nút cây đỏ đen, mất khoảng 0.8–1.3 giây CPU trên máy mình, vượt giới hạn 0.5 giây.
Cách 3Hai con trỏ + hàng đợi đơn điệu – O(n)
Ta không cần cả cái multiset, chỉ cần max và min. Xét riêng max: khi thêm $a[r]$, mọi phần tử $a[j] \le a[r]$ với $j < r$ sẽ không bao giờ là max nữa (vì $a[r]$ lớn hơn hoặc bằng và còn ở lại cửa sổ lâu hơn). Nên ta bỏ luôn chúng. Kết quả là deque mx lưu các chỉ số mà giá trị giảm dần từ đầu tới cuối, và a[mx.front()] chính là max của cửa sổ. Deque mn làm ngược lại (giá trị tăng dần) để lấy min.
Khi tăng $l$, nếu chỉ số ở đầu deque nhỏ hơn $l$ (đã ra khỏi cửa sổ) thì pop_front. Vì deque lưu chỉ số tăng dần nên chỉ cần kiểm tra phần tử đầu.
- Mỗi chỉ số được
push_back1 lần và bịpop(ở đầu hoặc cuối) tối đa 1 lần, nên tổng thời gian là $O(n)$ dù có các vòngwhilelồng trongfor. - Trong vòng
while(a[mx.front()] - a[mn.front()] > d), mình tăngltrước rồi mới kiểm tra đầu 2 deque. Deque không bao giờ rỗng ở đây vì chỉ sốrluôn còn trong cả hai. - Đề yêu cầu 0.5 giây với $10^6$ số, phần đọc dữ liệu đã chiếm đáng kể, nên đừng quên
ios::sync_with_stdio(0); cin.tie(0);.
Kết quả chạy thật: bản C++ đúng 100/100 test (Subtask 1: 40/40, Subtask 2: 40/40, Subtask 3: 20/20). Test lâu nhất chỉ mất 0.13 giây (thời gian CPU), dư sức với giới hạn 0.5 giây.
Tổng kếtKết quả chạy thật trên bộ test
Mình chấm cả 3 cách (bản C++ và bản Python) trên toàn bộ 100 test với giới hạn 0.5 giây. Máy chấm của mình lúc chạy đang khá tải nên mình đo thời gian CPU của chương trình cho công bằng:
| Lời giải | Subtask 1 test 1–40 | Subtask 2 test 41–80 | Subtask 3 test 81–100 | Tổng | CPU lớn nhất (test đúng) |
|---|---|---|---|---|---|
| Cách 1 – C++ | 40/40 | 0/40 | 0/20 | 40/100 | 0.03s |
| Cách 1 – Python | 20/40 | 0/40 | 0/20 | 20/100 | 0.05s |
| Cách 2 – C++ | 40/40 | 40/40 | 0/20 | 80/100 | 0.06s |
| Cách 2 – Python | 40/40 | 40/40 | 0/20 | 80/100 | 0.50s |
| Cách 3 – C++ | 40/40 | 40/40 | 20/20 | 100/100 | 0.13s |
| Cách 3 – Python | 40/40 | 40/40 | 0/20 | 80/100 | 0.24s |
Nhận xét
Đăng nhận xét