Magsum (Tin học trẻ toàn quốc 2024 – Vòng sơ khảo – Bảng C1, C2)
Đề bài
Cho dãy $A$ gồm $N$ số nguyên dương $a_1, a_2, \dots, a_N$. Em hãy đếm số cặp chỉ số $(L, R)$ với $1 \le L \le R \le N$ sao cho phần tử lớn nhất của đoạn $a_L, a_{L+1}, \dots, a_R$ lớn hơn một nửa tổng của đoạn đó:
$$\max(a_L, a_{L+1}, \dots, a_R) > \frac{a_L + a_{L+1} + \dots + a_R}{2}.$$
Dữ liệu vào:
- Dòng 1: số nguyên dương $N$ ($N \le 3 \cdot 10^5$);
- Dòng 2: $N$ số nguyên dương $a_1, a_2, \dots, a_N$ ($a_i \le 10^9$).
Kết quả: một số nguyên là số cặp $(L, R)$ thỏa mãn.
Subtask:
- Subtask 1 (50%): $N \le 10^3$;
- Subtask 2 (30%): dãy không giảm ($a_i \le a_{i+1}$ với mọi $i$);
- Subtask 3 (20%): 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.
3
2 2 44Giải thích: các cặp thỏa mãn là $(1, 1)$, $(2, 2)$, $(3, 3)$ và $(2, 3)$. Ví dụ đoạn $(2, 3)$ gồm $2, 4$: $\max = 4 > \frac{2 + 4}{2} = 3$. Còn đoạn $(1, 2)$ gồm $2, 2$: $\max = 2$ không lớn hơn $\frac{4}{2} = 2$ (bất đẳng thức chặt!). Đoạn $(1, 3)$: $4 > 4$ cũng sai.
Lời mở đầu
Đề ngắn gọn, vét cạn $O(N^2)$ ăn ngay 50 điểm. Muốn full thì cần hai kỹ thuật quen thuộc của dạng "đếm đoạn theo phần tử lớn nhất": ngăn xếp đơn điệu để biết mỗi phần tử làm max trên vùng nào, và mẹo "duyệt bên ngắn hơn" (small-to-large) để tổng số bước chỉ còn $O(N \log N)$. Mình đi từng bước: $O(N^2)$ → thêm subtask dãy không giảm → $O(N \log^2 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ệ subtask của đề: 21 test (test 1 là ví dụ của đề).
| Nhóm | Test | $N$ lớn nhất | $a_i$ lớn nhất | Test dãy không giảm | Test có ≤ 5 giá trị khác nhau | Tổng dãy lớn nhất | Đáp án lớn nhất |
|---|---|---|---|---|---|---|---|
| Subtask 1 | 1–10 | 1.000 | 1.000.000.000 | test 1–2, 4 | test 1–2, 4, 7–8, 10 | 999.000.000.001 | 131.241 |
| Subtask 2 | 11–16 | 300.000 | 1.000.000.000 | test 11–16 | test 12 | 300.000.000.000.000 | 599.963 |
| Subtask 3 | 17–21 | 300.000 | 1.000.000.000 | không có | test 21 | 149.923.963.836.630 | 17.600.529.978 |
- Có các test "bẫy": toàn bộ phần tử bằng nhau (test 4, 12 – đáp án đúng bằng $N$ vì chỉ các đoạn một phần tử thỏa mãn), dãy là các lũy thừa của 2, dãy chỉ có vài giá trị khác nhau.
- Tổng một đoạn có thể tới $3 \cdot 10^5 \cdot 10^9 = 3 \cdot 10^{14}$, và đáp án lớn nhất là $17.600.529.978$ (test 21) – vượt xa giới hạn kiểu
int, phải dùnglong longcho cả tổng lẫn đáp án.
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(N^2)$ C++ | Cách 1 Python | Cách 2 sub 1 + 2 | Cách 3 C++ | Cách 3 Python |
|---|---|---|---|---|---|---|---|
| Subtask 1 (50%) | $N \le 10^3$ | 1–10 | 10/10 | 10/10 | 10/10 | 10/10 | 10/10 |
| Subtask 2 (30%) | dãy không giảm | 11–16 | 0/6 | 0/6 | 6/6 | 6/6 | 6/6 |
| Subtask 3 (20%) | không ràng buộc thêm | 17–21 | 0/5 | 0/5 | 0/5 | 5/5 | 5/5 |
Ý tưởngViết lại điều kiện cho dễ làm
Nhân hai vế với 2, điều kiện trở thành phép so sánh số nguyên (không cần số thực):
$$2 \cdot \max(a_L..a_R) > a_L + \dots + a_R \iff \text{tổng các phần tử còn lại} < \max.$$
Tức là: phần tử lớn nhất phải "áp đảo" – lớn hơn tổng tất cả những phần tử khác trong đoạn. Với mảng tiền tố $pre[i] = a_1 + \dots + a_i$, tổng đoạn là $pre[R] - pre[L-1]$.
Hai nhận xét quan trọng:
- Mọi $a_i > 0$ nên $pre$ tăng ngặt – cố định $L$ và max thì càng kéo $R$ ra xa, tổng càng lớn, điều kiện càng khó thỏa. Đây là chỗ để tìm kiếm nhị phân.
- Nếu cố định phần tử làm max là $a_p$, thì điều kiện chỉ còn là $pre[R] - pre[L-1] < 2a_p$ – một bất đẳng thức giữa hai đầu mút.
Cách 1Vét cạn mọi đoạn – O(N²) (Subtask 1)
Cố định $L$, mở rộng $R$ dần từ $L$ tới $N$, cập nhật tổng và max trong $O(1)$ mỗi bước rồi kiểm tra điều kiện.
Kết quả chạy thật: Bản C++ đúng 10/21 test, quá thời gian test 11–21 (các test đúng chạy lâu nhất 0.004s) → 50 điểm. Bản Python đúng 10/21 test, quá thời gian test 11–21 (các test đúng chạy lâu nhất 0.200s) – $N = 1000$ chỉ có $5 \cdot 10^5$ đoạn nên Python vẫn kịp. Với $N = 3 \cdot 10^5$ thì có $4{,}5 \cdot 10^{10}$ đoạn – không thể.
Cách 2Thêm subtask dãy không giảm – tìm kiếm nhị phân
Khi dãy không giảm, phần tử lớn nhất của đoạn $[L, R]$ chính là $a_R$ (phần tử cuối). Điều kiện trở thành
$$pre[R] - pre[L-1] < 2a_R \iff pre[L-1] > pre[R] - 2a_R.$$
Với mỗi $R$, đặt $t = L - 1 \in [0, R-1]$: cần đếm số $t$ có $pre[t] > pre[R] - 2a_R$. Vì $pre$ tăng ngặt nên các $t$ thỏa mãn là một đoạn cuối $[t_0, R-1]$, tìm $t_0$ bằng upper_bound. Chương trình kiểm tra dãy có không giảm không: có thì dùng cách này, không thì quay về vét cạn.
Kết quả chạy thật: Bản C++ đúng 16/21 test, quá thời gian test 17–21 (các test đúng chạy lâu nhất 0.046s) → 80 điểm (subtask 1 và 2). Subtask 3 vẫn rơi vào nhánh vét cạn nên quá thời gian.
Cách 3Mỗi phần tử làm max một vùng – duyệt bên ngắn (full)
Bước 1 – mỗi đoạn gán cho đúng một "max". Với mỗi vị trí $p$, xét các đoạn mà $a_p$ là max và $p$ là vị trí max đứng trái nhất (để đoạn có nhiều max bằng nhau chỉ bị đếm một lần). Gọi
- $lp[p]$ = vị trí gần nhất bên trái có $a \ge a_p$ (không có thì $0$);
- $rp[p]$ = vị trí gần nhất bên phải có $a > a_p$ (không có thì $N + 1$).
Khi đó đoạn $[L, R]$ nhận $p$ làm max đứng trái nhất khi và chỉ khi $lp[p] < L$ $\le p$ $\le R < rp[p]$. Hai mảng này tìm bằng ngăn xếp đơn điệu trong $O(N)$ (chú ý dấu: bên trái dùng $\ge$, bên phải dùng $>$).
Bước 2 – đếm trong vùng của $p$. Cần đếm cặp $(L, R)$ trong vùng có $pre[R] - pre[L-1] < 2a_p$. Duyệt từng $L$ rồi tìm nhị phân $R$ (hoặc ngược lại). Nhưng duyệt bên nào? Bên ngắn hơn!
Vì sao duyệt bên ngắn hơn lại nhanh? Vùng $(lp[p], rp[p])$ của các phần tử chính là các nút của cây Cartesian (cây max): $p$ là gốc, vùng bên trái và bên phải là hai cây con. Mỗi lần ta trả chi phí $\min(\text{trái}, \text{phải})$ – đúng như khi gộp tập "nhỏ vào lớn": một chỉ số nằm ở bên ngắn thì vùng chứa nó lớn gấp đôi trở lên, nên mỗi chỉ số bị duyệt không quá $\log_2 N$ lần. Tổng số lần duyệt $\le N \log_2 N$, mỗi lần một tìm kiếm nhị phân → $O(N \log^2 N)$.
Em nhập dãy (tối đa 12 số) rồi bấm Tiếp để xem từng vùng: ô viền cam là $p$, vùng sáng là $(lp, rp)$, ô vàng là đầu mút đang duyệt ở bên ngắn, ô xanh là các đầu mút bên kia ghép được với nó:
- Dòng
while (... a[st.back()] < a[i])(bên trái) giữ lại phần tử bằng $a_i$ nên $lp$ là vị trí gần nhất có $a \ge a_i$; còn bên phải dùng<=nên $rp$ là vị trí gần nhất có $a > a_i$. Đổi lẫn hai dấu này là đếm trùng/đếm thiếu các đoạn có nhiều max bằng nhau (test 4, 12 bắt lỗi này). - Bên trái ngắn: với mỗi $L$, cần $pre[R] < pre[L-1]$ $+ 2a_p$ với $R \in [p, rp)$ →
lower_boundcho chỉ số $r$ đầu tiên vi phạm, cộng $r - p$. - Bên phải ngắn: với mỗi $R$, cần $pre[t] > pre[R] - 2a_p$ với $t = L - 1 \in [lp, p)$ →
upper_bound, cộng $p - t$. - Đoạn một phần tử $[p, p]$ luôn thỏa (tổng $a_p < 2a_p$), nên mỗi $p$ đóng góp ít nhất 1 – đáp án luôn $\ge N$.
Kết quả chạy thật: Bản C++ đúng 21/21 test, chạy lâu nhất 0.076s. Full điểm. Bản Python đúng 21/21 test, chạy lâu nhất 0.751s – bản Python cũng qua được nhờ bisect chạy bằng C và tổng số lần duyệt bên ngắn khá nhỏ trên thực 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. Vét cạn $O(N^2)$ | C++ | 10/21 | 0.004s | 50% |
| Python | 10/21 | 0.200s | 50% | |
| 2. Vét cạn + tìm kiếm nhị phân cho dãy không giảm | C++ | 16/21 | 0.046s | 80% |
| 3. Ngăn xếp đơn điệu + duyệt bên ngắn $O(N \log^2 N)$ | C++ | 21/21 | 0.076s | 100% |
| Python | 21/21 | 0.751s | 100% |
Nhận xét
Đăng nhận xét