Kỳ thi học sinh giỏi quốc gia môn Tin học (VOI): thể thức hai ngày thi, chủ đề hay gặp và cách chia 180 phút

Kỳ thi chọn học sinh giỏi quốc gia THPT môn Tin học, thường được gọi tắt là VOI (Vietnam Olympiad in Informatics), do Bộ Giáo dục và Đào tạo tổ chức hằng năm. Mỗi tỉnh, thành phố cử một đội tuyển gồm các học sinh đã vượt qua vòng chọn của địa phương. Với phần lớn học sinh chuyên Tin, đây là kỳ thi quan trọng nhất trong ba năm THPT.

Bài viết này dành cho học sinh lớp 10, 11 đang ở đội tuyển tỉnh và phụ huynh muốn hiểu kỳ thi. Nội dung gồm: thể thức thi và quyền lợi khi đạt giải, các nhóm kiến thức thường xuất hiện, cách chia 180 phút của một buổi thi, và một bài mẫu theo phong cách bài mở đầu của đề VOI kèm chạy tay chi tiết.

1. Thể thức thi và quyền lợi khi đạt giải

Kỳ thi diễn ra trong hai buổi thi, mỗi buổi thí sinh giải 3 bài trong 180 phút bằng máy tính. Bài làm là chương trình nguồn (thường là C++, một số năm có Pascal và Python), được máy chấm chạy với bộ test bí mật sau khi kết thúc buổi thi.

Điểm khác biệt lớn nhất so với kỳ thi đồng đội như ICPC là cách chấm. Mỗi bài VOI được chia thành nhiều subtask (nhóm test), mỗi nhóm có ràng buộc riêng và một phần điểm riêng. Ví dụ, một bài có thể chia thành: nhóm 1 với \(N \le 20\), nhóm 2 với \(N \le 2000\), nhóm 3 với một điều kiện đặc biệt (dữ liệu đã sắp xếp, đồ thị là đường thẳng), và nhóm cuối với \(N \le 2 \cdot 10^5\). Thí sinh không cần giải trọn bài mới có điểm.

Cách chấm này giống với kỳ thi Olympic Tin học quốc tế (IOI), nơi các học sinh có kết quả cao nhất của Việt Nam sẽ tham dự sau vòng chọn đội tuyển. Các thí sinh có điểm cao nhất VOI được triệu tập vào vòng chọn đội tuyển dự thi quốc tế.

Về quyền lợi, học sinh đạt giải Nhất, Nhì, Ba được xét tuyển thẳng vào đại học theo quy chế tuyển sinh hiện hành của Bộ Giáo dục và Đào tạo, với điều kiện về tốt nghiệp THPT và ngành đăng ký phù hợp với môn đạt giải. Mỗi trường có thể có thêm quy định riêng, nên học sinh cần đọc thông báo tuyển sinh của trường mình nhắm tới.

2. Các nhóm kiến thức thường gặp

Đề VOI không công bố danh sách chủ đề cố định, nhưng nhìn lại đề các năm, có thể chia kiến thức cần chuẩn bị thành ba tầng:

Nếu bạn đang ở tầng nền tảng, hãy xem Lộ trình lập trình thi đấu và HSG Tin học để có thứ tự học hợp lý. Đừng vội học các kỹ thuật nâng cao khi tầng nền tảng chưa chắc, vì phần lớn điểm của đề đến từ hai tầng đầu.

3. Cách chia 180 phút trong một buổi thi

Lỗi phổ biến nhất của thí sinh VOI không phải thiếu kiến thức, mà là dồn hơn hai tiếng vào subtask cuối của một bài rồi bỏ trắng các phần dễ của hai bài còn lại. Bốn chặng dưới đây giúp tránh lỗi đó:

1. Phút 0–20: đọc cả ba bài. Chưa gõ code. Với mỗi bài, ghi ra giấy nháp: các subtask, phần điểm, thuật toán bạn nghĩ ra cho từng subtask và thời gian ước tính để viết.
2. Phút 20–75: làm bài bạn tự tin nhất. Viết lời giải vét cạn cho subtask nhỏ trước (thường chỉ 10–15 dòng), rồi mới viết lời giải nhanh. Giữ cả hai trong cùng chương trình: nếu \(N\) nhỏ thì gọi hàm vét cạn, nếu \(N\) lớn thì gọi hàm nhanh.
3. Phút 75–150: lấy các subtask dễ của hai bài còn lại. Một lời giải quay lui lấy được nhóm test nhỏ của bài khó thường chỉ mất 15 phút, trong khi cố nâng một bài từ phần lớn điểm lên trọn điểm có thể mất cả giờ mà chưa chắc thành công.
4. Phút 150–180: kiểm tra, không viết thuật toán mới. Rà lại tên tệp và cách đọc ghi theo đúng quy định của đề, kích thước mảng đủ cho subtask lớn nhất, các phép nhân có thể tràn int (dùng long long), và chạy lại ví dụ trong đề.

Ở chặng 2, hàm vét cạn còn có một công dụng nữa: làm bản đối chiếu cho hàm nhanh. Sinh vài trăm test nhỏ ngẫu nhiên và so kết quả hai hàm là cách nhanh nhất để bắt lỗi trước khi hết giờ. Cách làm chi tiết có trong bài Kỹ thuật sinh test và đối chiếu code. Còn cách đọc ràng buộc để suy ra độ phức tạp cần đạt được trình bày ở bài Cách đọc đề và ăn điểm subtask.

4. Bài mẫu: bán kính phủ sóng nhỏ nhất

Bài đầu của mỗi buổi thi VOI thường kiểm tra một kỹ thuật nền tảng được kết hợp khéo léo. Bài dưới đây là ví dụ điển hình cho kỹ thuật tìm kiếm nhị phân trên đáp án kết hợp kiểm tra bằng tham lam.

Đề bài: Trên một con đường thẳng có \(N\) ngôi nhà ở các tọa độ nguyên \(X_1, \dots, X_N\). Bạn được đặt tối đa \(K\) trạm phát sóng, mọi trạm có cùng bán kính nguyên \(R \ge 0\). Một trạm đặt tại vị trí \(P\) phủ được mọi nhà trong đoạn \([P - R, P + R]\), tức một đoạn dài \(2R\). Tìm \(R\) nhỏ nhất để \(K\) trạm phủ hết mọi ngôi nhà. Ràng buộc: \(N \le 2 \cdot 10^5\), \(0 \le X_i \le 10^9\).

Quan sát 1: đáp án có tính đơn điệu. Nếu bán kính \(R\) đủ để phủ hết, thì mọi bán kính lớn hơn cũng đủ. Nếu \(R\) không đủ, mọi bán kính nhỏ hơn cũng không đủ. Vì vậy ta tìm kiếm nhị phân \(R\) trong đoạn từ \(0\) đến \(\lceil (X_{\max} - X_{\min}) / 2 \rceil\).

Quan sát 2: kiểm tra một giá trị \(R\) bằng tham lam. Sắp xếp tọa độ tăng dần. Xét ngôi nhà đầu tiên chưa được phủ ở tọa độ \(X_i\). Không có nhà nào chưa phủ nằm bên trái \(X_i\), nên phủ thêm về bên trái là lãng phí. Cách đặt tốt nhất là cho đoạn phủ bắt đầu đúng tại \(X_i\), tức trạm phủ \([X_i, X_i + 2R]\). Bỏ qua mọi nhà trong đoạn này rồi lặp lại. Nếu số trạm cần dùng không vượt quá \(K\) thì \(R\) đủ. Bước kiểm tra này chạy trong \(\mathcal{O}(N)\), cả bài là \(\mathcal{O}(N \log N + N \log X)\).

Chạy tay với \(X = [1, 3, 6, 10, 14, 16]\), \(K = 2\). Đoạn tìm kiếm ban đầu là \([0, 8]\):

Đoạn tìm kiếm rỗng sau bước 4, đáp án là \(R = 3\). Kiểm tra lại: với \(R = 2\), mỗi trạm chỉ phủ một đoạn dài 4, mà khoảng cách từ nhà 1 tới nhà 16 là 15, hai đoạn dài 4 không thể phủ hết.

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

// Tìm bán kính R nguyên nhỏ nhất để K trạm phủ hết N tọa độ (mỗi trạm phủ đoạn dài 2*R)
bool can_cover(const vector<long long>& x, int k, long long r) {
    int used = 0;
    int i = 0, n = (int)x.size();
    while (i < n) {
        used++;
        if (used > k) return false;
        long long limit = x[i] + 2 * r;
        while (i < n && x[i] <= limit) i++;
    }
    return true;
}

long long min_radius(vector<long long> x, int k) {
    sort(x.begin(), x.end());
    long long lo = 0, hi = (x.back() - x.front() + 1) / 2, ans = hi;
    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        if (can_cover(x, k, mid)) {
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    if (!(cin >> n >> k)) {
        cout << min_radius({1, 3, 6, 10, 14, 16}, 2) << "\n";
        return 0;
    }
    vector<long long> x(n);
    for (int i = 0; i < n; ++i) cin >> x[i];
    cout << min_radius(x, k) << "\n";
    return 0;
}

import sys

def can_cover(x: list[int], k: int, r: int) -> bool:
    used = 0
    i = 0
    n = len(x)
    while i < n:
        used += 1
        if used > k:
            return False
        limit = x[i] + 2 * r
        while i < n and x[i] <= limit:
            i += 1
    return True

def min_radius(x: list[int], k: int) -> int:
    x.sort()
    lo = 0
    hi = (x[-1] - x[0] + 1) // 2
    ans = hi
    while lo <= hi:
        mid = (lo + hi) // 2
        if can_cover(x, k, mid):
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return ans

def main() -> None:
    data = sys.stdin.read().split()
    if not data:
        print(min_radius([1, 3, 6, 10, 14, 16], 2))
        return
    n = int(data[0])
    k = int(data[1])
    x = [int(v) for v in data[2:2 + n]]
    print(min_radius(x, k))

if __name__ == "__main__":
    main()

Với dữ liệu mẫu, chương trình in:

3

Nếu đây là bài thi thật, subtask đầu (ví dụ \(N \le 1000\), tọa độ nhỏ) có thể giải bằng cách thử lần lượt từng giá trị \(R\) từ 0 trở lên và kiểm tra bằng đúng hàm tham lam ở trên. Lời giải đó vừa lấy điểm chắc, vừa dùng làm bản đối chiếu cho lời giải tìm kiếm nhị phân.

5. Chuẩn bị trong những tháng trước kỳ thi

• Giải đề các năm trước theo đúng thời gian. Ngồi đủ 180 phút, không xem lời giải, rồi tự chấm theo từng subtask để biết mình thường mất điểm ở đâu.
• Ghi sổ lỗi. Mỗi lần mất điểm vì tràn số, sai chỉ số hay đọc sai đề, ghi lại một dòng. Đọc lại sổ này trước mỗi buổi thi.
• Luyện thi trực tuyến đều đặn. Các vòng thi trên Codeforces giúp quen áp lực thời gian; xem Cách luyện Codeforces cho người mới.
• Giữ sức cho buổi thi thứ hai. Hai buổi thi được chấm độc lập. Kết quả buổi đầu chưa như ý vẫn có thể bù lại ở buổi sau, nên tránh ngồi so đáp án và tự chấm sau buổi thi đầu tiên.

Luyện ngay trên Big-O Coding

Ba bài dưới đây có cấu trúc subtask theo phong cách VOI, gồm tìm kiếm nhị phân trên đáp án, quy hoạch động và cây phân đoạn:

Nguồn tham khảo

• Wikipedia — International Olympiad in Informatics
• USACO Guide — Contest Strategy
• USACO Guide — Binary Search