Kỹ thuật sinh test và đối chiếu code (stress testing): tự tìm test làm sai lời giải trong vài giây

Bạn nộp bài, qua được ví dụ trong đề, nhưng máy chấm báo sai ở test thứ 7. Bạn không được xem test đó. Đọc lại code ba lần vẫn thấy logic hợp lý. Lúc này, cách hiệu quả nhất thường không phải đọc tiếp mà là để máy tính tự đi tìm một test làm chương trình sai.

Kỹ thuật này gọi là stress testing (sinh test và đối chiếu code). Ý tưởng rất đơn giản: viết thêm một lời giải chậm nhưng chắc chắn đúng, sinh thật nhiều test nhỏ ngẫu nhiên, chạy cả hai lời giải và dừng lại ngay khi chúng cho kết quả khác nhau. Test đó chính là chìa khóa để tìm lỗi. Bài viết này trình bày ba thành phần của một bộ stress test, một ví dụ cụ thể với bài đổi tiền, và những lưu ý để dùng kỹ thuật này trong phòng thi.

1. Ba thành phần của một bộ stress test

Điểm mấu chốt nằm ở cột cuối: test nhỏ. Nhiều người sinh test lớn vì nghĩ test lớn mới bắt được lỗi. Thực tế ngược lại: phần lớn lỗi (sai công thức, sai ca biên, sai chỉ số) đều xuất hiện ở dữ liệu rất nhỏ. Test nhỏ còn giúp bạn tính tay được đáp án đúng, điều không thể làm với mảng \(10^5\) phần tử.

Lời giải đối chứng thường chính là lời giải subtask đầu mà bạn đã viết để lấy điểm chắc, như trình bày trong bài Cách đọc đề và ăn điểm subtask. Vì vậy, viết lời giải vét cạn trước không bao giờ là phí thời gian.

2. Ví dụ: thuật toán tham lam đổi tiền sai ở đâu?

Đề bài: Có các loại đồng xu mệnh giá cho trước, mỗi loại dùng không giới hạn. Tìm số đồng xu ít nhất để tạo ra đúng số tiền \(S\).

Một ý tưởng tự nhiên là tham lam: luôn lấy đồng xu lớn nhất còn dùng được. Với hệ tiền như 1, 2, 5, 10, cách này cho kết quả đúng. Nhưng nó có đúng với mọi bộ mệnh giá không? Thay vì cố chứng minh, ta để máy kiểm tra bằng cách so với quy hoạch động — lời giải đối chứng chắc chắn đúng:

\[dp[0] = 0, \qquad dp[i] = \min_{c \in \text{mệnh giá},\ c \le i} \left( dp[i - c] + 1 \right)\]

Chương trình dưới đây duyệt số tiền từ 1 trở lên với bộ mệnh giá \(\{1, 3, 4\}\), chạy cả hai cách và dừng ở số tiền đầu tiên mà kết quả khác nhau:

#include <bits/stdc++.h>
using namespace std;

// Minh họa Stress Testing: phát hiện phản ví dụ nơi Tham lam đổi tiền bị sai so với Quy hoạch động
int greedy_coins(const vector<int>& coins, int amount) {
    vector<int> c = coins;
    sort(c.rbegin(), c.rend());
    int cnt = 0;
    for (int v : c) {
        cnt += amount / v;
        amount %= v;
    }
    return amount == 0 ? cnt : -1;
}

int dp_coins(const vector<int>& coins, int amount) {
    const int INF = 1e9;
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int i = 1; i <= amount; ++i) {
        for (int v : coins) {
            if (i >= v && dp[i - v] != INF) {
                dp[i] = min(dp[i], dp[i - v] + 1);
            }
        }
    }
    return dp[amount] == INF ? -1 : dp[amount];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, max_amt;
    vector<int> coins;
    if (!(cin >> n >> max_amt)) {
        coins = {1, 3, 4};
        max_amt = 10;
    } else {
        coins.resize(n);
        for (int i = 0; i < n; ++i) cin >> coins[i];
    }
    int first_diff = -1, g_ans = -1, d_ans = -1;
    for (int amt = 1; amt <= max_amt; ++amt) {
        int g = greedy_coins(coins, amt);
        int d = dp_coins(coins, amt);
        if (g != d) {
            first_diff = amt;
            g_ans = g;
            d_ans = d;
            break;
        }
    }
    if (first_diff == -1) {
        cout << "MATCH\n";
    } else {
        cout << "DIFF_AT=" << first_diff << " GREEDY=" << g_ans << " DP=" << d_ans << "\n";
    }
    return 0;
}

import sys

def greedy_coins(coins: list[int], amount: int) -> int:
    c = sorted(coins, reverse=True)
    cnt = 0
    for v in c:
        cnt += amount // v
        amount %= v
    return cnt if amount == 0 else -1

def dp_coins(coins: list[int], amount: int) -> int:
    INF = 10**9
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for v in coins:
            if i >= v and dp[i - v] + 1 < dp[i]:
                dp[i] = dp[i - v] + 1
    return -1 if dp[amount] == INF else dp[amount]

def main() -> None:
    data = sys.stdin.read().split()
    if not data:
        coins = [1, 3, 4]
        max_amt = 10
    else:
        n = int(data[0])
        max_amt = int(data[1])
        coins = [int(x) for x in data[2:2 + n]]

    for amt in range(1, max_amt + 1):
        g = greedy_coins(coins, amt)
        d = dp_coins(coins, amt)
        if g != d:
            print(f"DIFF_AT={amt} GREEDY={g} DP={d}")
            return
    print("MATCH")

if __name__ == "__main__":
    main()

Kết quả chạy:

DIFF_AT=6 GREEDY=3 DP=2

Bảng đối chiếu từng số tiền:

Chỉ trong 6 bước, máy đã tìm ra phản ví dụ nhỏ nhất. Nhìn vào test này, lỗi của tham lam hiện ra rõ ràng: lấy đồng 4 trước khiến phần còn lại là 2, phải trả bằng hai đồng 1; trong khi bỏ qua đồng 4 và dùng hai đồng 3 tốt hơn. Nếu chỉ thử với ví dụ trong đề (thường là các số như 7 hoặc 10), bạn có thể không bao giờ phát hiện ra.

Ví dụ này duyệt tuần tự vì không gian test nhỏ. Với các bài khác, ta thay vòng duyệt bằng bộ sinh ngẫu nhiên, như phần tiếp theo.

3. Khung stress test dùng lại cho mọi bài

Khung dưới đây viết bằng Python, gọi hai chương trình đã biên dịch (nhanh và cham), sinh dữ liệu ngẫu nhiên nhỏ và dừng ở test đầu tiên cho kết quả khác. Bạn chỉ cần sửa hàm sinh_test cho từng bài:

import random
import subprocess

def sinh_test(rng):
    n = rng.randint(1, 8)
    a = [rng.randint(-10, 10) for _ in range(n)]
    return f"{n}\n{' '.join(map(str, a))}\n"

def chay(lenh, du_lieu):
    kq = subprocess.run(lenh, input=du_lieu, capture_output=True, text=True, timeout=5)
    return kq.stdout.split()

rng = random.Random(2026)
for lan in range(1, 2001):
    test = sinh_test(rng)
    a = chay(["./nhanh"], test)
    b = chay(["./cham"], test)
    if a != b:
        print("SAI O LAN", lan)
        print(test)
        print("nhanh:", a, "cham:", b)
        break
else:
    print("2000 test deu khop")

Ba chi tiết đáng chú ý:

• Cố định hạt giống ngẫu nhiên (random.Random(2026)). Khi tìm ra test sai và sửa code, bạn chạy lại với cùng hạt giống để chắc chắn test đó đã qua. Trong C++, dùng std::mt19937 rng(2026); thay cho rand().
• So sánh theo từng từ (split()), không so cả chuỗi, để tránh báo sai vì khác dấu cách hay xuống dòng cuối.
• Giới hạn thời gian (timeout=5) để phát hiện cả trường hợp lời giải nhanh bị lặp vô hạn.

4. Khi nào nên dùng và những lưu ý trong phòng thi

Stress testing đặc biệt hiệu quả trong các tình huống sau:

• Bài tham lam: như ví dụ đổi tiền, tham lam thường đúng với test dễ nhưng sai ở trường hợp đặc biệt.
• Bài nhiều ca biên: mảng toàn số âm, \(N = 1\), mọi phần tử bằng nhau, đồ thị không liên thông.
• Lời giải có tối ưu phức tạp: cây phân đoạn, hai con trỏ, quy hoạch động có giảm chiều — chỉ cần sai một chỉ số là kết quả lệch.

Một số lưu ý để không mất thời gian vô ích:

1. Lời giải đối chứng cũng có thể sai. Nếu hai chương trình lệch nhau, hãy tính tay đáp án của test đó trước khi kết luận bên nào sai.
2. Thu nhỏ test khi tìm thấy. Nếu test sai có \(N = 8\), thử giảm giới hạn sinh xuống \(N \le 4\) rồi chạy lại. Test càng nhỏ, lỗi càng dễ nhìn.
3. Chuẩn bị sẵn khung trước kỳ thi. Trong kỳ thi ICPC, nhiều đội in sẵn khung stress test trong tài liệu mang vào phòng thi để gõ trong 2–3 phút. Ở các kỳ thi cá nhân, bạn nên luyện gõ khung này thuộc lòng.
4. Không thay thế việc suy nghĩ về độ phức tạp. Stress test với dữ liệu nhỏ chỉ kiểm tra tính đúng. Để chắc chắn không quá thời gian, hãy tự tạo một test lớn nhất theo ràng buộc và đo thời gian chạy.

Nếu đang luyện trên Codeforces, bạn có thể áp dụng ngay kỹ thuật này cho các bài bị sai sau kỳ thi; xem thêm Cách luyện Codeforces cho người mới. Danh sách các bước gỡ lỗi khác (đọc lại đề, kiểm tra tràn số, in giá trị trung gian) có trong trang Debugging Checklist của USACO Guide ở phần nguồn tham khảo.

Luyện ngay trên Big-O Coding

Ba bài dưới đây đều có lời giải tham lam dễ nghĩ ra nhưng dễ sai ở ca đặc biệt. Hãy viết thêm lời giải vét cạn và chạy đối chiếu trước khi nộp:

Nguồn tham khảo

• USACO Guide — Debugging Checklist
• cppreference — std::mersenne_twister_engine
• CP-Algorithms — tuyển tập thuật toán