Bài 2: Tạo bộ test chuẩn cho bài lập trình – Sinh test, đối chiếu lời giải trâu và đóng gói cho Themis

Một đề thi hay có thể bị hỏng chỉ vì bộ test yếu: lời giải sai vẫn được điểm tối đa, còn lời giải đúng lại bị chấm sai vì đáp án nhầm. Bài viết này giới thiệu quy trình tạo test mà các ban ra đề vẫn dùng: sinh test tự động, đối chiếu với lời giải "trâu" và đóng gói thành thư mục chấm được ngay bằng Themis.

Bài thứ hai của chuyên mục "Góc giáo viên". Toàn bộ code trong bài đã được chạy thử; thầy cô có thể sao chép và dùng ngay cho bài của mình.

👩‍🏫 Thầy cô đang bồi dưỡng đội tuyển HSG Tin? Khóa học dành cho giáo viên giúp thầy cô cập nhật kiến thức, nhận đề thi và được hỗ trợ bài tập lâu dài. Liên hệ Zalo 0767666702 hoặc bấm nút "Đăng ký học" ở đầu trang.

1. Một bộ test tốt gồm những gì?

Theo VNOI Wiki, bộ test nên có đủ bốn loại:

Loại test	Ví dụ	Mục đích
Test nhỏ	Ngẫu nhiên, kích thước nhỏ	Dễ kiểm tra bằng tay, phát hiện lỗi sai
Test biên	n = 1, giá trị nhỏ nhất/lớn nhất, toàn số âm…	Bắt các lỗi "quên trường hợp đặc biệt"
Test lớn	Kích thước tối đa	Phân biệt lời giải nhanh và lời giải chậm
Test đặc biệt	Cây dạng đường thẳng, dãy tăng dần…	Những dạng dữ liệu ngẫu nhiên hiếm khi sinh ra

Hình 1. Bốn loại test nên có trong mỗi bộ test, minh họa với bài DOANCON.

2. Ba chương trình cần có

Ví dụ với bài DOANCON: cho dãy n số nguyên (n ≤ 10⁵, |a_i| ≤ 10⁹), tìm tổng lớn nhất của một đoạn con liên tiếp.

• Lời giải chuẩn: thuật toán nhanh (Kadane, O(n)).
• Lời giải trâu: thử mọi đoạn con (O(n²)) – chậm nhưng gần như chắc chắn đúng.
• Chương trình sinh test: tạo dữ liệu ngẫu nhiên theo tham số.

Lời giải chuẩn (C++) và lời giải trâu (Python)

// Lời giải chuẩn: tổng đoạn con lớn nhất (thuật toán Kadane), O(n)
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    long long best = LLONG_MIN, cur = 0;
    for(int i = 0; i < n; i++){
        long long x; cin >> x;
        cur = max(x, cur + x);          // đoạn tốt nhất kết thúc tại i
        best = max(best, cur);
    }
    cout << best << "\n";
}

# Lời giải "trâu": thử mọi đoạn con, O(n^2) – chậm nhưng chắc chắn đúng
n = int(input())
a = list(map(int, input().split()))
best = a[0]
for i in range(n):
    s = 0
    for j in range(i, n):
        s += a[j]
        best = max(best, s)
print(best)

3. Đối chiếu tự động (stress test)

Ý tưởng: sinh hàng trăm test nhỏ ngẫu nhiên, chạy cả hai lời giải, nếu kết quả khác nhau thì dừng lại và in test đó ra. Dùng seed cố định để test lỗi luôn tái hiện được.

Hình 2. Vòng lặp stress test: sinh test, chạy hai lời giải, so sánh – dừng ngay khi thấy khác biệt.

gen.py (sinh test) và stress.py (đối chiếu)

# ===== File gen.py =====
# Sinh một test ngẫu nhiên: python3 gen.py <seed> <n_max> <gia_tri_max>
import random, sys
seed, n_max, v = int(sys.argv[1]), int(sys.argv[2]), int(sys.argv[3])
random.seed(seed)                       # cùng seed -> cùng test, dễ tái hiện lỗi
n = random.randint(1, n_max)
print(n)
print(*[random.randint(-v, v) for _ in range(n)])

# ===== File stress.py =====
# So sánh lời giải chuẩn với lời giải trâu trên nhiều test nhỏ ngẫu nhiên
import subprocess, sys
subprocess.run(["g++", "-O2", "-o", "sol", "sol.cpp"], check=True)
for seed in range(1, 501):
    test = subprocess.run([sys.executable, "gen.py", str(seed), "8", "10"],
                          capture_output=True, text=True).stdout
    a = subprocess.run(["./sol"], input=test, capture_output=True, text=True).stdout.strip()
    b = subprocess.run([sys.executable, "trau.py"], input=test, capture_output=True, text=True).stdout.strip()
    if a != b:
        print("SAI o seed", seed); print(test); print("Loi giai:", a, "| Trau:", b); break
else:
    print("Khop ca 500 test ngau nhien")

Kết quả chạy:

Khop ca 500 test ngau nhien

Để thấy sức mạnh của cách làm này, hãy thử một lời giải có lỗi: khởi tạo best = 0 thay vì giá trị nhỏ nhất. Lỗi này chỉ lộ ra khi mọi số đều âm – rất dễ lọt nếu chỉ thử vài ví dụ bằng tay:

Kết quả chạy với lời giải có lỗi:

SAI o seed 2
1
-8

Loi giai: 0 | Trau: -8

Chỉ sau 2 test, chương trình đã tìm ra dữ liệu làm lời giải sai: dãy chỉ có một số −8.

4. Đóng gói bộ test cho Themis

Khi lời giải chuẩn đã được kiểm chứng, dùng nó để tạo đáp án cho bộ test chính thức – kết hợp đủ test biên, test lớn và test đặc biệt – theo đúng cấu trúc thư mục của Themis (xem Bài 1):

Hình 3. Quy trình đóng gói bộ test: từ danh sách test đến thư mục DOANCON chấm được ngay bằng Themis.

taotest.py – tạo thư mục DOANCON/Test01…Test10

# Tạo bộ test theo cấu trúc thư mục của Themis: DOANCON/Test01/DOANCON.INP, DOANCON.OUT, ...
import os, random, subprocess
subprocess.run(["g++", "-O2", "-o", "sol", "sol.cpp"], check=True)
random.seed(2026)
N = 100000; V = 10**9
tests = [
    [5],                                              # n = 1, số dương
    [-7],                                             # n = 1, số âm
    [-3, -1, -4, -1, -5],                             # toàn số âm (bẫy hay gặp)
    [2, -1, 3, -5, 4, -1, 2, 1, -5, 4],               # ví dụ trong đề
    [random.randint(-100, 100) for _ in range(1000)], # ngẫu nhiên vừa
    [random.randint(-V, V) for _ in range(N)],        # n lớn nhất, ngẫu nhiên
    [V] * N,                                          # tổng tới 10^14: cần long long
    [-V] * N,                                         # toàn âm, n lớn nhất
    [V if i % 2 else -V + 1 for i in range(N)],       # đan xen lớn – nhỏ
    [random.choice([-1, 1]) * random.randint(V - 10, V) for _ in range(N)],
]
for k, a in enumerate(tests, 1):
    d = os.path.join("DOANCON", f"Test{k:02d}")
    os.makedirs(d, exist_ok=True)
    inp = f"{len(a)}\n{' '.join(map(str, a))}\n"
    open(os.path.join(d, "DOANCON.INP"), "w").write(inp)
    out = subprocess.run(["./sol"], input=inp, capture_output=True, text=True).stdout
    open(os.path.join(d, "DOANCON.OUT"), "w").write(out)
    print(f"Test{k:02d}: n = {len(a):6d}, dap an = {out.strip()}")

Kết quả chạy:

Test01: n =      1, dap an = 5
Test02: n =      1, dap an = -7
Test03: n =      5, dap an = -1
Test04: n =     10, dap an = 6
Test05: n =   1000, dap an = 3545
Test06: n = 100000, dap an = 214967457146
Test07: n = 100000, dap an = 100000000000000
Test08: n = 100000, dap an = -1000000000
Test09: n = 100000, dap an = 1000049999
Test10: n = 100000, dap an = 390999998410

Test07 có đáp án 10¹⁴ – vượt kiểu int. Đây là test "bẫy" giúp phân biệt học sinh biết dùng long long với học sinh không để ý giới hạn. Mỗi bộ test nên có ít nhất một test như vậy.

5. Công cụ chuyên nghiệp: testlib và Polygon

testlib.h là thư viện do Mike Mirzayanov (người sáng lập Codeforces) phát triển, được dùng trên Polygon và Codeforces. Thư viện hỗ trợ viết bộ sinh test, bộ kiểm tra dữ liệu (validator) và trình chấm (checker). Ưu điểm lớn: bộ sinh số ngẫu nhiên rnd cho cùng một test trên mọi máy, mọi trình biên dịch.

Sinh test bằng testlib

// Bộ sinh test dùng testlib: ./gen_testlib -n=100000 -v=1000000000 1
#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char* argv[]){
    registerGen(argc, argv, 1);              // hạt giống ngẫu nhiên lấy từ tham số dòng lệnh
    int n = opt<int>("n");
    long long v = opt<long long>("v");
    println(n);
    vector<long long> a(n);
    for(auto& x : a) x = rnd.next(-v, v);    // số ngẫu nhiên trong đoạn [-v, v]
    println(a);
}

Kết quả chạy:

$ ./gen_testlib -n=5 -v=10 1
5
-5 1 -5 3 -3
$ ./gen_testlib -n=5 -v=10 2
5
-5 9 -2 7 -2

Hình 4. Ba loại chương trình viết bằng testlib: sinh test, kiểm tra dữ liệu và trình chấm.

• Validator (registerValidation): đọc test với giới hạn chặt, phát hiện test sai đề (số vượt giới hạn, thừa dấu cách…).
• Checker (registerTestlibCmd): dùng cho bài có nhiều đáp án đúng.
• Polygon (polygon.codeforces.com): hệ thống soạn đề trực tuyến của Codeforces, quản lý đề, test, lời giải đúng/sai và tự kiểm tra toàn bộ.

Cần bộ test cho một bài cụ thể mà chưa có thời gian tự làm? Thầy cô trong khóa học dành cho giáo viên có thể gửi đề để được hỗ trợ tạo test và lời giải.

🎓 Quyền lợi khi thầy cô đăng ký khóa học dành cho giáo viên

• Cập nhật kiến thức liên tục: chuyên đề thuật toán, cấu trúc dữ liệu và xu hướng ra đề HSG mới nhất.
• Nhận đề thi theo yêu cầu: cần đề kiểm tra hay thi thử cho học sinh, thầy cô được cung cấp đề lấy từ kho đề của khóa học, kèm bộ test và lời giải.
• Hỗ trợ bài tập lâu dài: gặp bài khó – kể cả bài không có trong danh sách bài tập của khóa – thầy cô vẫn được giải đáp, hỗ trợ trong nhiều năm.
• Đồng hành bồi dưỡng đội tuyển: góp ý lộ trình, cách chấm bài, tổ chức thi cho học sinh.

📩 Liên hệ Zalo 0767666702 (thầy Nguyễn Việt Nam Sơn) hoặc bấm nút "Đăng ký học" ở đầu trang.

📖 ĐỌC TIẾP: GÓC GIÁO VIÊN

Bài 3: Tổ chức thi thử HSG Tin trong phòng máy – Bảng kiểm tra từ chuẩn bị máy đến chấm điểm

Đọc tiếp: Thi thử trong phòng máy →

← Bài trước: Cài đặt ThemisXem tất cả 4 bài →

Nguồn tham khảo

• VNOI Wiki – Sinh test
• Codeforces – What are generators? (Mike Mirzayanov)
• Codeforces – Generators with testlib.h
• Codeforces – [testlib] Validators
• Codeforces – [testlib] Checkers
• GitHub – MikeMirzayanov/testlib
• Codeforces – How to test your program in Python
• Polygon