Cách tự viết trình chấm khi tham dự các kì thi HSG Tin học

Đã bao giờ bạn gặp một trường hợp làm xong một bài tập và đoạn code của bạn chạy đúng với test ví dụ, tuy nhiên khi đem nộp trên OJ (trình chấm online), bạn lại chẳng ăn được điểm nào ngoài cái test ví dụ kia chưa? Rõ ràng bạn đã code bạn đã chạy đúng test ví dụ kia, sao mấy test khác lại chạy sai vậy?

Đây là một trường hợp rất phổ biến khi đoạn code của bạn chưa tối ưu hoặc vẫn còn sai những edge cases, hoặc thậm chí logic code của bạn sai nhưng bằng cách thần kỳ nào đấy bạn vẫn qua được test ví dụ. Điều này là hoàn toàn bình thường bởi hầu như ai sau một vài lần chỉnh sửa code thì mới có thể AC được các bài tập.

Với nhiều người khi làm bài tập trên các trang chấm bài online, chúng ta thường nộp code ngay sau khi đúng test đề bài và nếu chưa ăn được hết bộ test, ta sẽ debug và lặp lại quá trình trên cho đến khi AC. Tuy nhiên, trong các kì thi HSG Tin học các cấp, câu chuyện sẽ rất khác khi ta không được làm bài online mà chỉ khi hết giờ, code được chấm duy nhất một lần. Chiến thuật khi làm bài trên các OJ sẽ không thể áp dụng cho các kì thi này. Từ đó việc tự sinh test và so đáp án là điều dường như bắt buộc để kiểm tra tính đúng đắn của đoạn code bằng việc viết một trình chấm.

1. Cấu trúc của một trình chấm cho bài thi HSG Tin học

Một chương trình chấm sẽ gồm hai phần chính: sinh test và trình chấm.

• Sinh test: tự động sinh ra các bộ input ngẫu nhiên
• Trình chấm: tự động chạy hai chương trình lời giải khác nhau và so output của chúng. Lời giải đầu tiên của bạn sẽ là code chuẩn của bạn, lời giải thứ hai thường sẽ là code trâu mà bạn đảm bảo được tính chính xác của nó.

2. Sinh test

• Việc sinh ra một bộ input ngẫu nhiên có thể sử dụng random trong \(C++\).

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int Rand(int l, int r){ // sinh ngẫu nhiên một số trong đoạn [L, R]
    return uniform_int_distribution<int>(l, r) (rng);
}

Lưu ý: Không nên sử dụng hàm \(rand()\) bởi khoảng \([L, R]\) có thể được sinh ra là quá nhỏ.

3. Trình chấm

Trình chấm sẽ sinh test như trên rồi tự động chạy hai lời giải lần lượt, output được lưu trong hai file riêng biệt NAME.OUT, NAME.ANS. Cuối cùng trình chấm sẽ kiểm sự giống nhau của hai file. Lặp lại quá trình trong \(T\) lần với \(T\) là số test bạn muốn sinh.

Đây là template bạn có thể tham khảo để áp dụng trong các kì thi.

#include <bits/stdc++.h>

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int Rand(int l, int r){ // sinh ngẫu nhiên một số trong đoạn [L, R]
    return uniform_int_distribution<int>(l, r) (rng);
}

string NAME = ""; // điền tên bài ở đây

const int NUMTEST = 30; // số test bạn muốn sinh

int main(){
    for (int iTest = 1; iTest <= NUMTEST; i++){
        ofstream inp((NAME + ".inp").c_str());
        // Bắt đầu sinh test ở đây
        
        /* Ví dụ sinh một mảng n phần tử 
         * int n = Rand(1, 1000);
         * inp << n << endl;
         * for (int i = 1; i <= n; i++){
         *     inp << Rand(1, 1000000000) << " ";
         * }
         * inp << endl;
         * */
        
        // Kết thúc sinh test
        inp.close();
        
        // Chạy hai chương trình code. 
        // Lưu ý là bạn phải compile và run trước chúng để tạo ra file .exe
        system((NAME + ".exe").c_str());
        system((NAME + "_ans.exe").c_str());
        
        // So sánh hai file
        if (system(("fc " + NAME + ".out " + NAME + ".ans").c_str()) != 0) // Hai file không trùng
        {
            cout << "Test " << iTest << ": Wrong Answer" << endl;
            return 0;
        }
        cout << "Test " << iTest << ": Accepted" << endl;
    }
}

4. Lời khuyên

• Ngoài việc sinh random, các bạn nên tự test tay với những trường hợp edge cases \(n = 1\) hoặc \(n = max\) hay \(a_i = Min\) hoặc \(a_i=Max\).
• Nên dành khoảng 10-15 phút cho việc test mỗi bài để đảm bảo không mất điểm đáng tiếc.
• Luyện tập viết trình chấm thường xuyên để có thể áp dụng trong phòng thi.

Xem thêm các kiến thức thú vị tại: https://www.facebook.com/codedreamedu và https://codedream.edu.vn/hoc-thuat-toan/