Cặp số hoàn hảo
Đề bài
Cặp số hoàn hảo – capso.*
Hai số nguyên được gọi là một “Cặp số hoàn hảo” nếu như tổng của chúng bằng giá trị $s$ cho trước.
Hai bạn học sinh lúc ngồi nhàn rỗi nghĩ ra trò chơi sau đây để tăng khả năng tư duy toán học: cho dãy số $a_1, a_2, \ldots, a_n$, các bạn chọn trong dãy số gồm $n$ số nguyên sao cho giá trị của hai số đã chọn $a_i, a_j$ với $i < j$ thỏa mãn $a_i + a_j = s$ là cặp số hoàn hảo.
Cho một dãy số nguyên $a_1, a_2, \ldots, a_n$ và số nguyên $s$.
Yêu cầu: Em hãy lập trình đếm xem trong dãy số đã cho có bao nhiêu cặp số hoàn hảo.
Dữ liệu vào:
- Dòng thứ nhất ghi số nguyên dương $n$ $(n \le 10^6)$ và số nguyên $s$ $(|s| \le 10^9)$.
- Các dòng tiếp theo lần lượt ghi các số $a_1, a_2, \ldots, a_n$ $(|a_i| \le 10^9)$.
Kết quả ra: Ghi ra một số nguyên duy nhất là số lượng cặp số hoàn hảo.
Ràng buộc:
- Có 60% điểm ứng với $1 \le n \le 10^3$;
- Có 40% điểm ứng với $1 \le n \le 10^6$.
Lưu ý trên CLUE OJ: dữ liệu nhập từ bàn phím và in ra màn hình. Tuy đề gốc cho giới hạn thời gian 1 giây, nhưng vì máy chấm VNOJ rất mạnh còn máy chấm thực tế của ban giám khảo có thể không mạnh bằng, nên trên web VNOJ thầy chỉ cho 0.3 giây. Bài trong kỳ thi chỉ được nộp 1 lần duy nhất, vì vậy hãy kiểm tra thật kỹ rồi mới nộp.
10 7
5 2 5 3 4 3 1 6 4 07Lời mở đầu
Đây là bài "đếm cặp có tổng bằng $s$" kinh điển – gần như đề thi học sinh giỏi nào cũng có một bài na ná như vậy. Với $n \le 10^3$ thì hai vòng for là xong, nhưng với $n = 10^6$ thì số cặp lên tới khoảng $5 \cdot 10^{11}$, không thể thử hết. Mình sẽ đi từ cách vét cạn, sang cách dùng map để "nhớ" các số đã gặp, rồi tới cách sắp xếp + hai con trỏ chạy nhanh nhất. Các bạn chú ý cả chuyện kiểu dữ liệu nữa nhé: đáp án có thể vượt quá phạm vi int.
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ì?
Bộ test có 100 test. Mình thống kê theo từng nhóm:
| Test | n | Giá trị $a_i$ | s | Đáp án lớn nhất | Số test đáp án 0 |
|---|---|---|---|---|---|
| 1–10 | 9 / 10 / 21 / 24 / 28 / 29 / 30 | -59 … 60 | -46 … 37 | 11 | 1 |
| 11–60 | 1.000 | -32.767 … 32.767 | -31.479 … 31.964 | 20 | 2 |
| 61–70 | 10.000 | -32.767 … 32.767 | -31.690 … 19.651 | 769 | 0 |
| 71–80 | 100.000 | -32.767 … 32.767 | -30.841 … 28.117 | 72.202 | 0 |
| 81–100 | 1.000.000 | -32.767 … 32.767 | -30.592 … 30.037 | 7.494.956 | 0 |
Một vài nhận xét quan trọng:
- Giá trị $a_i$ trong test thật chỉ nằm trong khoảng $[-32767, 32767]$ (nhỏ hơn nhiều so với $10^9$ của đề), nhưng ta vẫn phải code theo đúng giới hạn của đề: $a_i + a_j$ có thể tới $2 \cdot 10^9$, vượt
int, nên mình dùnglong long. - Đáp án lớn nhất trong bộ test khoảng 7,5 triệu, nhưng về lý thuyết nếu cả $10^6$ số đều bằng nhau và $s$ bằng 2 lần số đó thì đáp án là $\frac{10^6 \cdot (10^6 - 1)}{2} \approx 5 \cdot 10^{11}$ – bắt buộc biến đếm phải là
long long. - Ở các test $n = 10^6$, dãy có rất nhiều số trùng nhau (chỉ có 65535 giá trị khác nhau), nên cách xử lý số trùng phải thật chuẩn.
Bảng subtask (đối chiếu với test thật) và cách giải nào ăn được subtask nào:
| Subtask | Điều kiện | Test | Cách 1 (vét cạn) | Cách 2 (map) | Cách 3 (sắp xếp) |
|---|---|---|---|---|---|
| 1 (60%) | $n \le 10^3$ | 1–60 | ✔ | ✔ | ✔ |
| 2 (40%) | $n \le 10^6$ | 61–100 | chỉ test 61–70 | chậm ở $n = 10^6$ | ✔ |
Ý tưởngĐứng ở $a_j$, hỏi "phía trước có bao nhiêu số $s - a_j$?"
Cố định số đứng sau $a_j$ của cặp. Số đứng trước $a_i$ phải bằng đúng $s - a_j$. Vậy số cặp có số sau là $a_j$ chính là số lần giá trị $s - a_j$ đã xuất hiện ở các vị trí trước $j$.
cnt[v] = số lần giá trị $v$ đã gặp. Tại mỗi $j$: cộng cnt[s - a[j]] vào đáp án, rồi mới tăng cnt[a[j]].Thứ tự "cộng trước, tăng sau" rất quan trọng: nó đảm bảo $i < j$ và một số không tự ghép với chính nó (ví dụ $s = 10$, $a_j = 5$ thì không được tính cặp $(a_j, a_j)$). Vì $|a_i|$ tới $10^9$ nên không dùng mảng đếm được, phải dùng map.
Em nhập $s$ và dãy số rồi bấm Tiếp để xem từng bước (ô vàng là số đang xét, ô xanh là các số phía trước ghép được với nó):
Cách 1Vét cạn mọi cặp – Subtask 1
Cách tự nhiên nhất: thử mọi cặp $i < j$, cặp nào có tổng bằng $s$ thì đếm. Có $\frac{n(n-1)}{2}$ cặp.
- Vòng
jbắt đầu từi + 1nên mỗi cặp chỉ được xét đúng 1 lần và không có cặp $(i, i)$. a[]vàdemđều làlong longđể không bị tràn số.
Kết quả chạy thật: bản C++ đúng 70/100 test (đúng test 1–70; test 71–100 vượt 1 giây), test đúng chạy lâu nhất 0.07s; bản Python đúng 60/80 test (mình chỉ chạy test 1–80 vì vét cạn Python với $n = 10^6$ chạy cả ngày không xong). Đúng như dự đoán: ăn trọn Subtask 1 và cả các test $n = 10^4$, còn từ $n = 10^5$ trở đi thì số cặp quá lớn.
Cách 2Dùng map nhớ các số đã gặp
Cài đặt đúng ý tưởng ở trên: mỗi phần tử chỉ cần 1 lần tìm và 1 lần thêm vào map. Mình còn không cần lưu cả mảng $a$: đọc số nào xử lý luôn số đó.
cnt.find(s - x)trả về vị trí của khoás - xtrong map, hoặccnt.end()nếu không có. Dùngfindthay chocnt[s - x]để không vô tình tạo thêm khoá rỗng (map sẽ phình to và chậm đi).cnt[x]++đặt sau lệnh cộng đáp án – đúng thứ tự "cộng trước, tăng sau".- Bản Python dùng
dict, tương tựunordered_mapcủa C++ (bảng băm).
Kết quả chạy thật: bản C++ đúng 86/100 test (đúng test 1–80, 85, 87–88, 91–92, 100; test 81–84, 86, 89–90, 93–99 vượt 1 giây), test đúng chạy lâu nhất 0.94s; bản Python đúng 99/100 test. Kết quả luôn đúng, nhưng các test $n = 10^6$ chạy sát hoặc vượt 1 giây.
map mất $O(\log n)$ và phải nhảy qua nhiều nút cây nằm rải rác trong bộ nhớ. Với $10^6$ số là khoảng $2 \cdot 10^6$ thao tác cây – vẫn là $O(n \log n)$ nhưng "hằng số" lớn. Đề lại còn ép 0.3 giây trên VNOJ, nên ta cần một cách gọn nhẹ hơn.Cách 3Sắp xếp + hai con trỏ – Full điểm
Sắp xếp tăng dần, đặt con trỏ l ở đầu, r ở cuối:
- Nếu
a[l] + a[r] < s: tổng nhỏ quá, màa[l]ghép với số lớn nhất còn chưa đủ, nêna[l]không ghép được với ai →l++. - Nếu
a[l] + a[r] > s: tương tự,a[r]bị loại →r--. - Nếu bằng $s$: có thể có nhiều số bằng
a[l]và nhiều số bằnga[r]liền nhau. Đếm khối bằnga[l]($c_1$ số) và khối bằnga[r]($c_2$ số), cộng $c_1 \cdot c_2$ cặp rồi bỏ cả 2 khối. - Trường hợp đặc biệt
a[l] == a[r]: cả đoạn từltớirtoàn số bằng nhau (bằng $s/2$), chọn 2 trong $k = r - l + 1$ số được $\frac{k(k-1)}{2}$ cặp, rồi dừng.
- Trong nhánh
elsecuối ta cóa[l] < a[r], nên các vòngwhilegom khối không bao giờ chạy lố sang khối bên kia. - Bản Python mình dùng
Counterđếm số lần xuất hiện của từng giá trị $x$, rồi ghép $x$ với $y = s - x$ (chỉ tính khi $x < y$ để không đếm 2 lần, còn $x = y$ thì cộng $\binom{c}{2}$). Cùng tư tưởng "gom các số bằng nhau" như hai con trỏ.
Kết quả chạy thật: bản C++ đúng 100/100 test, chạy lâu nhất 0.19s; bản Python đúng 100/100 test. Full điểm với thời gian rất thoải mái.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất | Ghi chú |
|---|---|---|---|---|
| 1. Vét cạn $O(n^2)$ | C++ | 70/100 | > 1s | Đúng test 1–70; test 71–100 quá thời gian |
| Python | 60/80 | > 1s | Chỉ chạy thử test 1–80: đúng 1–60, test 61–80 quá thời gian | |
2. Đếm bằng map | C++ | 86/100 | > 1s | Đúng hết nhưng 14 test $n = 10^6$ chạy quá 1 giây |
| Python | 99/100 | > 1s | Test 88 quá 1 giây | |
| 3. Sắp xếp + 2 con trỏ | C++ | 100/100 | 0.19s | Full điểm |
| Python | 100/100 | 0.60s | Đếm theo giá trị bằng Counter |
unordered_map (có reserve trước) thay cho map ở Cách 2 thì cũng nhanh gần bằng Cách 3. Đừng quên: biến đếm phải là long long!
Nhận xét
Đăng nhận xét