Kỳ thi ICPC là gì? Thể thức thi đồng đội, cách tính phạt thời gian và chiến thuật 3 người 1 máy

Trong cộng đồng khoa học máy tính toàn cầu, ICPC (International Collegiate Programming Contest) được mệnh danh là kỳ thi thế vận hội dành cho sinh viên đại học. Khởi nguồn từ Đại học Texas A&M năm 1970, kỳ thi hiện quy tụ hàng chục nghìn sinh viên từ hơn 3.000 trường đại học trên toàn thế giới mỗi năm.

Điểm tạo nên sức hút đặc biệt của ICPC nằm ở thể thức thi đấu: 3 thành viên dùng chung duy nhất 1 máy tính trong suốt 5 giờ liên tục. Mọi quyết định nộp bài sai, mọi phút chiếm giữ bàn phím để gỡ lỗi (debug) đều ảnh hưởng trực tiếp đến thứ hạng của cả đội. Bài viết này tổng hợp cấu trúc các vòng thi ICPC tại Việt Nam và châu Á, phân tích công thức tính điểm chuẩn xác bằng bài toán mô phỏng bảng xếp hạng, đồng thời chia sẻ chiến thuật phối hợp 3 người và chuẩn bị bộ tài liệu in (Team Reference Document).

1. Cấu trúc các vòng thi ICPC từ cấp quốc gia đến World Finals

Hành trình của một đội tuyển sinh viên tại Việt Nam hướng tới vòng chung kết toàn cầu (ICPC World Finals) đi qua chuỗi vòng loại phân tầng chặt chẽ:

Khác với bậc phổ thông vốn có thể thức chấm điểm từng phần theo Subtask (xem thêm tại Lộ trình lập trình thi đấu và HSG Tin học), ICPC áp dụng luật chấm nhị phân tuyệt đối (Pass/Fail): một bài nộp chỉ được tính là giải xong (AC — Accepted) khi vượt qua toàn bộ bộ test ẩn của ban giám khảo. Chỉ cần sai một ca biên duy nhất, bài nộp sẽ nhận phán quyết WA (Wrong Answer), TLE (Time Limit Exceeded) hoặc RTE (Runtime Error) và không có bất kỳ điểm thành phần nào.

2. Luật xếp hạng và cách tính thời gian phạt (Penalty) trong ICPC

Bảng xếp hạng ICPC (Scoreboard) sắp xếp các đội theo hai tiêu chí ưu tiên từ cao xuống thấp:

1. Số lượng bài giải đúng (Solved): Đội nào giải đúng nhiều bài hơn sẽ xếp trên, bất kể thời gian làm bài là bao nhiêu.
2. Tổng thời gian phạt (Total Penalty): Nếu hai đội có cùng số bài giải đúng, đội nào có tổng thời gian phạt nhỏ hơn sẽ xếp trên.

Công thức tính thời gian phạt của một đội được xác định như sau:

\[\text{Tổng Penalty} = \sum_{p \in \text{Các bài đã AC}} \left( t_{\text{AC}}(p) + 20 \times w(p) \right)\]

Trong đó:

• \(t_{\text{AC}}(p)\) là số phút tính từ lúc bắt đầu giờ thi cho tới thời điểm đội nộp bản code đạt AC đầu tiên cho bài \(p\).
• \(w(p)\) là số lần nộp bị từ chối (WA, TLE, MLE, RTE) của bài \(p\) trước khi đạt AC (không tính lỗi biên dịch CE — Compilation Error ở hầu hết các hệ thống chấm chuẩn như DOMjudge).
• Quy tắc sống còn: Nếu một bài \(p\) bị nộp sai \(w(p)\) lần nhưng đến hết giờ vẫn không đạt AC, thì toàn bộ \(w(p)\) lần nộp sai đó không bị cộng phạt vào tổng thời gian của đội.

Hãy theo dõi ví dụ cụ thể với \(7\) lượt nộp bài của hai đội Alpha và Beta trong Hình 1 để thấy rõ tác động của thời gian phạt:

Kết thúc phiên thi, cả Beta và Alpha đều giải được \(2\) bài, nhưng Beta đứng đầu bảng xếp hạng với tổng phạt \(75\) phút so với \(87\) phút của Alpha. Bạn có thể thấy: việc giải các bài dễ thật sớm và hạn chế nộp ẩu khi chưa kiểm tra kỹ ca biên quyết định trực tiếp màu huy chương khi hai đội bằng số bài.

3. Bài toán minh họa: Chương trình tổng hợp bảng xếp hạng ICPC

Các bài toán mô phỏng quy trình thực tế (Simulation) kết hợp sắp xếp đa tiêu chí bằng Bảng băm (Hash Table) rất thường xuất hiện ở nhóm bài mở màn trong đề thi ICPC và Olympic Tin học Sinh viên Việt Nam (OLP). Đoạn chương trình C++17 và Python dưới đây nhận danh sách các lượt nộp bài theo thứ tự thời gian và xuất bảng xếp hạng chuẩn ICPC.

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

// Tính bảng xếp hạng ICPC: mỗi lần nộp sai trước khi AC cộng 20 phút phạt; bài chưa AC không tính phạt
struct Team {
    string name;
    int solved = 0;
    int penalty = 0;
    map<string, int> wrong;
    set<string> ac;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m;
    vector<tuple<string, string, int, string>> subs;
    if (!(cin >> m)) {
        subs = {
            {"Alpha", "A", 12, "AC"},
            {"Beta",  "A", 10, "WA"},
            {"Beta",  "A", 25, "AC"},
            {"Alpha", "B", 40, "WA"},
            {"Alpha", "B", 55, "AC"},
            {"Beta",  "B", 30, "AC"},
            {"Beta",  "C", 90, "TLE"}
        };
    } else {
        for (int i = 0; i < m; ++i) {
            string t, p, v;
            int minute;
            cin >> t >> p >> minute >> v;
            subs.emplace_back(t, p, minute, v);
        }
    }
    map<string, Team> teams;
    for (auto& [t, p, minute, v] : subs) {
        auto& tm = teams[t];
        tm.name = t;
        if (tm.ac.count(p)) continue;
        if (v == "AC") {
            tm.ac.insert(p);
            tm.solved++;
            tm.penalty += minute + tm.wrong[p] * 20;
        } else {
            tm.wrong[p]++;
        }
    }
    vector<Team> board;
    for (auto& kv : teams) board.push_back(kv.second);
    sort(board.begin(), board.end(), [](const Team& a, const Team& b) {
        if (a.solved != b.solved) return a.solved > b.solved;
        if (a.penalty != b.penalty) return a.penalty < b.penalty;
        return a.name < b.name;
    });
    for (size_t i = 0; i < board.size(); ++i) {
        cout << board[i].name << ":" << board[i].solved << ":" << board[i].penalty
             << (i + 1 == board.size() ? "" : " ");
    }
    cout << "\n";
    return 0;
}

import sys

def solve() -> None:
    data = sys.stdin.read().split()
    if not data:
        subs = [
            ("Alpha", "A", 12, "AC"),
            ("Beta",  "A", 10, "WA"),
            ("Beta",  "A", 25, "AC"),
            ("Alpha", "B", 40, "WA"),
            ("Alpha", "B", 55, "AC"),
            ("Beta",  "B", 30, "AC"),
            ("Beta",  "C", 90, "TLE"),
        ]
    else:
        m = int(data[0])
        subs = []
        idx = 1
        for _ in range(m):
            subs.append((data[idx], data[idx + 1], int(data[idx + 2]), data[idx + 3]))
            idx += 4

    teams = {}
    for t, p, minute, v in subs:
        if t not in teams:
            teams[t] = {"solved": 0, "penalty": 0, "wrong": {}, "ac": set()}
        tm = teams[t]
        if p in tm["ac"]:
            continue
        if v == "AC":
            tm["ac"].add(p)
            tm["solved"] += 1
            tm["penalty"] += minute + tm["wrong"].get(p, 0) * 20
        else:
            tm["wrong"][p] = tm["wrong"].get(p, 0) + 1

    board = sorted(teams.items(), key=lambda kv: (-kv[1]["solved"], kv[1]["penalty"], kv[0]))
    print(" ".join(f"{name}:{info['solved']}:{info['penalty']}" for name, info in board))

if __name__ == "__main__":
    solve()

Khi chạy chương trình trên nhật ký \(7\) lượt nộp bài của Alpha và Beta, kết quả thu được là:

Beta:2:75 Alpha:2:87

Hai chi tiết cài đặt cần lưu ý:

1. Nếu một đội đã đạt AC ở bài \(p\) (tm.ac.count(p)), mọi lượt nộp sau đó cho cùng bài \(p\) đều bị bỏ qua hoàn toàn.
2. Khi cả số bài giải được (solved) lẫn tổng thời gian phạt (penalty) đều bằng nhau, hàm so sánh sắp xếp tên đội theo thứ tự từ điển tăng dần để bảng kết quả luôn cố định.

4. Chiến thuật phối hợp 3 người 1 máy và chuẩn bị Notebook 25 trang

Vì chỉ có một bàn phím duy nhất cho ba cái đầu, những đội mạnh nhất không bao giờ để cả ba người cùng nhìn chằm chằm vào một màn hình suốt 5 tiếng. Một quy trình làm việc chuẩn trong phòng thi ICPC gồm bốn nguyên tắc:

1. Chia bộ đề ngay phút đầu tiên: Khi giám thị phát đề giấy (thường từ bài A đến bài M), ba thành viên chia nhau đọc nhanh 3 vùng: người thứ nhất đọc A–D, người thứ hai đọc E–H, người thứ ba đọc I–M. Đồng thời, một người theo dõi bảng xếp hạng trực tuyến để phát hiện ngay bài nào vừa được nhiều đội giải xong đầu tiên (bài "cho điểm" — Giveaway problem).
2. Tối ưu hóa thời gian chiếm máy (Keyboard Time): Máy tính chỉ nên dùng để gõ lời giải đã rõ thuật toán trên giấy hoặc chạy bộ sinh test tự động. Việc suy nghĩ công thức, biến đổi quy hoạch động hay vẽ đồ thị bắt buộc phải thực hiện trên giấy nháp.
3. In code ra giấy để gỡ lỗi (Print Debugging): Tại các vòng thi trực tiếp, ban tổ chức cung cấp tính năng in mã nguồn ra giấy và mang tận bàn. Khi một bài bị WA mà nhìn qua chưa thấy lỗi trong 3 phút, người vừa gõ nên bấm lệnh in code rồi nhường máy ngay cho đồng đội gõ bài khác. Ngồi đọc bản in trên giấy cùng một đồng đội thứ hai thường phát hiện lỗi chỉ số hoặc tràn số nhanh hơn nhiều so với việc cuộn màn hình trong tâm lý căng thẳng.
4. Đóng băng bảng điểm giờ cuối (Scoreboard Freeze): Trong \(60\) phút cuối cùng (từ phút \(240\) đến \(300\)), bảng xếp hạng sẽ bị "đóng băng" — các đội chỉ thấy các bài nộp mới hiển thị trạng thái chờ (?) chứ không biết đối thủ đúng hay sai. Lúc này, đội thi cần tập trung dứt điểm 1–2 bài khả thi nhất thay vì phân tán sức lực sang bài mới.

Chuẩn bị Team Reference Document (Sổ tay thuật toán 25 trang)

Trong vòng thi ICPC Regional và World Finals, mỗi đội được mang vào phòng thi một tập tài liệu in tối đa 25 trang A4 một mặt (cỡ chữ không nhỏ hơn giới hạn quy định). Để tận dụng tối đa 25 trang này, đội bạn nên biên soạn:

• Các khuôn mẫu thuật toán dài, dễ nhầm dấu: Luồng cực đại (Dinic, MCMF), KMP/Z-function/Aho-Corasick, Hình học tính toán (bao lồi, giao điểm đoạn thẳng), Số học (CRT, nghịch đảo modulo, NTT/FFT), Heavy-Light Decomposition và Cây phân đoạn (Segment Tree).
• Kịch bản đối chiếu tự động: Khuôn mẫu 15 dòng script sinh test và đối chiếu code (Stress Testing) để giải cứu các bài bị sai test ẩn vào nửa cuối giờ thi.
• Danh sách kiểm tra trước khi nộp bài: Kiểm tra tràn số long long, kiểm tra mảng toàn số âm, đồ thị không liên thông, và \(N = 1\).

Luyện ngay trên Big-O Coding

Để rèn luyện phản xạ giải nhanh các bài toán mô phỏng, xử lý bảng điểm và tư duy cấu trúc dữ liệu chuẩn ICPC, bạn có thể thực hành ngay 3 bài tập sau trên hệ thống:

Nguồn tham khảo

• Wikipedia — International Collegiate Programming Contest
• ICPC Foundation — trang chính thức ICPC
• USACO Guide — Contest Strategy