Số trung bình (Ver 2)
Đề bài
Số trung bình
Cho dãy số nguyên không âm $a_1, a_2, \ldots, a_n$, hãy đếm số bộ ba chỉ số $i < k < j$ sao cho $a_i + a_j = 2 \times a_k$.
Dữ liệu: dòng đầu tiên ghi số nguyên dương $T$ $(T \le 10)$ là số lượng bộ dữ liệu. Tiếp đến là $T$ nhóm dòng, mỗi nhóm tương ứng với một bộ dữ liệu có cấu trúc như sau:
- Dòng đầu chứa số nguyên $n$;
- Dòng thứ hai gồm $n$ số $a_1, a_2, \ldots, a_n$ $(|a_i| \le 10^9)$.
Kết quả: gồm $T$ dòng, mỗi dòng chứa một số là kết quả tương ứng với bộ dữ liệu vào.
Ràng buộc:
- 20% số test đầu tiên có $n \le 20$;
- 30% số test tiếp theo có $n \le 100$;
- 20% số test tiếp theo có $n \le 1000$;
- 30% số test còn lại có $n \le 1700$.
2
3
1 2 5
3
1 1 10
1Giải thích ví dụ: dãy 1 2 5 chỉ có một bộ $(i, k, j) = (1, 2, 3)$ nhưng $1 + 5 = 6 \ne 2 \cdot 2$ → 0. Dãy 1 1 1 có bộ $(1, 2, 3)$ thoả $1 + 1 = 2 \cdot 1$ → 1.
Lời mở đầu
$a_i + a_j = 2a_k$ nghĩa là $a_k$ là trung bình cộng của $a_i$ và $a_j$ (ba số lập thành cấp số cộng theo đúng thứ tự vị trí). Thử mọi bộ ba thì $O(n^3)$ – quá chậm với $n = 1700$. Mẹo quen thuộc của chủ đề Map/Set: cố định phần tử ở giữa, rồi dùng map đếm xem bên trái có bao nhiêu số "khớp". Còn một cách đẹp không dùng map: hai con trỏ trên hai nửa đã sắp xếp.
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 chính thức có gì?
| Test | T | n lớn nhất | Giá trị nhỏ nhất | Giá trị lớn nhất | Đáp án lớn nhất |
|---|---|---|---|---|---|
| 1 – 20 | 2, 5 | 20 | -30 | 30 | 17 |
| 21 – 50 | 10 | 100 | -999.634.252 | 999.726.341 | 95 |
| 51 – 70 | 10 | 1.000 | -999.869.040 | 999.981.440 | 31.903 |
| 71 – 100 | 10 | 1.700 | -999.971.606 | 999.972.140 | 160.475 |
- Bốn nhóm test khớp đúng 4 mức ràng buộc của đề (20 / 30 / 20 / 30 test). Từ test 21 trở đi mỗi file đều có đủ $T = 10$ bộ, nên thời gian là của 10 bộ cộng lại.
- Giá trị trải từ khoảng $-10^9$ tới $10^9$, nên $2a_k$ (tới $2 \cdot 10^9$) và $2a_k - a_j$ (tới $3 \cdot 10^9$) tràn kiểu
int→ dùnglong long. - Dãy có nhiều giá trị lặp lại (ví dụ $n = 1700$ nhưng chỉ khoảng 1370 giá trị khác nhau) → khi đếm phải tính số lần xuất hiện, không chỉ "có hay không".
| Subtask | Điều kiện | Các test | Cách 1 3 vòng lặp | Cách 2 map | Cách 3 hai con trỏ |
|---|---|---|---|---|---|
| 1 (20%) | $n \le 20$ | 1 – 20 | 20/20 | 20/20 | 20/20 |
| 2 (30%) | $n \le 100$ | 21 – 50 | 30/30 | 30/30 | 30/30 |
| 3 (20%) | $n \le 1000$ | 51 – 70 | 1/20 | 20/20 | 20/20 |
| 4 (30%) | $n \le 1700$ | 71 – 100 | 0/30 | 30/30 | 30/30 |
Ý tưởngCố định số ở giữa, hỏi map bên trái
Viết lại điều kiện: $a_i = 2a_k - a_j$. Nếu ta cố định $k$ và cố định $j$ (với $j > k$) thì chỉ còn câu hỏi: bên trái $k$ có bao nhiêu chỉ số $i$ mà $a_i = 2a_k - a_j$?
map trai đếm số lần xuất hiện của các giá trị $a_0, \ldots, a_{k-1}$. Với mỗi $j > k$: cộng trai[2a[k] - a[j]] vào đáp án. Xong $k$ thì trai[a[k]]++ rồi sang $k$ tiếp theo.Mỗi cặp $(k, j)$ tốn một lần tra map $O(\log n)$ → tổng $O(n^2 \log n)$, với $n = 1700$ là khoảng $1{,}4 \cdot 10^6$ lần tra mỗi bộ – rất nhanh. Dùng map vì giá trị lớn tới $10^9$ (và âm), không làm mảng đếm được.
Em nhập dãy rồi bấm Tiếp để xem với từng $k$ (ô viền cam), từng $j$, máy tra map bên trái thế nào:
Cách 1Thử mọi bộ ba – O(n³)
Ba vòng lặp lồng nhau theo đúng thứ tự $i < k < j$, đếm các bộ thoả điều kiện.
- Mảng khai báo
long longđể2 * a[k]vàa[i] + a[j]không bị tràn số. - Số bộ ba là $\binom{n}{3} \approx \frac{n^3}{6}$: với $n = 100$ chỉ khoảng $1{,}6 \cdot 10^5$, nhưng $n = 1000$ đã là $1{,}7 \cdot 10^8$ mỗi bộ, nhân 10 bộ thì quá 1 giây.
Kết quả chạy thật: bản C++ đúng 51/100 test (quá 1 giây ở các test 51–54, 56–100), test đúng chạy lâu nhất 0.999s; bản Python đúng 50/100 test (quá thời gian ở các test 51–100), lâu nhất 0.29s. Tức là ăn chắc 50% điểm (subtask 1, 2); ở subtask 3 chỉ "hên" được một test.
Cách 2Cố định k + map đếm bên trái – O(n² log n)
Cài đặt đúng ý tưởng ở trên.
- Dùng
trai.find(...)thay vìtrai[...]để tra: toán tử[]sẽ tự tạo phần tử mới (giá trị 0) nếu chưa có, làm map phình to và chậm đi. trai[a[k]]++đặt sau vòngfor j: lúc xét $k$ thì map chỉ chứa các chỉ số $i < k$, đúng yêu cầu $i < k$.- Mỗi bộ dữ liệu khai báo lại
map(nằm trongwhile(t--)) nên không bị dính dữ liệu của bộ trước.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.508s; bản Python đúng 70/100 test (quá thời gian ở các test 71–100), lâu nhất 0.65s.
Cách 3Hai con trỏ trên hai nửa đã sắp xếp – O(n²)
Với $k$ cố định, bài toán thành: đếm số cặp $(x, y)$ với $x$ thuộc nửa trái $L = \{a_0..a_{k-1}\}$, $y$ thuộc nửa phải $R = \{a_{k+1}..a_{n-1}\}$ và $x + y = 2a_k$. Đây là bài "đếm cặp có tổng bằng $S$" quen thuộc: nếu $L$ và $R$ đều đã sắp xếp thì dùng hai con trỏ – $i$ chạy từ đầu $L$ (nhỏ → lớn), $j$ chạy từ cuối $R$ (lớn → nhỏ):
- $L_i + R_j < S$: cần tổng lớn hơn →
i++. - $L_i + R_j > S$: cần tổng nhỏ hơn →
j--. - Bằng nhau: đếm cụm giá trị $x$ liên tiếp trong $L$ ($c_i$ phần tử) và cụm $y$ trong $R$ ($c_j$ phần tử) → cộng $c_i \cdot c_j$ cặp.
Khi $k$ tăng 1: $a_{k-1}$ chuyển sang nửa trái (chèn vào đúng chỗ để $L$ vẫn sắp xếp), $a_k$ rời nửa phải (xoá khỏi $R$). Chèn/xoá trong vector tốn $O(n)$ nhưng là thao tác dời bộ nhớ liên tục nên rất nhanh.
upper_boundtìm chỗ chèn giữ $L$ tăng dần;lower_boundtìm đúng một bản của $a_k$ trong $R$ để xoá.- Phần đếm cụm trùng là chỗ hay sai nhất: phải đếm cả hai cụm rồi nhân, không được chỉ
i++; j--và cộng 1.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.085s. Nhanh hơn Cách 2 khoảng 6 lần vì không phải tra map.
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. Ba vòng lặp | C++ | 51/100 | 0.999s | Quá thời gian ở test 51–54, 56–100 |
| Python | 50/100 | 0.295s | Quá thời gian ở test 51–100 | |
| 2. Cố định k + map | C++ | 100/100 | 0.508s | Full điểm |
| Python (dict) | 70/100 | 0.651s | Quá thời gian ở test 71–100 | |
| 3. Hai con trỏ trên 2 nửa đã sắp xếp | C++ | 100/100 | 0.085s | Full điểm |
Nhận xét
Đăng nhận xét