Bài 22: Kỹ năng luyện thi lập trình: đọc giới hạn, tránh tràn số, debug, sinh test và chấm trâu (stress test)
Lời mở đầu
Sau bảy bài thuật toán, em đã có trong tay quay lui, chặt nhị phân, hai con trỏ, tham lam, quy hoạch động, bitmask và BFS/DFS. Nhưng trong phòng thi, điểm số còn phụ thuộc rất nhiều vào những thứ không phải thuật toán: đọc giới hạn để biết cần độ phức tạp nào, tránh các lỗi kinh điển, và nhất là tự kiểm tra bài của mình khi không có hệ thống chấm.
Bài này gom lại các kỹ năng đó thành quy trình cụ thể. Phần đáng giá nhất là kỹ thuật chấm trâu (stress test): viết thêm một lời giải chậm nhưng chắc chắn đúng, sinh hàng nghìn test nhỏ ngẫu nhiên và so sánh hai lời giải. Đây là cách các bạn thi học sinh giỏi giỏi nhất dùng để bắt lỗi trước khi nộp bài.
cerr; viết trình sinh test ngẫu nhiên, lời giải trâu và script đối chiếu; chiến thuật làm bài theo subtask. Có khung chạy tay, công cụ ước lượng thời gian và 8 bài tập.Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Đọc giới hạn để chọn thuật toán
Một máy chấm thông thường chạy được khoảng $10^8$ phép tính đơn giản mỗi giây với C++ (Python chậm hơn khoảng 10 – 50 lần, tức cỡ $10^7$). Vì vậy chỉ cần nhìn giới hạn $n$ trong đề, em đã đoán được đề muốn thuật toán độ phức tạp nào:
| Giới hạn $n$ | Độ phức tạp chấp nhận được | Thường là |
|---|---|---|
| $n \le 10$ | $O(n!)$ | sinh hoán vị, quay lui (bài 15) |
| $n \le 20$ | $O(2^n \cdot n)$ | duyệt bitmask (bài 20) |
| $n \le 500$ | $O(n^3)$ | ba vòng lặp, QHĐ đoạn |
| $n \le 5000$ | $O(n^2)$ | hai vòng lặp, QHĐ hai chiều (bài 19) |
| $n \le 10^6$ | $O(n \log n)$ | sắp xếp, chặt nhị phân (bài 16), BFS |
| $n \le 10^8$ | $O(n)$ | một vòng lặp, hai con trỏ (bài 17) |
| $n \le 10^{18}$ | $O(\log n)$ hoặc $O(1)$ | công thức toán, chặt nhị phân, lũy thừa nhanh |
Đề thi thường chia subtask: ví dụ 40% test có $n \le 1000$, 60% còn lại $n \le 10^5$. Đọc kỹ thì em biết: lời giải $O(n^2)$ đơn giản đã lấy được 40% điểm.
Thử ước lượng: nhập $n$ và xem mỗi độ phức tạp cần bao nhiêu phép tính, chạy mất khoảng bao lâu với C++ và Python (giới hạn thời gian 1 giây).
Phần 2Các lỗi kinh điển làm mất điểm
Lỗi dưới đây xuất hiện trong bài làm của rất nhiều bạn, kể cả bạn giỏi. Hãy biến danh sách này thành thói quen kiểm tra trước khi nộp:
- Tràn số.
intchỉ chứa tới khoảng $2.1 \cdot 10^9$. Tổng của $10^5$ số cỡ $10^9$, hay tích hai số cỡ $10^5$, đều tràn. Dùnglong long(tới $9.2 \cdot 10^{18}$) và viết1LL * a * bkhi nhân hai biếnint. - Mảng ngoài biên. Khai báo
a[n]nhưng truy cậpa[n], hoặc vòng lặpi <= nvới mảng đánh số từ 0. Khai báo dư vài phần tử (N = 100005) và kiểm tra lại điều kiện vòng lặp. - Quên reset khi nhiều test. Đề có $T$ test mà biến đếm, mảng đánh dấu, danh sách kề không được xóa giữa các test.
- Khởi tạo sai. Tìm max mà khởi tạo
best = 0trong khi đáp án có thể âm; tìm min mà khởi tạo1e9trong khi giá trị tới $10^{18}$. - Số thực. In sai số chữ số thập phân, so sánh
==hai số thực, chia hai số nguyên ra số nguyên (7 / 2 = 3). - Nhập/xuất chậm. Với $10^6$ số, C++ cần
ios::sync_with_stdio(false); cin.tie(nullptr);, Python cầnsys.stdin. - Trường hợp biên. $n = 1$, mảng toàn số bằng nhau, toàn số âm, không có đáp án (phải in $-1$)…
Khung chạy tay dưới đây cho thấy tràn số âm thầm thế nào: cùng một phép tính nhưng ba cách khai báo cho ba kết quả khác nhau. Máy không báo lỗi, chỉ cho kết quả sai.
Python: số nguyên tự mở rộng, không tràn (nhưng chậm hơn)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int s1 = 0;
long long s2 = 0, s3 = 0;
for(int i = 0; i < n; i++){
int a;
cin >> a;
s1 += a * a;
s2 += a * a;
s3 += 1LL * a * a;
}
cout << s1 << "\n" << s2 << "\n" << s3;
return 0;
}n = int(input())
a = list(map(int, input().split()))
s = sum(x * x for x in a) # số nguyên Python không bao giờ tràn
print(s)
print(s)
print(s)Mô phỏng trực quan. Tràn số là lỗi mất điểm “oan” nhất, vì máy không hề báo lỗi mà chỉ âm thầm cho ra số sai. Em xem ba cách tính tổng bình phương chạy song song trên đúng dữ liệu 50000 50000 50000, để thấy chính xác bước nào và vì sao từng cách bắt đầu sai:
Phần 3Debug có hệ thống
Khi chương trình cho kết quả sai, đừng sửa “đoán mò”. Làm theo trình tự:
- Tái hiện: tìm một test nhỏ nhất có thể mà chương trình sai (phần 4 sẽ chỉ cách để máy tự tìm).
- Tính tay đáp án đúng của test đó và các giá trị trung gian mình mong đợi (như khung “chạy tay” trong các bài).
- In ra để xem: in các biến quan trọng bằng
cerr. Luồngcerrkhông lẫn vào đáp án ởcout, nên quên xóa cũng ít khi bị chấm sai (nhưng vẫn nên xóa vì in nhiều sẽ chậm). - Khoanh vùng: tìm dòng đầu tiên mà giá trị in ra khác giá trị tính tay. Lỗi nằm ngay trước đó.
#define dbg(x) cerr << #x << " = " << (x) << "\n"
...
dbg(i); dbg(best); // in ra: i = 3, best = 7Python dùng print(..., file=sys.stderr). Ngoài ra, biên dịch C++ với -Wall -Wextra để trình biên dịch cảnh báo biến chưa khởi tạo, so sánh có dấu/không dấu…, và -fsanitize=address,undefined để bắt truy cập ngoài mảng, tràn số ngay khi chạy.
Phần 4Sinh test và chấm trâu (stress test)
Ý tưởng chấm trâu cần ba chương trình:
- sol: lời giải nhanh em muốn nộp (có thể có lỗi).
- trau: lời giải chậm, viết đơn giản nhất có thể, chẳng hạn duyệt hết mọi khả năng. Chậm nhưng gần như chắc chắn đúng.
- gen: sinh một test nhỏ ngẫu nhiên (dùng hạt giống – seed – để tái hiện được).
Một script chạy vòng lặp: sinh test, chạy cả hai lời giải, so kết quả; khác nhau thì dừng lại và in test đó. Vì test nhỏ (n = 2..5), em dễ dàng tính tay để tìm lỗi.
Trình sinh test (C++) và script đối chiếu (Python)
// gen.cpp: sinh test ngẫu nhiên, seed lấy từ tham số dòng lệnh
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char* argv[]){
mt19937 rng(atoi(argv[1]));
int n = rng() % 5 + 2; // test nhỏ: 2..6 phần tử
cout << n << "\n";
for(int i = 0; i < n; i++) cout << rng() % 10 + 1 << " ";
return 0;
}# stress.py: chạy hàng nghìn test, dừng khi sol và trau khác nhau
# (biên dịch trước: g++ gen.cpp -o gen; g++ sol.cpp -o sol; g++ trau.cpp -o trau)
import subprocess
for seed in range(1, 10001):
test = subprocess.run(["./gen", str(seed)], capture_output=True, text=True).stdout
a = subprocess.run(["./sol"], input=test, capture_output=True, text=True).stdout.split()
b = subprocess.run(["./trau"], input=test, capture_output=True, text=True).stdout.split()
if a != b:
print("Sai ở seed", seed)
print(test)
print("sol:", a, " trau:", b)
break
else:
print("Qua 10000 test")Để em thấy rõ cả quy trình trong một chương trình, khung dưới đây gói gen, trau, sol vào một file. Bài toán: cho dãy $a$, tìm giá trị lớn nhất của $a_j - a_i$ với $i < j$. Lời giải nhanh có một lỗi nhỏ: khởi tạo best = 0. Em có nhìn ra trước khi máy tìm thấy không?
Mô phỏng trực quan. Đọc tới đây có bạn vẫn chưa hình dung vòng chấm trâu chạy ra sao. Em xem lại đúng khung chấm trâu ở trên với seed 9 và 20 vòng: mỗi vòng sinh một mảng nhỏ, chạy bản trâu và bản nhanh, so kết quả, cho tới khi bắt được test làm bản nhanh sai:
Phần 5Chiến thuật trong phòng thi
- Đọc hết đề trước (10 – 15 phút): ghi chú giới hạn, subtask, dạng bài của từng câu. Sắp thứ tự làm từ câu mình chắc nhất.
- Ăn điểm subtask trước: có lời giải trâu cho subtask nhỏ thì viết và nộp ngay, rồi mới nghĩ lời giải đầy đủ. Lời giải trâu đó dùng luôn để chấm trâu.
- Đừng kẹt một câu quá lâu: đặt mốc thời gian, hết giờ thì chuyển câu, quay lại sau.
- Tự tạo test: test mẫu, test biên ($n = 1$, giá trị lớn nhất, toàn bằng nhau, không có đáp án), test lớn để đo thời gian.
- Kiểm tra trước khi nộp: tên file, định dạng đầu vào/đầu ra (đọc file hay bàn phím), xóa dòng debug,
long longchỗ cần thiết.
- Đoạn Con (DPSUBSEG) (Dễ)
- Sửa Đèn (Dễ)
- Tích Lớn Nhất (TICHMAX) (Dễ)
- Cắt Dây (CATDAY) (Trung bình)
- Đong Gạo (DONGGAO) (Dễ)
Với mỗi bài ở trên, em hãy thử viết cả lời giải trâu và lời giải nhanh rồi chấm trâu chúng với nhau trước khi xem lời giải trên web.
Bài tậpLuyện các bẫy hay gặp
Cho $n$ số nguyên ($n \le 10^6$, $|a_i| \le 10^9$). In tổng của chúng. Nhớ đọc nhanh.
3
1000000000 1000000000 10000000003000000000💡 Gợi ý
long long. Với $10^6$ số, thêm ios::sync_with_stdio(false); cin.tie(nullptr);, Python dùng sys.stdin.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
long long s = 0;
for(int i = 0; i < n; i++){ long long a; cin >> a; s += a; }
cout << s;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
print(sum(map(int, data[1:n + 1])))Cho $n$ số nguyên dương ($n \le 10^5$, $a_i \le 10^9$). In tích của chúng chia lấy dư cho $10^9 + 7$.
3
1000000000 1000000000 3147💡 Gợi ý
p = p * (a % MOD) % MOD với p kiểu long long. Tích hai số dưới $10^9 + 7$ cỡ $10^{18}$, vẫn vừa long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
const long long MOD = 1000000007;
int n;
cin >> n;
long long p = 1;
for(int i = 0; i < n; i++){ long long a; cin >> a; p = p * (a % MOD) % MOD; }
cout << p;
return 0;
}MOD = 10**9 + 7
n = int(input())
p = 1
for a in map(int, input().split()):
p = p * a % MOD
print(p)Dòng đầu là $T$ ($T \le 1000$). Mỗi test gồm $n$ rồi $n$ số nguyên. Với mỗi test in số lần xuất hiện của giá trị xuất hiện nhiều nhất.
2
5
1 2 2 3 2
3
7 7 13
2💡 Gợi ý
map đếm thì phải tạo mới hoặc xóa map ở đầu mỗi test. Nếu khai báo ngoài vòng lặp mà quên clear(), test thứ hai sẽ cộng dồn số đếm của test trước.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int T;
cin >> T;
while(T--){
int n;
cin >> n;
map<int,int> dem; // khai báo trong vòng lặp: mỗi test một map mới
int best = 0;
for(int i = 0; i < n; i++){ int a; cin >> a; best = max(best, ++dem[a]); }
cout << best << "\n";
}
return 0;
}import sys
from collections import Counter
data = sys.stdin.read().split()
T = int(data[0]); p = 1
out = []
for _ in range(T):
n = int(data[p]); p += 1
c = Counter(data[p:p + n]); p += n
out.append(max(c.values()))
print("\n".join(map(str, out)))Cho $n$ điểm số nguyên ($1 \le n \le 100$, mỗi điểm từ 0 đến 10). In điểm trung bình với đúng 2 chữ số sau dấu phẩy.
3
7 8 108.33💡 Gợi ý
25 / 3 = 8) và in sai định dạng. C++: (double)s / n rồi cout << fixed << setprecision(2); Python: f"{s / n:.2f}".Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int s = 0;
for(int i = 0; i < n; i++){ int a; cin >> a; s += a; }
cout << fixed << setprecision(2) << (double)s / n;
return 0;
}n = int(input())
a = list(map(int, input().split()))
print(f"{sum(a) / n:.2f}")Viết trình sinh test dùng công thức đồng dư: bắt đầu với hạt giống $x$, mỗi lần cần một số ngẫu nhiên thì gán $x = (x \cdot 1103515245 + 12345) \bmod 2^{31}$ và lấy $x \bmod 100 + 1$. Cho $x$ ban đầu và $n$, in $n$ rồi dòng thứ hai là $n$ số sinh được.
1 55
91 76 85 82 75💡 Gợi ý
long long (hoặc unsigned long long). Mod $2^{31}$ tương đương & ((1LL << 31) - 1). Cùng hạt giống thì luôn ra cùng test: đó là lý do ta lưu seed để tái hiện lỗi.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long x; int n;
cin >> x >> n;
cout << n << "\n";
for(int i = 0; i < n; i++){
x = (x * 1103515245 + 12345) % (1LL << 31);
cout << x % 100 + 1 << (i + 1 < n ? " " : "\n");
}
return 0;
}x, n = map(int, input().split())
res = []
for _ in range(n):
x = (x * 1103515245 + 12345) % (1 << 31)
res.append(x % 100 + 1)
print(n)
print(*res)Bài gốc: cho dãy $a_1..a_n$ và số $s$, tìm hai chỉ số $i \ne j$ mà $a_i + a_j = s$ (có thể có nhiều đáp án). Em viết trình chấm: đọc $n$, $s$, dãy $a$, rồi đọc đáp án của thí sinh là hai số $i$, $j$. In OK nếu đáp án hợp lệ, ngược lại in WRONG.
4 9
2 7 4 5
3 4OK💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; long long s;
cin >> n >> s;
vector<long long> a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
long long i, j;
cin >> i >> j;
bool ok = 1 <= i && i <= n && 1 <= j && j <= n && i != j && a[i] + a[j] == s;
cout << (ok ? "OK" : "WRONG");
return 0;
}import sys
data = list(map(int, sys.stdin.read().split()))
n, s = data[0], data[1]
a = [0] + data[2:2 + n]
i, j = data[2 + n], data[3 + n]
ok = 1 <= i <= n and 1 <= j <= n and i != j and a[i] + a[j] == s
print("OK" if ok else "WRONG")Cho $n$ số nguyên ($n \le 2 \cdot 10^5$, $|a_i| \le 10^9$) và $k$. Đếm số cặp $i < j$ có $|a_i - a_j| \le k$.
5 2
1 5 3 4 104💡 Gợi ý
long long! Hãy viết thêm lời giải $O(n^2)$ để chấm trâu.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; long long k;
cin >> n >> k;
vector<long long> a(n);
for(auto &x : a) cin >> x;
sort(a.begin(), a.end());
long long dem = 0;
int i = 0;
for(int j = 0; j < n; j++){
while(a[j] - a[i] > k) i++;
dem += j - i;
}
cout << dem;
return 0;
}import sys
data = list(map(int, sys.stdin.read().split()))
n, k = data[0], data[1]
a = sorted(data[2:2 + n])
dem = 0
i = 0
for j in range(n):
while a[j] - a[i] > k:
i += 1
dem += j - i
print(dem)Cho $n$ số nguyên ($n \le 10^6$, $|a_i| \le 10^9$). Tìm tổng lớn nhất của một đoạn con liên tiếp khác rỗng.
4
-5 -2 -8 -3-2💡 Gợi ý
cur = max(a[i], cur + a[i]), best = max(best, cur). Bẫy: khởi tạo best = 0 sẽ sai khi mọi số đều âm (như ví dụ); phải khởi tạo best = a[0]. Tổng tới $10^{15}$ nên dùng long long. Đây đúng là loại lỗi mà chấm trâu với lời giải $O(n^2)$ sẽ bắt được ngay.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for(auto &x : a) cin >> x;
long long cur = a[0], best = a[0];
for(int i = 1; i < n; i++){
cur = max(a[i], cur + a[i]);
best = max(best, cur);
}
cout << best;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
cur = best = a[0]
for x in a[1:]:
cur = max(x, cur + x)
best = max(best, cur)
print(best)
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét