Dãy số (Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng B)

Nguồn: Tin học trẻ 2024 Độ khó: Khá Cửa sổ trượt Hàng đợi 2 đầu Tổng tiền tố Tuần hoàn

Đề bài

Nguồn đề: Hội thi Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng B (bài Dãy số). Vòng khu vực dùng chung một đề cho cả ba miền Bắc, Trung, Nam. Đề bên dưới do mình viết lại bằng lời của mình cho dễ hiểu (giữ đúng nghĩa, đúng số liệu và ví dụ của đề gốc).

Cho dãy số nguyên dương $A = (a_1, a_2, \dots, a_n)$ và số nguyên dương $k$. Viết dãy $A$ liên tiếp $k$ lần ta được dãy $A^k$ có $m = n \times k$ phần tử: $A^k = (a_1, \dots, a_n, a_1, \dots, a_n, \dots, a_1, \dots, a_n)$. Đánh số lại các phần tử của $A^k$ từ $1$ tới $m$.

Xét đoạn gồm $d$ phần tử liên tiếp của $A^k$ bắt đầu từ phần tử thứ $i$ ($1 \le i \le m - d + 1$). Đoạn đó gọi là đoạn đẹp nếu hai lần phần tử nhỏ nhất của đoạn lớn hơn trung bình cộng của đoạn:

$$2 \times \min(\text{đoạn}) > \frac{\text{tổng các phần tử của đoạn}}{d}.$$

Yêu cầu: đếm số chỉ số $i$ ($1 \le i \le m - d + 1$) mà đoạn $d$ phần tử bắt đầu từ $i$ là đoạn đẹp.

Dữ liệu vào:

• Dòng 1: ba số nguyên dương $n, k, d$ ($n, k \le 10^5$; $d \le n \times k$).
• Dòng 2: $n$ số nguyên dương $a_1, a_2, \dots, a_n$ ($a_i \le 10^6$).

Kết quả: một số nguyên là số chỉ số $i$ cần đếm.

Subtask:

• Subtask 1 (30%): $n \times k \le 3 \cdot 10^3$;
• Subtask 2 (30%): $n \times k \le 4 \cdot 10^5$;
• Subtask 3 (30%): $n \times k \le 5 \cdot 10^7$;
• Subtask 4 (10%): không có ràng buộc gì thêm.

Giới hạn thời gian: 1 giây. Dữ liệu nhập từ bàn phím, in ra màn hình.

Ví dụ 1 – input

2 3 3
1 3

Ví dụ 1 – output

2

Ví dụ 2 – input

3 10 3
1 5 10

Ví dụ 2 – output

0

Giải thích ví dụ 1: $A^3 = (1, 3, 1, 3, 1, 3)$, $d = 3$. Các đoạn bắt đầu ở $i = 1$ và $i = 3$ là $(1, 3, 1)$: $2 \times 1 = 2 > \frac{5}{3}$ nên đẹp. Các đoạn bắt đầu ở $i = 2$ và $i = 4$ là $(3, 1, 3)$: $2 \times 1 = 2 < \frac{7}{3}$ nên không đẹp. Đáp án là $2$.

Ví dụ 2: mọi đoạn 3 phần tử đều là một hoán vị vòng của $(1, 5, 10)$, có $2 \times 1 = 2 < \frac{16}{3}$ nên không đoạn nào đẹp.

Lời mở đầu

Đề nhìn thì đơn giản: duyệt từng đoạn, tính min và tổng, so sánh. Cái khó nằm ở kích thước: $m = n \times k$ có thể tới $10^{10}$ – không thể dựng dãy, cũng không thể duyệt từng đoạn. Bài này rất hợp để luyện "nâng cấp" lời giải qua từng subtask: vét cạn $O(m \cdot d)$ → cửa sổ trượt $O(m)$ → nhận ra tính tuần hoàn để còn $O(n)$.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

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ộ test20 testÝ tưởngtuần hoànCách 1O(m·d) – 30đCách 2O(m) – 90đCách 3O(n) – 100đTổng kếtkết quả

Bộ testBộ test có gì?

Bộ test trên CLUE do mình tự sinh theo đúng giới hạn và tỉ lệ điểm subtask của đề: 20 test (test 1, 2 là hai ví dụ của đề). Mỗi subtask có cả trường hợp $d < n$ lẫn $d \ge n$, $d$ rất nhỏ và $d$ gần bằng $m$.

Nhóm	Test	$n$ lớn nhất	$k$ lớn nhất	$m = n \times k$ lớn nhất	Test có $d \ge n$	Test có đoạn "bằng nhau"	Đáp án lớn nhất
Subtask 1	1–6	3.000	81	3.000	test 1–2, 4–6	test 5	2.881
Subtask 2	7–12	100.000	1.000	400.000	test 9–10, 12	test 11	380.001
Subtask 3	13–18	100.000	100.000	50.000.000	test 14, 16, 18	test 15–16	48.576.997
Subtask 4	19–20	100.000	100.000	10.000.000.000	test 19–20	không có	4.360.459.964

Cột "đoạn bằng nhau" là các test có đoạn mà $2 \times \min \times d$ đúng bằng tổng – đoạn này không đẹp (đề dùng dấu $>$). Có 4/20 test như vậy, viết nhầm thành $\ge$ là sai ngay.

Đã nộp thử trên bộ chấm chính thức

Lời giải cuối cùng (cách 3) mình đã nộp lên hệ thống chấm chính thức của Hội thi (tinhoctre.vn) và được 100/100 điểm (AC).

Kết quả chạy thật các cách bên dưới theo từng subtask:

Subtask	Điều kiện	Test	Cách 1 $O(m \cdot d)$	Cách 1 Python	Cách 2 $O(m)$	Cách 3 $O(n)$	Cách 3 Python
Subtask 1 (30%)	$n \times k \le 3 \cdot 10^3$	1–6	6/6	6/6	6/6	6/6	6/6
Subtask 2 (30%)	$n \times k \le 4 \cdot 10^5$	7–12	4/6	3/6	6/6	6/6	6/6
Subtask 3 (30%)	$n \times k \le 5 \cdot 10^7$	13–18	2/6	0/6	6/6	6/6	6/6
Subtask 4 (10%)	không ràng buộc thêm	19–20	0/2	0/2	0/2	2/2	2/2

Ý tưởngBỏ phép chia và nhìn ra tính tuần hoàn

1. Tránh số thực. Vì $d > 0$ nên $2 \times \min > \frac{\text{tổng}}{d} \iff 2 \times \min \times d > \text{tổng}$. So sánh hoàn toàn bằng số nguyên. Chú ý: tổng có thể tới $10^{10} \cdot 10^6 = 10^{16}$ và $2 \times \min \times d$ tới $2 \cdot 10^{16}$ – phải dùng long long.

2. Tuần hoàn. Phần tử thứ $i$ (đếm từ 0) của $A^k$ là $a_{i \bmod n}$. Vì vậy đoạn bắt đầu ở vị trí $s$ và đoạn bắt đầu ở $s + n$ giống hệt nhau (miễn là cả hai nằm trọn trong dãy). Kết quả "đẹp hay không" chỉ phụ thuộc vào số dư $r = s \bmod n$ – chỉ có $n$ trường hợp khác nhau!

Em nhập dãy rồi bấm Tiếp để xem từng đoạn được kiểm tra, các ô cùng màu khung là các vị trí bắt đầu có cùng số dư (kết quả giống nhau):

Dãy A = k = d =

Ví dụ nhanh:

Cách 1Duyệt mọi đoạn – O(m·d) (Subtask 1)

Dựng hẳn dãy $A^k$ vào mảng b, với mỗi vị trí bắt đầu chạy một vòng lặp tính min và tổng của đoạn.

C++▶ Chạy tay từng dòng codeCách 1: dựng dãy A^k, với mỗi đoạn tính min và tổng bằng vòng lặp.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Với $m \le 3000$ thì số phép tính tối đa khoảng $m \cdot d \le 9 \cdot 10^6$ – rất nhanh.

Không gian$O(m)$

Thời gian$O(m \cdot d)$

Kết quả chạy thật: Bản C++ đúng 12/20 test, sai test 19–20, quá thời gian test 9–10, 13–14, 16–17 (các test đúng chạy lâu nhất 0.626s). Qua trọn subtask 1, cộng thêm vài test lớn mà $d$ rất nhỏ hoặc $d$ gần bằng $m$ (khi đó $m \cdot d$ hoặc số đoạn $m - d + 1$ nhỏ). Các test $m$ cỡ $10^{10}$ thì ngay việc dựng mảng b đã không thể. Bản Python đúng 9/20 test, sai test 19–20, quá thời gian test 8–10, 13–18 (các test đúng chạy lâu nhất 0.232s).

Cách 2Cửa sổ trượt trên cả dãy – O(m) (Subtask 1, 2, 3)

Hai đoạn liên tiếp chỉ khác nhau đúng 1 phần tử ở đầu và 1 phần tử ở cuối, nên:

• Tổng: cộng phần tử mới vào, trừ phần tử vừa rời khỏi cửa sổ.
• Min: dùng hàng đợi 2 đầu (deque) đơn điệu – giữ các phần tử có giá trị tăng dần; phần tử mới vào thì "đá" mọi phần tử cuối hàng lớn hơn hoặc bằng nó (chúng không bao giờ còn là min nữa); phần tử ở đầu hàng ra khỏi cửa sổ thì bỏ. Min luôn là đầu hàng.

Không cần dựng $A^k$: phần tử thứ $i$ là a[i % n]. Để nhanh hơn, mình dùng hai biến đếm vòng p = i % n, q = (i - d) % n thay cho phép chia lấy dư.

C++▶ Chạy tay từng dòng codeCách 2: cửa sổ trượt trên cả dãy A^k – tổng cộng/trừ dần, min bằng deque đơn điệu.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Mỗi phần tử vào deque 1 lần và ra nhiều nhất 1 lần nên cả vòng lặp là $O(m)$.
• Deque lưu cả chỉ số (để biết khi nào phần tử rời cửa sổ) lẫn giá trị.

Không gian$O(n + d)$

Thời gian$O(m)$

Kết quả chạy thật: Bản C++ đúng 18/20 test, quá thời gian test 19–20 (các test đúng chạy lâu nhất 0.765s). Qua subtask 1, 2, 3 (90 điểm); $m = 5 \cdot 10^7$ chạy khoảng 0,5–0,8 giây (vẫn trong 1 giây). Subtask 4 có $m$ tới $10^{10}$ thì $O(m)$ cũng không kịp.

Cách 3Chỉ xét n vị trí bắt đầu – O(n) (full)

Theo ý tưởng tuần hoàn, ta chỉ cần biết với mỗi số dư $r = 0, 1, \dots, n - 1$: đoạn $d$ phần tử bắt đầu ở $r$ (trên dãy $A$ lặp vô hạn) có min mn[r] và tổng sm[r] bằng bao nhiêu. Nhân đôi mảng $a$ (nối $a$ với chính nó) để đi vòng tròn cho tiện, và dùng tổng tiền tố pre.

• Nếu $d \ge n$: đoạn chứa trọn ít nhất một chu kỳ nên min là min cả dãy $A$. Viết $d = q \cdot n + rem$: tổng $= q \cdot S + $ (tổng $rem$ phần tử vòng tròn bắt đầu từ $r$) $= q \cdot S + pre[r + rem] - pre[r]$, với $S$ là tổng dãy $A$.
• Nếu $d < n$: đoạn nằm trong mảng nhân đôi, đoạn bắt đầu ở $r$ là $a[r..r+d-1]$. Dùng lại cửa sổ trượt với deque trên mảng nhân đôi (chỉ $n + d - 1 < 2n$ phần tử).

Cuối cùng, các vị trí bắt đầu hợp lệ (đếm từ 0) là $s \in [0, last]$ với $last = m - d$. Số các $s$ trong đoạn này có $s \bmod n = r$ là $\left\lfloor \frac{last - r}{n} \right\rfloor$ $+ 1$ (nếu $r \le last$, ngược lại là 0). Cộng số này vào đáp án với mỗi $r$ đẹp.

C++▶ Chạy tay từng dòng codeCách 3: chỉ tính min và tổng cho n vị trí bắt đầu (theo số dư), rồi nhân với số lần lặp.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. if(dq.front() < st) dq.pop_front(); – đầu cửa sổ mỗi bước chỉ dịch 1 ô nên bỏ nhiều nhất 1 phần tử ở đầu hàng.
2. Điều kiện r <= last quan trọng khi $d$ gần bằng $m$: ví dụ $d = m$ thì chỉ có đúng 1 vị trí bắt đầu ($r = 0$).
3. 2 * mn[r] * d: $d$ là long long nên cả biểu thức tính bằng long long, không tràn.

Không gian$O(n)$

Thời gian$O(n)$

Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.018s. Full điểm. Bản Python đúng 20/20 test, chạy lâu nhất 0.147s – chỉ $O(n)$ nên Python cũng qua hết.

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)	Điểm theo subtask
1. Duyệt mọi đoạn, tính min và tổng bằng vòng lặp	C++	12/20	0.626s	30%
	Python	9/20	0.232s	30%
2. Cửa sổ trượt (deque) trên cả dãy A^k	C++	18/20	0.765s	90%
3. Tuần hoàn: chỉ xét n vị trí bắt đầu	C++	20/20	0.018s	100%
	Python	20/20	0.147s	100%

Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình (giới hạn 1 giây, các test quá giờ bị dừng ở khoảng 4 giây). Ba điều rút ra: (1) đổi phép so sánh có phân số thành phép nhân để làm việc với số nguyên, nhớ dùng long long; (2) cửa sổ trượt + deque đơn điệu cho min mọi đoạn độ dài cố định trong $O(m)$; (3) dữ liệu được "lặp lại" thì hãy tìm tính tuần hoàn – chỉ cần giải trên một chu kỳ rồi nhân số lần lặp.

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 😇