Bắt tay ở kỳ thi
Đề bài
Trường của Tèo có tổng cộng 30 lớp, mỗi lớp cử $N$ bạn đi dự một kỳ thi lập trình. Trước giờ thi, để chúc nhau may mắn, mỗi bạn bắt tay đúng một lần với mỗi bạn khác (dù cùng lớp hay khác lớp).
Hỏi có tất cả bao nhiêu cái bắt tay?
Dữ liệu vào: Một dòng chứa số nguyên dương $N$.
Kết quả: In ra tổng số cái bắt tay.
Giới hạn:
- $1 \le N \le 10^6$
Subtask:
- Subtask 1 (40% số điểm): $N \le 35$.
- Subtask 2 (60% số điểm): không có ràng buộc gì thêm.
Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.
143521770Giải thích: Ví dụ 1: có $30 \cdot 1 = 30$ bạn, mỗi cặp hai bạn bắt tay đúng một lần nên số cái bắt tay là $\dfrac{30 \cdot 29}{2} = 435$.
Nguồn: phỏng theo bài "BẮT TAY" – vinhdinhcoder.net.
Lời mở đầu
Đây là bài nhập môn rất quen thuộc của phần tổ hợp: đếm số cặp. Code đúng chỉ có 1 dòng công thức, nhưng bài này có hai "cái bẫy" kinh điển mà năm nào mình cũng thấy các em sập: vòng lặp quá chậm và tràn số kiểu int. Mình sẽ đi lần lượt từ cách "đếm tay" bằng 2 vòng lặp, rút xuống 1 vòng lặp, rồi tới công thức $O(1)$ – và chạy thật cả 3 cách trên bộ test để các em thấy mỗi cách được bao nhiêu điểm.
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ó 20 test, mỗi test chỉ là một số $N$. Mình đặt $m = 30N$ là tổng số bạn đi thi. Mình đã kiểm tra: test 1–8 đúng là có $N \le 35$ (subtask 1), test 9–20 là subtask 2.
| Nhóm | Test | $N$ | $m = 30N$ lớn nhất | Đáp án lớn nhất | Số test $m(m-1) > 2^{31}-1$ |
|---|---|---|---|---|---|
| Subtask 1 | 1–8 | 1 … 35 | 1.050 | 550.725 | 0 |
| Subtask 2 | 9–20 | 36 … 1.000.000 | 30.000.000 | 449.999.985.000.000 | 8 |
- Ở subtask 2, $N$ lớn nhất là $10^6$ nên có tới $m = 3 \cdot 10^7$ bạn, đáp án lên tới 449.999.985.000.000 – lớn hơn rất nhiều so với giới hạn của kiểu
int($2^{31} - 1 = 2\,147\,483\,647$). - Subtask 2 vẫn có vài test $N$ nhỏ (test 12, 16, 18, 19 có $N \le 1000$), nên một cách "chưa tối ưu" vẫn có thể ăn thêm vài test lẻ ở subtask 2.
- Có 8 test (test 9–11, 13–15, 17, 20) mà tích $m(m-1)$ vượt quá $2^{31} - 1$, tức là $N \ge 1545$ – đây là các test "bắt" lỗi tràn số.
Kết quả chạy thật của các cách bên dưới theo từng subtask:
| Subtask | Điều kiện | Test | Cách 1 2 vòng lặp | Cách 2 1 vòng lặp | Cách 3 công thức, int | Cách 3long long |
|---|---|---|---|---|---|---|
| Subtask 1 (40%) | $N \le 35$ | 1–8 | 8/8 | 8/8 | 8/8 | 8/8 |
| Subtask 2 (60%) | $N \le 10^6$ | 9–20 | 4/12 | 12/12 | 4/12 | 12/12 |
(Kết quả bản C++; bản Python xem ở từng cách và bảng tổng kết.)
Ý tưởngMỗi cái bắt tay là một cặp 2 bạn
Có $m = 30N$ bạn. Mỗi cái bắt tay ứng với đúng một cặp hai bạn khác nhau (không quan tâm thứ tự: "An bắt tay Bình" cũng chính là "Bình bắt tay An"). Chuyện cùng lớp hay khác lớp không ảnh hưởng gì – 30 lớp chỉ để cho biết tổng số bạn là $30N$.
Một cách đếm rất trực quan: cho các bạn lần lượt bước vào phòng. Bạn thứ $i$ bước vào sẽ bắt tay với $i - 1$ bạn đã có mặt từ trước. Vậy tổng số cái bắt tay là
$$0 + 1 + 2 + \dots + (m - 1) = \dfrac{m(m-1)}{2} = C_m^2.$$
Em nhập số lớp và số bạn mỗi lớp rồi bấm Tiếp để xem từng bạn bước vào (đường màu cam là các cái bắt tay mới):
Cách 1Hai vòng lặp đếm từng cặp – $O(m^2)$
Cách "thật thà" nhất: đánh số các bạn từ $1$ đến $m$, với mỗi bạn $i$ duyệt mọi bạn $j$; nếu $i \ne j$ thì bạn $i$ bắt tay bạn $j$, tăng biến đếm. Vì mỗi cái bắt tay giữa $i$ và $j$ bị đếm 2 lần (một lần ở cặp $(i, j)$, một lần ở cặp $(j, i)$) nên cuối cùng chia đôi.
- Biến
demphải làlong longvì nó đếm tới $m(m-1)$. - Hai vòng lặp chạy tất cả $m \cdot m$ ô của bảng (như hình trong khung chạy tay), nên số phép tính là $m^2 = 900N^2$. Với $N = 35$: chỉ khoảng $10^6$ phép – rất nhanh. Với $N = 10^6$: $9 \cdot 10^{14}$ phép – máy chạy cả ngày cũng không xong!
Kết quả chạy thật: bản C++ đúng 12/20 test, quá thời gian ở test 9–11, 13–15, 17, 20; test đúng chạy lâu nhất 0.42s. Bản Python đúng 11/20 test, quá thời gian ở test 9–11, 13–15, 17–18, 20; test đúng chạy lâu nhất 0.95s. Đúng trọn subtask 1, còn ở subtask 2 chỉ "ăn ké" được các test có $N$ nhỏ.
for(j = i + 1; j <= m; j++) dem++; (chỉ đếm cặp $i < j$, không cần chia 2) thì mình chạy thử: bản C++ đó đúng 20/20 test; test đúng chạy lâu nhất 0.02s! Lý do: với -O2, g++ nhận ra vòng trong chỉ là "cộng thêm $m - i$" nên tự thay bằng phép cộng, chương trình còn $O(m)$. Đừng trông chờ vào may mắn này: chỉ cần thêm một câu if như code ở trên là trình biên dịch chịu thua, và các trình chấm/cờ biên dịch khác có thể cho kết quả khác.Cách 2Một vòng lặp – $O(m)$
Dùng đúng ý tưởng "lần lượt bước vào phòng": bạn thứ $i$ bắt tay $i - 1$ bạn đến trước, nên chỉ cần một vòng lặp cộng dồn $i - 1$.
- Không còn phải xét từng cặp, mỗi bạn chỉ tốn 1 phép cộng → $m = 3 \cdot 10^7$ phép cộng, C++ chạy chưa tới 0,1 giây.
- Python thì chậm hơn C++ cỡ vài chục lần với vòng lặp, $3 \cdot 10^7$ vòng là quá sức trong 1 giây.
Kết quả chạy thật: bản C++ đúng 20/20 test; test đúng chạy lâu nhất 0.01s. Bản Python đúng 16/20 test, quá thời gian ở test 9–10, 14, 17; test đúng chạy lâu nhất 0.32s.
Cách 3Công thức $C_m^2 = \dfrac{m(m-1)}{2}$ – $O(1)$
Tổng $0 + 1 + \dots + (m - 1)$ có công thức quen thuộc $\dfrac{m(m-1)}{2}$. Đây cũng chính là số cách chọn 2 bạn trong $m$ bạn: $C_m^2$. Chú ý $m$ và $m - 1$ là hai số liên tiếp nên luôn có một số chẵn → $m(m-1)$ chia hết cho 2, phép chia nguyên không làm mất gì.
Bẫy kinh điển: tràn số int
Nhiều bạn viết như sau, và còn rất "cẩn thận" khai báo biến kết quả là long long:
nlàint, các hằng30,1,2cũng làint→ toàn bộ biểu thức30 * n * (30 * n - 1) / 2được máy tính bằng kiểuint(32 bit, tối đa $2\,147\,483\,647$).- Chỉ sau khi tính xong (đã tràn) kết quả mới được gán sang
long long ans– lúc này đã quá muộn, giá trị sai đã được "đóng gói" rồi. - Với $N = 10^6$: $m(m-1) \approx 9 \cdot 10^{14}$, gấp hơn 400 nghìn lần giới hạn
int, máy chỉ giữ lại 32 bit cuối → ra một số âm vô nghĩa.
Kết quả chạy thật: bản C++ này đúng 12/20 test, sai ở test 9–11, 13–15, 17, 20; test đúng chạy lâu nhất 0.00s – sai đúng 8 test có $m(m-1) > 2^{31}-1$ (test 9–11, 13–15, 17, 20), mất gần hết subtask 2 dù thuật toán hoàn toàn đúng!
Em kéo $N$ lên dần để xem lúc nào ô nhớ int bị tràn:
Chú thích: trong C++, tràn số kiểu int là "hành vi không xác định" – chuẩn không quy định kết quả, mỗi trình biên dịch có thể ra một số rác khác nhau. Con số "code dùng int in ra" ở trên là đúng con số mình chạy thật bằng g++ -O2 (nó đổi biểu thức thành $450n^2 - 15n$ rồi tính trong 32 bit). Điều chắc chắn duy nhất: kết quả sai.
Sửa lại: dùng long long ngay từ đầu
Chỉ cần n (và m) là long long thì mọi phép nhân đều tính bằng 64 bit (tối đa khoảng $9,2 \cdot 10^{18}$), dư sức chứa $9 \cdot 10^{14}$. Một cách khác là viết 30LL * n để ép phép nhân đầu tiên sang long long.
- Với Python thì không lo tràn số: số nguyên Python tự lớn tuỳ ý. Chỉ cần nhớ dùng
//(chia nguyên) thay vì/, nếu không sẽ in ra số thực kiểu435.0.
Kết quả chạy thật: bản C++ đúng 20/20 test; test đúng chạy lâu nhất 0.00s. Bản Python đúng 20/20 test; test đúng chạy lâu nhất 0.01s. Full điểm.
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. Hai vòng lặp $O(m^2)$ | C++ | 12/20 | > 1s | Quá thời gian test 9–11, 13–15, 17, 20 |
| Python | 11/20 | > 1s | Quá thời gian test 9–11, 13–15, 17–18, 20 | |
| 2. Một vòng lặp $O(m)$ | C++ | 20/20 | 0.01s | Full điểm |
| Python | 16/20 | > 1s | Quá thời gian test 9–10, 14, 17 | |
3. Công thức, dùng int | C++ | 12/20 | 0.00s | Sai test 9–11, 13–15, 17, 20 (tràn số) |
3. Công thức, long long | C++ | 20/20 | 0.00s | Full điểm |
| Python | 20/20 | 0.01s | Full điểm |
long long cho cả các biến tham gia phép nhân, không chỉ cho biến kết quả.
Nhận xét
Đăng nhận xét