Olympic Tin học Sinh viên Việt Nam (OLP): Các khối thi, cấu trúc đề và lộ trình ôn luyện

Mỗi dịp cuối năm (thường vào tháng 11 hoặc tháng 12), hàng trăm sinh viên từ các trường đại học, học viện và cao đẳng trên khắp Việt Nam lại hội tụ tại kỳ thi Olympic Tin học Sinh viên Việt Nam (OLP) kết hợp cùng vòng khu vực ICPC Asia. Nếu như ICPC là cuộc đua đồng đội 3 người 1 máy, thì các khối thi cá nhân của OLP là nơi mỗi sinh viên tự khẳng định năng lực tư duy thuật toán, tốc độ cài đặt và kỹ năng phân tích độ phức tạp độc lập.

Bài viết này giúp bạn nắm rõ sự khác biệt giữa các khối thi trong OLP, cấu trúc đề thi cá nhân, lộ trình ôn luyện cho từng đối tượng sinh viên và minh họa trực tiếp qua bài toán tối ưu hóa mạng lưới bằng thuật toán Kruskal.

1. Phân biệt các khối thi cá nhân và tập thể tại OLP Việt Nam

Để tạo điều kiện công bằng cho sinh viên ở nhiều chuyên ngành và xuất phát điểm khác nhau, Ban tổ chức OLP chia kỳ thi thành các khối thi riêng biệt với quy định đối tượng và độ khó đề thi tăng dần:

Nhờ cơ chế phân khối rõ ràng này, một sinh viên năm nhất chưa từng học đội tuyển chuyên Tin ở cấp 3 vẫn hoàn toàn có cơ hội tranh huy chương Vàng ở khối Không chuyên tin hoặc Chuyên tin nếu ôn luyện bài bản trong 4–6 tháng.

2. Cấu trúc đề thi cá nhân OLP và chiến thuật ăn điểm Subtask

Đề thi cá nhân của các khối Chuyên tin và Siêu cúp thường kéo dài 180 đến 240 phút với \(3\) đến \(4\) bài toán. Khác với luật chấm nhị phân của ICPC, phần thi cá nhân OLP thường chấm điểm theo từng Subtask (ràng buộc con) tương tự phong cách Olympic phổ thông:

• Subtask 1 (\(20\%\text{--}30\%\) số điểm): Giới hạn dữ liệu nhỏ (\(N \le 20\) hoặc \(N \le 1.000\)), cho phép thí sinh dùng nhánh cận, vét cạn hoặc mô phỏng \(\mathcal{O}(N^2)\) để lấy điểm chắc chắn.
• Subtask 2 (\(30\%\text{--}40\%\) số điểm): Giới hạn trung bình (\(N \le 5 \times 10^4\)) hoặc cấu trúc dữ liệu đặc biệt (ví dụ: đồ thị có dạng đường thẳng, cây nhị phân cân bằng, hoặc trọng số cạnh chỉ gồm \(0\) và \(1\)).
• Subtask 3 (\(30\%\text{--}40\%\) số điểm cuối): Giới hạn tối đa (\(N, M \le 2 \times 10^5\)), yêu cầu thuật toán tối ưu \(\mathcal{O}(N \log N)\) hoặc \(\mathcal{O}(N)\) kết hợp tăng tốc nhập xuất trong C++ và Python.

Một chiến thuật rất hiệu quả tại phòng thi OLP là quét ngang toàn bộ các Subtask dễ của cả 4 bài trong 90 phút đầu, đảm bảo tích lũy ngay \(150\text{--}200\) điểm nền trước khi dồn thời gian tối ưu trọn vẹn 1–2 bài thế mạnh (xem kỹ thuật chi tiết tại bài Cách đọc đề và ăn điểm Subtask).

3. Bài toán minh họa OLP: Tối ưu chi phí kết nối mạng bằng Kruskal & DSU

Các bài toán tối ưu hóa hạ tầng mạng trên đồ thị trọng số (như tìm cây khung nhỏ nhất, đường đi ngắn nhất hoặc kiểm tra tính liên thông khi thêm/bớt cạnh) xuất hiện rất đều đặn trong đề thi OLP khối Chuyên tin.

Đề bài tóm tắt: Cho mạng lưới gồm \(N = 5\) máy chủ và \(M = 7\) tuyến cáp hai chiều, mỗi tuyến nối hai máy chủ \((u, v)\) với chi phí lắp đặt \(w\). Hãy tìm tổng chi phí nhỏ nhất để chọn ra đúng \(N - 1\) tuyến cáp sao cho mọi máy chủ đều liên thông với nhau (Cây khung nhỏ nhất — Minimum Spanning Tree).

Để giải bài toán này trong thời gian \(\mathcal{O}(M \log M)\), ta sử dụng thuật toán Kruskal kết hợp cấu trúc Tập hợp rời rạc (DSU / Union-Find). Trước hết, ta sắp xếp \(7\) cạnh theo trọng số \(w\) tăng dần và xét lần lượt từng cạnh như bảng chạy tay dưới đây:

Dưới đây là mã nguồn chuẩn C++17 và Python cài đặt thuật toán Kruskal với DSU có nén đường đi (Path Compression):

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

// Thuật toán Kruskal + DSU tìm Cây khung nhỏ nhất (MST)
struct DSU {
    vector<int> p;
    DSU(int n) : p(n + 1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        p[b] = a;
        return true;
    }
};

long long mst_kruskal(int n, vector<tuple<long long, int, int>> edges) {
    sort(edges.begin(), edges.end());
    DSU dsu(n);
    long long total = 0;
    int taken = 0;
    for (auto& [w, u, v] : edges) {
        if (dsu.unite(u, v)) {
            total += w;
            taken++;
        }
    }
    return taken == n - 1 ? total : -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) {
        vector<tuple<long long, int, int>> edges = {
            {4, 1, 2}, {2, 1, 3}, {1, 2, 3}, {5, 2, 4}, {8, 3, 4}, {3, 4, 5}, {7, 3, 5}
        };
        cout << mst_kruskal(5, edges) << "\n";
        return 0;
    }
    vector<tuple<long long, int, int>> edges(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        edges[i] = {w, u, v};
    }
    cout << mst_kruskal(n, edges) << "\n";
    return 0;
}

import sys

def mst_kruskal(n: int, edges: list[tuple[int, int, int]]) -> int:
    edges.sort()
    parent = list(range(n + 1))

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    total = 0
    taken = 0
    for w, u, v in edges:
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[rv] = ru
            total += w
            taken += 1
    return total if taken == n - 1 else -1

def main() -> None:
    data = sys.stdin.read().split()
    if not data:
        edges = [
            (4, 1, 2), (2, 1, 3), (1, 2, 3), (5, 2, 4), (8, 3, 4), (3, 4, 5), (7, 3, 5)
        ]
        print(mst_kruskal(5, edges))
        return
    n = int(data[0])
    m = int(data[1])
    edges = []
    idx = 2
    for _ in range(m):
        u, v, w = int(data[idx]), int(data[idx + 1]), int(data[idx + 2])
        edges.append((w, u, v))
        idx += 3
    print(mst_kruskal(n, edges))

if __name__ == "__main__":
    main()

Khi thực thi trên đồ thị mẫu \(N = 5, M = 7\), chương trình in ra tổng chi phí nhỏ nhất:

11

4. Lộ trình 16 tuần ôn thi OLP cho sinh viên đại học

Để đạt phong độ cao nhất vào kỳ thi tháng 12 mà vẫn cân bằng việc học trên giảng đường, bạn có thể chia quá trình ôn luyện thành 4 giai đoạn 4 tuần:

1. Tuần 1–4 (Củng cố nền tảng & STL): Rà soát độ phức tạp thuật toán, thành thạo các cấu trúc dữ liệu chuẩn (vector, set, map, priority_queue), mảng cộng dồn, hai con trỏ, tìm kiếm nhị phân trên đáp án và số học modulo.
2. Tuần 5–8 (Quy hoạch động & Tham lam): Luyện tập các mẫu quy hoạch động 1 chiều, cái túi (Knapsack), dãy con tăng dài nhất (LIS) \(\mathcal{O}(N \log N)\), xâu con chung (LCS), quy hoạch động trên lưới và trên cây cơ bản.
3. Tuần 9–12 (Đồ thị & Cấu trúc dữ liệu nâng cao): Làm chủ BFS/DFS, Dijkstra, Bellman-Ford, Floyd-Warshall, DSU, Kruskal/Prim, Sắp xếp Topo, khớp và cầu, cùng Cây Fenwick (BIT) và Segment Tree.
4. Tuần 13–16 (Giải đề OLP các năm & Thi thử bấm giờ): Mỗi tuần giải 2 đề thi thật trong 180 phút không dùng tài liệu bên ngoài; rèn kỹ năng viết bộ sinh test đối chiếu (Stress Testing) để tự bắt lỗi ca biên.

5. Quyền lợi và giá trị của giải thưởng OLP đối với sinh viên

Tham gia và đạt giải tại Olympic Tin học Sinh viên Việt Nam không chỉ là niềm vinh dự cá nhân mà còn mở ra những bước ngoặt lớn cho con đường nghề nghiệp của sinh viên ngành công nghệ:

• Tuyển dụng đặc cách và học bổng doanh nghiệp: Các tập đoàn công nghệ hàng đầu tại Việt Nam và khu vực (như VNG, Viettel, FPT, MoMo, Shopee...) luôn cử đại diện tuyển dụng trực tiếp tại lễ bế mạc OLP. Sinh viên đạt giải Nhất, Nhì các khối Chuyên tin và Siêu cúp thường được mời thẳng vào các vòng phỏng vấn thực tập sinh kỹ thuật cao mà không cần qua vòng sàng lọc hồ sơ CV thông thường.
• Điểm cộng học tập và học bổng khuyến khích tài năng: Hầu hết các trường đại học kỹ thuật (ĐH Bách Khoa Hà Nội, ĐH Công nghệ - ĐHQGHN, ĐH Khoa học Tự nhiên TP.HCM, ĐH Bách Khoa TP.HCM...) đều có chính sách khen thưởng, quy đổi điểm môn học chuyên ngành và trao học bổng tài trợ cho sinh viên mang huy chương OLP về cho trường.
• Bàn đạp tiến vào đấu trường ICPC toàn cầu: Phong độ cá nhân tốt tại OLP giúp bạn tìm kiếm những đồng đội ăn ý nhất để thành lập đội tuyển 3 người dự thi kỳ thi ICPC Quốc tế, hướng tới vòng chung kết châu Á - Thái Bình Dương và tấm vé tham dự World Finals danh giá.

Luyện ngay trên Big-O Coding

Bạn có thể bắt đầu rèn luyện ngay các bài toán đồ thị, cây khung nhỏ nhất và cấu trúc dữ liệu sát chuẩn đề thi Olympic Tin học Sinh viên tại đây:

Nguồn tham khảo

• Wikipedia — Kruskal's algorithm
• CP-Algorithms — Minimum spanning tree, Kruskal's algorithm
• Wikipedia — International Collegiate Programming Contest