Tín hiệu cảnh báo

Nguồn: HueICT 2024 vòng thi thử – Bảng Naive Độ khó: Dễ Cửa sổ trượt Mảng đánh dấu

Đề bài

Để quản lý chất lượng của sản phẩm nông nghiệp, người ta lắp đặt một hệ thống tín hiệu chẩn đoán đánh số từ $1$ đến $N$. Tuy nhiên sau một thời gian sử dụng có một số thiết bị tín hiệu bị hỏng.

Hãy tính toán số lượng thiết bị tín hiệu ít nhất cần sửa sao cho tồn tại một dãy thiết bị tín hiệu liên tiếp với ít nhất $K$ tín hiệu còn hoạt động.

Input:

Dòng đầu tiên chứa ba số nguyên $N, K$ và $B$ thoả $1 \le B, K \le N \le 10^5$.
$B$ dòng tiếp theo chứa số ID của thiết bị tín hiệu bị hỏng.

Output: in ra kết quả cần tìm, dãy thiết bị tín hiệu liên tiếp đó có thể nằm bất kỳ vị trí nào trong dãy hệ thống tín hiệu.

Subtask:

$20\%$ số test đầu tiên có $N \le 20$;
$60\%$ số test tiếp theo có $N \le 10^4$;
$20\%$ số test còn lại không có điều kiện gì thêm.

Ví dụ – input

Ví dụ – output

Giải thích ví dụ: các thiết bị hỏng là $1, 2, 5, 9, 10$. Dãy $6$ thiết bị liên tiếp từ $3$ đến $8$ chỉ có đúng một thiết bị hỏng (thiết bị $5$), sửa nó là xong → đáp án $1$. Không có dãy $6$ thiết bị liên tiếp nào mà không có thiết bị hỏng.

Lời mở đầu

Đây là bài "nhập môn" kinh điển của kỹ thuật cửa sổ trượt (sliding window): xét mọi đoạn có cùng độ dài $K$, và thay vì đếm lại từ đầu cho mỗi đoạn, ta chỉ cần thêm một ô bên phải, bỏ một ô bên trái. Mình sẽ đi từ cách đếm trực tiếp (dễ nghĩ, ăn subtask 1 và 2) tới cách cửa sổ trượt $O(N)$, kèm kết quả chạy thật trên bộ test của CLUE.

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, 3 subtask Ý tưởngđoạn dài K Cách 1O(N·K)Cách 2cửa sổ trượt O(N)

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

Test	N	K	B (số hỏng)	ID hỏng lớn nhất	Đáp án
1 – 20	2 … 18	1 … 16	1 … 14	18	0 … 5
21 – 40	24 … 100	4 … 83	7 … 88	99	0 … 65
41 – 60	113 … 978	58 … 834	44 … 721	978	21 … 707
61 – 80	1.165 … 8.433	232 … 7.636	4 … 7.049	8.433	1 … 4.377
81 – 90	16.145 … 42.041	2.711 … 29.538	1.062 … 27.718	32.768	245 … 25.718
91 – 100	100.000	3.361 … 29.790	547 … 29.425	32.768	0

Bộ test có 100 test, đúng theo 3 subtask của đề: test 1–20 có $N \le 20$, test 21–80 có $N \le 10^4$ (thật ra lớn nhất là 8.433), test 81–100 có $N$ tới $10^5$.
Không có ID hỏng nào bị lặp lại và mọi ID đều nằm trong $[1, N]$.
Điều lạ: 10 test cuối (91–100) có $N = 10^5$ nhưng mọi ID hỏng đều $\le 32768$ (có lẽ người sinh test dùng hàm rand() chỉ sinh được tới 32767), nên đoạn từ 32769 tới 100000 không có thiết bị hỏng nào → đáp án của cả 10 test đều là $0$.

Các subtask khớp với bộ test như sau (ô ghi số test đúng của từng cách – chạy thật):

Subtask	Điều kiện	Các test	Cách 1 (C++) $O(N \cdot K)$	Cách 2 (C++) cửa sổ trượt
1 (20%)	$N \le 20$	1 – 20	20/20	20/20
2 (60%)	$N \le 10^4$	21 – 80	60/60	60/60
3 (20%)	$N \le 10^5$	81 – 100	19/20	20/20

Ý tưởngChỉ cần xét các đoạn dài đúng K

Nhận xét 1. Sau khi sửa, ta cần một dãy liên tiếp có ít nhất $K$ thiết bị hoạt động. Nếu có một dãy dài hơn $K$ thì lấy $K$ thiết bị đầu của nó cũng đủ – mà số thiết bị cần sửa trong đoạn ngắn hơn chỉ có thể ít hơn hoặc bằng. Vậy ta chỉ cần xét các đoạn dài đúng $K$: $[l, l + K - 1]$ với $l = 1, 2, \ldots, N - K + 1$.

Nhận xét 2. Muốn cả đoạn hoạt động thì phải sửa mọi thiết bị hỏng trong đoạn. Đánh dấu hong[i] = 1 nếu thiết bị $i$ hỏng, khi đó số thiết bị cần sửa của đoạn chính là tổng của hong trên đoạn.

Bài toán quy về

Tìm đoạn con độ dài $K$ của mảng 0/1 hong[1..N] có tổng nhỏ nhất.

Nhận xét 3 (cửa sổ trượt). Đoạn $[l, r]$ và đoạn kế tiếp $[l + 1, r + 1]$ chung nhau gần hết. Đi từ đoạn này sang đoạn kia chỉ cần cộng thêm hong[r + 1] (ô mới vào bên phải) và trừ đi hong[l] (ô vừa ra bên trái). Giống như một "cửa sổ" dài $K$ trượt dần sang phải.

Em nhập $N$, $K$ và danh sách thiết bị hỏng rồi bấm Tiếp để xem cửa sổ trượt (ô đỏ là thiết bị hỏng, khung tím là cửa sổ hiện tại):

N = K = Thiết bị hỏng:

Ví dụ nhanh:

Cách 1Đếm lại từng đoạn – O(N·K)

Cài đặt thẳng Nhận xét 1 và 2: với mỗi điểm đầu $l$, dùng một vòng lặp đếm số thiết bị hỏng trong $[l, l + K - 1]$, lấy nhỏ nhất.

C++▶ Chạy tay từng dòng codeCách 1: với mỗi điểm đầu l, đếm lại số thiết bị hỏng trong đoạn [l, l + k − 1] – O(N·K).

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

Mảng hong khai báo toàn cục nên tự động bằng 0; đọc ID nào thì gán hong[x] = 1.
ans = k: trong một đoạn dài $K$ thì tệ nhất cũng chỉ phải sửa $K$ thiết bị.
Điều kiện l + k - 1 <= n đảm bảo đoạn không vượt quá thiết bị thứ $N$.
Có $N - K + 1$ đoạn, mỗi đoạn đếm $K$ ô → $(N - K + 1) \cdot K$ phép cộng, lớn nhất khi $K \approx N/2$: khoảng $2.5 \cdot 10^9$ với $N = 10^5$. Trong bộ test, con số này lớn nhất là khoảng $2,1 \cdot 10^9$.

Không gian$O(N)$

Thời gian$O(N \cdot K)$

Kết quả chạy thật: bản C++ đúng 99/100 test (quá 1 giây ở các test 97), test chạy lâu nhất 0.889s; bản Python đúng 76/100 test (quá thời gian ở các test 63–64, 66, 71, 74, 81–89, 91–100), lâu nhất 0.98s.

Bản C++ của Cách 1 chạy sát nút giới hạn: các test $N = 10^5$ với $K$ lớn mất xấp xỉ 1 giây – lần chạy trong bảng có 1 test vượt 1 giây, chạy lại thì có lần qua hết (0.95 giây). Nó "thoát" được nhiều như vậy là nhờ vòng lặp trong rất đơn giản (máy tự tối ưu cộng nhiều ô một lúc) và nhờ bộ test chưa có trường hợp xấu nhất $K = N/2 = 5 \cdot 10^4$. Chấm trên máy chậm hơn, hoặc gặp test xấu nhất, là quá thời gian ngay – không nên tin vào may mắn. Bản Python thì đúng với dự đoán: chỉ qua subtask 1 và một phần subtask 2:

Subtask	Điều kiện	Các test	Cách 1 (Python)	Cách 2 (Python)
1 (20%)	$N \le 20$	1 – 20	20/20	20/20
2 (60%)	$N \le 10^4$	21 – 80	55/60	60/60
3 (20%)	$N \le 10^5$	81 – 100	1/20	20/20

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

Tính tổng của cửa sổ đầu tiên $[1, K]$ một lần. Sau đó mỗi lần trượt cửa sổ sang phải một ô ($r$ là ô mới vào), cửa sổ mới là $[r - K + 1, r]$ và ô vừa rời khỏi là $r - K$:

$\text{dem}_{\text{mới}}$ $= \text{dem}_{\text{cũ}}$ $+ \text{hong}[r] - \text{hong}[r - K]$

C++▶ Chạy tay từng dòng codeCách 2: tính cửa sổ đầu tiên rồi trượt: thêm ô r, bỏ ô r − k – O(N).

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

Vòng for(int i = 1; i <= k; i++) tính cửa sổ đầu tiên; ans = dem lấy luôn nó làm đáp án tạm.
Mỗi bước trượt chỉ có 1 phép cộng, 1 phép trừ → cả thuật toán $O(N)$, không phụ thuộc $K$.
Khi $K = N$ thì vòng trượt không chạy lần nào, đáp án là số thiết bị hỏng trên cả dãy – vẫn đúng.

Một cách khác cũng $O(N)$ là dùng mảng cộng dồn pre[i] = hong[1] + … + hong[i], khi đó số thiết bị hỏng của đoạn $[l, r]$ là pre[r] - pre[l - 1]. Cửa sổ trượt gọn hơn vì không cần thêm mảng.

Không gian$O(N)$

Thời gian$O(N + B)$

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

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

Cách	Ngôn ngữ	Đúng	Lâu nhất (test đúng)	Ghi chú
1. Đếm lại từng đoạn	C++	99/100	0.889s	Quá thời gian ở test 97
	Python	76/100	0.980s	Quá thời gian ở test 63–64, 66, 71, 74, 81–89, 91–100
2. Cửa sổ trượt	C++	100/100	0.009s	Full điểm
	Python	100/100	0.067s	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 của mình (giới hạn 1 giây/test). Cách 2 (cửa sổ trượt) chạy mọi test dưới 0.01 giây với C++ và dưới 0.1 giây với Python. Mẫu bài "tìm đoạn con độ dài cố định có tổng lớn nhất / nhỏ nhất" là dạng cửa sổ trượt cơ bản nhất – các bạn nhớ công thức "thêm bên phải, bỏ bên trái" nhé.

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 😇

Lập Trình Thuật Toán