Dãy số (Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng B)
Đề bài
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.
2 3 3
1 323 10 3
1 5 100Giả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à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 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.
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):
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.
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.
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ư.
- 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ị.
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.
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.- Điều kiện
r <= lastquan 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$). 2 * mn[r] * d: $d$ làlong longnên cả biểu thức tính bằnglong long, không trà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% |
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.
Nhận xét
Đăng nhận xét