Dãy con

Nguồn: CLUE OJ – Chương 14: Cửa sổ trượt + Tham lam Độ khó: Dễ Cửa sổ trượt Tuyển sinh 10 PTNK 2012

Đề bài

Dãy con (Đề tuyển sinh lớp 10 trường Phổ thông Năng khiếu năm 2012 – 2013)

Xét dãy $a$ gồm $n$ số nguyên $a_1, a_2, \ldots, a_n$ và một số nguyên dương $k$.

Yêu cầu: Tìm một đoạn gồm $k$ phần tử liên tiếp trong dãy $a$ có tổng lớn nhất.

Dữ liệu: Vào từ tập tin văn bản SEQUENCE.INP:

• Dòng đầu tiên chứa hai số nguyên $n$ và $k$ $(1 \le n \le 10^5,\ 1 \le k \le 1000)$.
• Dòng thứ hai chứa $n$ số nguyên của dãy $a$, mỗi phần tử có giá trị tuyệt đối không vượt quá $10^6$.

Các số trên cùng một dòng cách nhau bởi đúng một khoảng trắng.

Kết quả: Ghi ra tập tin văn bản SEQUENCE.OUT tổng của đoạn tìm được.

Giải thích ví dụ: đoạn gồm 3 số có tổng lớn nhất là $6, -4, 8$ với tổng bằng $10$.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB.

Ví dụ – input

10 3
2 -5 4 7 -8 3 6 -4 8 -1

Ví dụ – output

10

Lưu ý khi nộp trên CLUE OJ: bài này đọc/ghi bằng file đúng tên như đề (SEQUENCE.INP, SEQUENCE.OUT). Trong code mình dùng dòng if (fopen("SEQUENCE.INP", "r")) { freopen(...); freopen(...); }: có file thì đọc ghi file, không có file thì vẫn đọc bàn phím bình thường – tiện cho các bạn tự chạy thử.

Lời mở đầu

Đây là bài "nhập môn" của kỹ thuật cửa sổ trượt (sliding window): một "khung" rộng đúng $k$ ô trượt dần từ trái sang phải trên dãy số, và mỗi lần trượt ta chỉ cần cập nhật tổng bằng một phép cộng và một phép trừ thay vì cộng lại cả $k$ số. Mình sẽ đi từ cách làm "ngây thơ" nhất rồi mới tới cửa sổ trượt, chạy thật cả hai trên bộ test để các bạn thấy sự khác biệt.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

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 OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testÝ tưởngkhung trượtCách 1O(n·k)Cách 2O(n)Tổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 100 test. Đề không chia subtask, nhưng nhìn kích thước $n$ thì thấy rõ 4 mức:

Test	n	k	Giá trị $a_i$	Đáp án	Đáp án âm
1–10	7 … 17	1 … 14	-131.934 … 132.074	26.085 … 256.096	0 test
11–50	1.000	4 … 904	-132.755 … 132.756	-1.456.812 … 2.687.087	7 test
51–70	10.000	28 … 961	-132.768 … 132.763	891.495 … 4.242.986	0 test
71–100	100.000	12 … 955	-132.768 … 132.768	857.990 … 5.393.474	0 test

• Thực tế các số $a_i$ chỉ nằm trong khoảng $\pm 132\,768$ (nhỏ hơn giới hạn $10^6$ của đề), $k$ luôn $\le n$.
• Có 7 test đáp án âm (mọi đoạn $k$ số đều có tổng âm). Đây là cái bẫy kinh điển: nếu khởi tạo best = 0 thì sẽ in ra 0 – sai! Phải khởi tạo best bằng tổng của đoạn đầu tiên, hoặc một số rất nhỏ như LLONG_MIN.
• Tổng lớn nhất có thể là $k \cdot 10^6 = 10^9$ – vẫn vừa int nhưng sát nút, nên mình dùng long long cho chắc.

Kết quả chạy thật của từng cách theo từng mức (giới hạn 1 giây):

Mức	Điều kiện	Test	Cách 1 C++ (tính lại từng đoạn)	Cách 1 Python	Cách 2 C++ (cửa sổ trượt)	Cách 2 Python
Mức 1	$n \le 17$	1–10	10/10	10/10	10/10	10/10
Mức 2	$n = 1000$	11–50	40/40	40/40	40/40	40/40
Mức 3	$n = 10^4$	51–70	20/20	1/20	20/20	20/20
Mức 4	$n = 10^5$	71–100	30/30	0/30	30/30	30/30

Ý tưởngTrượt khung k ô: thêm một ô bên phải, bỏ một ô bên trái

Có tất cả $n - k + 1$ đoạn gồm $k$ phần tử liên tiếp: đoạn bắt đầu ở vị trí $1$, ở vị trí $2$, ..., ở vị trí $n - k + 1$. Ta chỉ cần tính tổng của từng đoạn rồi lấy lớn nhất.

Hãy so sánh hai đoạn kề nhau: đoạn kết thúc tại $i - 1$ là $a_{i-k}, a_{i-k+1}, \ldots, a_{i-1}$ và đoạn kết thúc tại $i$ là $a_{i-k+1}, \ldots, a_{i-1}, a_i$. Chúng chung nhau tới $k - 1$ phần tử, chỉ khác ở hai đầu:

Công thức trượt

$$S_{\text{mới}} = S_{\text{cũ}} + a_i - a_{i-k}$$ Khung dịch sang phải 1 ô: ô $a_i$ đi vào, ô $a_{i-k}$ đi ra. Mỗi lần trượt chỉ tốn $O(1)$.

Em nhập dãy và $k$ rồi bấm Tiếp để xem khung trượt (ô xanh là khung hiện tại, ô vàng vừa vào, ô đỏ vừa ra, khung tốt nhất được ghi lại bên dưới):

Dãy a: k =

Ví dụ nhanh:

Cách 1Tính lại tổng của từng đoạn – $O(n \cdot k)$

Cách tự nhiên nhất: với mỗi vị trí bắt đầu $i$, dùng một vòng for cộng $k$ số $a_i, \ldots, a_{i+k-1}$ rồi so với kết quả tốt nhất.

C++▶ Chạy tay từng dòng codeCách 1: với mỗi vị trí bắt đầu i, cộng lại k số – O(n·k).

Dữ liệu vào (stdin) – sửa thoải mái10 3 2 -5 4 7 -8 3 6 -4 8 -1

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. best = LLONG_MIN (số long long nhỏ nhất) để đoạn đầu tiên chắc chắn cập nhật được best, kể cả khi mọi tổng đều âm.
2. Điều kiện i + k - 1 <= n nghĩa là đoạn bắt đầu ở $i$ phải nằm gọn trong dãy.
3. Tổng s được khởi tạo lại bằng 0 cho mỗi đoạn – chính chỗ này làm cách 1 "phí sức": các đoạn kề nhau chung $k-1$ số nhưng lại cộng lại từ đầu.

Không gian$O(n)$

Thời gian$O(n \cdot k)$

Với $n = 10^5$, $k = 1000$ thì cỡ $10^8$ phép cộng. C++ làm $10^8$ phép cộng đơn giản chưa tới 0,1 giây nên vẫn qua hết; nhưng Python thì không.

Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.06s. Bản Python đúng 51/100 test, quá thời gian ở test 51–66, 68–100; test đúng chạy lâu nhất 0.07s (Python chậm hơn C++ cỡ vài chục lần nên $10^8$ phép cộng là quá sức).

Cách 2Cửa sổ trượt – $O(n)$

Tính tổng $k$ số đầu tiên một lần, sau đó trượt khung theo công thức $S = S + a_i - a_{i-k}$.

C++▶ Chạy tay từng dòng codeCách 2: cửa sổ trượt – thêm a[i], bỏ a[i−k], O(n).

Dữ liệu vào (stdin) – sửa thoải mái10 3 2 -5 4 7 -8 3 6 -4 8 -1

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Vòng for đầu tính tổng cửa sổ đầu tiên $a_1..a_k$, và best được khởi tạo bằng đúng tổng này (không dùng 0).
2. Trong vòng for thứ hai, khi khung kết thúc ở $i$ thì phần tử vừa rời khung là $a_{i-k}$ (khung mới là $a_{i-k+1}..a_i$).
3. Mỗi phần tử được cộng vào đúng 1 lần và trừ ra tối đa 1 lần nên tổng thời gian là $O(n)$, không còn phụ thuộc vào $k$.

Không gian$O(n)$

Thời gian$O(n)$

Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.02s. Bản Python đúng 100/100 test; test đúng chạy lâu nhất 0.11s.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
1. Tính lại tổng từng đoạn	C++	100/100	0.06s	Vẫn full điểm vì $n \cdot k \le 10^8$ phép cộng
	Python	51/100	> 1s	Quá thời gian test 51–66, 68–100
2. Cửa sổ trượt	C++	100/100	0.02s	Full điểm
	Python	100/100	0.11s	Full điểm

Ghi chú của mình: thời gian trong bảng là thời gian CPU đo trên máy mình, giới hạn 1 giây như đề. Vì đề cho $k \le 1000$ nên ngay cả cách 1 bằng C++ cũng full điểm – nhưng nếu $k$ lớn cỡ $n$ (ví dụ $n = k/2 = 10^5$) thì cách 1 sẽ thành $O(n^2)$ và gục ngay. Cửa sổ trượt chạy $O(n)$ bất kể $k$, đó là thói quen nên có. Ngoài ra, một cách tương đương là dùng mảng cộng dồn $P_i = a_1 + \ldots + a_i$, tổng đoạn kết thúc tại $i$ là $P_i - P_{i-k}$.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇