Lộ trình Lập trình Thi đấu (Competitive Programming) và Ôn thi Học sinh giỏi Tin học từ cơ bản đến Quốc gia

1. Bản đồ toàn cảnh các kỳ thi Tin học tại Việt Nam và Quốc tế

Khi bắt đầu bước chân vào con đường thuật toán, việc xác định đúng kỳ thi mục tiêu trong 6–12 tháng tới sẽ quyết định bạn nên ưu tiên học mảng kiến thức nào trước. Một học sinh lớp 9 ôn thi vào lớp 10 Chuyên Tin không cần vội vã học Phân rã nặng nhẹ (Heavy-Light Decomposition) hay Luồng cực đại, mà cần làm chủ tuyệt đối Số học, Xâu ký tự, Mảng cộng dồn và Quy hoạch động cơ bản. Ngược lại, một sinh viên năm nhất hướng tới vòng chung kết ICPC Regional cần rèn luyện phản xạ đọc đề tiếng Anh tốc độ cao, khả năng tư duy bài toán xây dựng (Constructive) và phối hợp đồng đội 3 người chung 1 máy tính.

Bảng dưới đây tổng hợp cấu trúc, ngôn ngữ cho phép và ngưỡng kiến thức trọng tâm của 6 kỳ thi lớn nhất trong hệ thống phong trào Tin học:

Hiểu rõ bản đồ này giúp bạn không bị lạc lối giữa biển tài liệu thuật toán trên mạng. Mỗi nấc thang có một yêu cầu kỹ năng cụ thể, và việc nhảy cóc giai đoạn hầu như luôn dẫn tới cảm giác quá tải hoặc hổng lỗ kiến thức cơ bản ở các ca biên nhỏ.

2. Lộ trình 4 tầng kiến thức từ người mới bắt đầu đến Đội tuyển Quốc gia

Để tránh tình trạng học nhảy cóc dẫn đến hổng kiến thức nền tảng, lộ trình chuẩn tại Big-O Coding chia quá trình rèn luyện thành 4 chặng tuần tự, xây dựng nền tảng vững chắc từ cú pháp ngôn ngữ cho tới các thuật toán chuyên sâu nhất.

Tầng 1: Nền tảng Ngôn ngữ, Độ phức tạp và Toán Số học (Tháng 1 – Tháng 3)

Ở chặng đầu tiên, mục tiêu của bạn là biến ngôn ngữ lập trình thành công cụ phản xạ tự nhiên và không bao giờ mất điểm ở các bài toán kỹ thuật cơ sở:

• Làm chủ C++17 STL hoặc Python 3: Thành thạo các cấu trúc dữ liệu cơ bản như std::vector, std::string, std::pair, các hàm sắp xếp std::sort, tìm kiếm nhị phân std::lower_bound, cấu trúc tập hợp std::set và bảng băm (Hash Table). Nắm vững kỹ thuật tăng tốc nhập xuất trong C++ và Python để đọc một triệu số nguyên trong thời gian rất ngắn dưới \(0.15\text{ giây}\).
• Số học cơ sở (Elementary Number Theory): Thuật toán Euclid tìm ước chung lớn nhất \(\gcd(a, b)\) trong thời gian logarit \(\mathcal{O}(\log(\min(a,b)))\), kỹ thuật phân tích thừa số nguyên tố trong \(\mathcal{O}(\sqrt{N})\), Sàng nguyên tố Eratosthenes \(\mathcal{O}(N \log \log N)\) và các phép toán đồng dư mô-đulo \((a + b) \bmod M\), \((a \times b) \bmod M\).
• Kỹ thuật xử lý mảng tuyến tính: Mảng cộng dồn (Prefix Sum) một chiều và hai chiều, mảng hiệu (Difference Array) cho phép cập nhật cộng dồn trên đoạn trong \(\mathcal{O}(1)\), và kỹ thuật Hai con trỏ (Two Pointers) kết hợp Cửa sổ trượt (Sliding Window).

Tầng 2: Các Khuôn mẫu Thiết kế Thuật toán Cốt lõi (Tháng 4 – Tháng 6)

Sau khi vững Tầng 1, bạn đã đủ sức giải trọn vẹn hai bài đầu trong đề thi Chuyên Tin và Bảng B Tin học trẻ. Tầng 2 đưa bạn sang các kỹ thuật giảm bậc độ phức tạp từ \(\mathcal{O}(N^2)\) xuống \(\mathcal{O}(N \log N)\):

• Tìm kiếm nhị phân trên tập kết quả (Binary Search on Answer): Khi hàm kiểm tra tính khả thi check(X) có tính đơn điệu (nếu \(X\) thỏa mãn thì mọi \(X' \gt X\) cũng thỏa mãn), ta chặt nhị phân trực tiếp giá trị đáp án tối ưu thay vì duyệt tuyến tính từng trường hợp.
• Chiến lược Tham lam (Greedy) & Sắp xếp theo sự kiện: Bài toán chọn đoạn không giao nhau, lập lịch công việc giảm độ trễ, ghép cặp tối ưu kết hợp với Hàng đợi ưu tiên (std::priority_queue hoặc cấu trúc Heap).
• Đệ quy Quay lui (Backtracking) & Nhánh cận: Kỹ thuật sinh tập con, chỉnh hợp, hoán vị và cắt tỉa sớm các nhánh không thể dẫn tới nghiệm tốt hơn kỷ lục hiện tại — vũ khí cực mạnh để ăn điểm Subtask 1 và Subtask 2 của các bài khó trong đề thi.
• Quy hoạch động 1 chiều và 2 chiều cổ điển: Dãy con tăng dài nhất (LIS trong \(\mathcal{O}(N \log N)\)), Bài toán Cái túi (Knapsack 0/1 và Unbounded), Xâu con chung dài nhất (LCS) và Khoảng cách biến đổi xâu (Edit Distance).

Tầng 3: Lý thuyết Đồ thị và Cấu trúc Dữ liệu Truy vấn Đoạn (Tháng 7 – Tháng 10)

Đây là ranh giới phân loại thí sinh đạt giải Nhất/Nhì cấp Tỉnh, huy chương Olympic 30/4 và tiến vào đội tuyển dự thi Quốc gia VOI:

• Thuật toán Đồ thị chuẩn: Duyệt theo chiều rộng (BFS) trên lưới và đồ thị không trọng số, Duyệt theo chiều sâu (DFS), Sắp xếp Tô-pô (Topological Sort) trên đồ thị có hướng không chu trình (DAG), Đường đi ngắn nhất Dijkstra \(\mathcal{O}((V+E)\log V)\), thuật toán Bellman-Ford và Floyd-Warshall.
• Tập hợp rời rạc (Disjoint Set Union — DSU) & Cây khung nhỏ nhất (MST): Kỹ thuật gộp tập hợp với nén đường đi (Path Compression) và gộp theo hạng trong \(\mathcal{O}(\alpha(N))\), thuật toán Kruskal và thuật toán Prim.
• Cấu trúc dữ liệu trên Cây và Đoạn: Cây chỉ số nhị phân (Fenwick Tree / BIT), Cây phân đoạn (Segment Tree) cơ bản và cập nhật khoảng với kỹ thuật Cập nhật lười (Lazy Propagation), bài toán Tổ tiên chung gần nhất (LCA bằng Binary Lifting), Khớp và Cầu (Articulation Points & Bridges) và Thành phần liên thông mạnh (Tarjan SCC).

Tầng 4: Tối ưu hóa Nâng cao cho VOI và ICPC Regional (Tháng 11 trở đi)

Ở tầng cao nhất, bài toán đòi hỏi sự kết hợp nhuần nhuyễn giữa toán học rời rạc, cấu trúc dữ liệu bậc cao và kỹ thuật tối ưu hóa trạng thái:

• Các hệ quy hoạch động chuyên sâu: Quy hoạch động trên cây (Tree DP & Rerooting), Quy hoạch động trạng thái bit (Bitmask DP \(\mathcal{O}(N \cdot 2^N)\) và SOS DP), Quy hoạch động chữ số (Digit DP), tối ưu bao lồi (Convex Hull Trick / Li Chao Tree) và tối ưu Chia để trị (Divide and Conquer Optimization).
• Toán học Tổ hợp & Số học nâng cao: Kỹ thuật nghịch đảo mô-đulo bằng định lý nhỏ Fermat, Nguyên lý Bao hàm - Loại trừ (Inclusion-Exclusion), Nhân ma trận lũy thừa nhanh \(\mathcal{O}(K^3 \log N)\), Phi hàm Euler và Định lý Thặng dư Trung Hoa (CRT).
• Cấu trúc Cây nâng cao, Luồng và Hình học: Kỹ thuật Gộp nhỏ vào lớn (DSU on Tree / Sack), Phân rã nặng nhẹ (Heavy-Light Decomposition — HLD), Luồng cực đại - Lát cắt cực tiểu (thuật toán Dinic), Cặp ghép cực đại trên đồ thị hai phía và Hình học tính toán số nguyên (Tích có hướng, Công thức diện tích Shoelace, Bao lồi Monotone Chain).

3. Minh họa tư duy subtask: từ vét cạn O(N^2) đến hai con trỏ O(N)

Trong mọi kỳ thi HSG tại Việt Nam, đề bài luôn chia điểm theo các Subtask (Giới hạn con). Hiểu được mối liên hệ giữa các Subtask giúp bạn không bao giờ rơi vào cảnh trắng tay khi gặp bài lạ. Hãy cùng phân tích một bài toán điển hình sau đây:

Đề bài: Cho mảng gồm \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) và một ngưỡng tổng \(S\). Hãy tìm độ dài của đoạn con liên tiếp ngắn nhất có tổng các phần tử lớn hơn hoặc bằng \(S\) (nếu không tồn tại đoạn nào, in ra số 0).

• Subtask 1 (\(40\%\) số điểm): Giới hạn nhỏ \(N \le 2{,}000\), các phần tử \(A_i \le 10^5\).
• Subtask 2 (\(60\%\) số điểm): Giới hạn lớn \(N \le 2 \times 10^5\), các phần tử \(A_i \le 10^9\) và ngưỡng \(S \le 10^{14}\).

Phân tích chiến thuật lấy trọn 100% điểm

Ở Subtask 1, vì \(N \le 2{,}000\), số lượng đoạn con liên tiếp chỉ là \(\frac{N(N+1)}{2} \approx 2 \times 10^6\). Bạn hoàn toàn có thể viết hai vòng lặp lồng nhau duyệt mọi cặp chỉ số đầu cuối \((l, r)\) trong thời gian \(\mathcal{O}(N^2)\) để chắc chắn bỏ túi \(40\%\) số điểm đầu tiên chỉ sau 5 phút gõ code.

Để chinh phục Subtask 2 trong thời gian tuyến tính \(\mathcal{O}(N)\), ta cần nhận ra một tính chất quan trọng: vì mọi phần tử \(A_i\) đều là số nguyên dương nghiêm ngặt (\(A_i \gt 0\)), khi mở rộng biên phải right sang bên phải, tổng các phần tử trong đoạn cur chỉ có thể tăng lên. Ngay khi tổng cur đạt hoặc vượt ngưỡng \(S\), việc tiếp tục mở rộng biên phải về sau sẽ chỉ làm đoạn con dài thêm mà không thể tối ưu độ dài hơn. Do đó, ta có thể thu hẹp biên trái left dần dần sang phải để tìm ra độ dài ngắn nhất thỏa mãn trước khi tiếp tục dịch biên phải. Vì cả hai con trỏ left và right đều chỉ tiến về phía trước theo một chiều duy nhất và không bao giờ quay lui, mỗi phần tử được xét vào và đẩy ra khỏi đoạn đúng một lần, mang lại tổng thời gian chạy tối ưu tuyệt đối \(\mathcal{O}(N)\).

Chạy tay từng bước trên mảng 2, 3, 1, 2, 4, 3 với ngưỡng S = 7

Bảng dưới đây theo dõi trạng thái của hai con trỏ left và right cùng tổng tích lũy cur tại từng bước lặp:

Kết quả cuối cùng trả về độ dài ngắn nhất là 2 (ứng với đoạn con [4, 3]). Dưới đây là mã nguồn cài đặt chuẩn bằng C++17 và Python 3:

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

// Tìm độ dài đoạn con ngắn nhất có tổng >= S (Subtask 1: O(N^2), Subtask 2: O(N))
int min_subarray_len(const vector<long long>& a, long long s) {
    int n = (int)a.size();
    int best = n + 1, left = 0;
    long long cur = 0;
    for (int right = 0; right < n; ++right) {
        cur += a[right];
        while (cur >= s) {
            best = min(best, right - left + 1);
            cur -= a[left++];
        }
    }
    return best <= n ? best : 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long s;
    if (!(cin >> n >> s)) {
        vector<long long> a = {2, 3, 1, 2, 4, 3};
        cout << min_subarray_len(a, 7) << "\n";
        return 0;
    }
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    cout << min_subarray_len(a, s) << "\n";
    return 0;
}

import sys

def min_subarray_len(a: list[int], s: int) -> int:
    n = len(a)
    best = n + 1
    left = 0
    cur = 0
    for right, val in enumerate(a):
        cur += val
        while cur >= s:
            if right - left + 1 < best:
                best = right - left + 1
            cur -= a[left]
            left += 1
    return best if best <= n else 0

def main() -> None:
    data = sys.stdin.read().split()
    if not data:
        print(min_subarray_len([2, 3, 1, 2, 4, 3], 7))
        return
    n = int(data[0])
    s = int(data[1])
    a = [int(x) for x in data[2:2 + n]]
    print(min_subarray_len(a, s))

if __name__ == "__main__":
    main()

4. Phương pháp rèn luyện hàng ngày và chiến thuật thi đấu thực chiến

Học thuật toán không chỉ là đọc lý thuyết trong sách giáo khoa, mà là quá trình rèn luyện phản xạ phát hiện mô hình bài toán dưới áp lực thời gian. Dưới đây là ba thói quen quyết định sự bứt phá của các thí sinh giỏi:

Thói quen 1: Quy trình giải một bài toán mới (Upsolving)

Khi đối diện với một bài tập chưa từng gặp, bạn nên tuân thủ kỷ luật 3 bước sau:

1. Dành 30 đến 45 phút đầu suy nghĩ độc lập trên giấy nháp: Vẽ các ví dụ nhỏ, tìm tính chất đặc biệt, tính chất đơn điệu hoặc bất biến. Tuyệt đối không mở lời giải (Editorial) quá sớm vì sẽ làm thui chột khả năng tự liên tưởng.
2. Nếu chưa nghĩ ra thuật toán tối ưu, hãy viết code vét cạn lấy điểm Subtask 1 trước: Việc viết code vét cạn giúp bạn hiểu sâu sắc bản chất bài toán và có sẵn một bộ chương trình chuẩn để đối chiếu sau này.
3. Đọc lời giải và tự gõ lại toàn bộ từ con số 0: Khi đọc Editorial, chỉ đọc phần gợi ý ý tưởng cốt lõi, gấp tài liệu lại rồi tự tay cài đặt toàn bộ mã nguồn. Nếu chỉ đọc lướt qua code mẫu của người khác và gật gù thì ngày hôm sau bạn vẫn sẽ không tự cài đặt lại được.

Thói quen 2: Lập sổ tay ghi chép lỗi sai (Bug Diary)

Hơn \(80\%\) số điểm bị mất trong các kỳ thi không phải vì thí sinh không nghĩ ra thuật toán, mà vì các lỗi sơ đẳng lặp đi lặp lại:

• Quên ép kiểu số nguyên lớn: biểu thức 1LL * a * b trong C++ khi nhân hai số int vượt quá giới hạn hai tỷ.
• Khai báo kích thước mảng: khai báo thiếu phần tử cho mảng một chiều hoặc dùng quá nhiều bộ nhớ tĩnh gây lỗi bộ nhớ (Memory Limit Exceeded).
• Ca biên đặc biệt: trường hợp mảng chỉ có đúng một phần tử \(N = 1\), đồ thị không liên thông, cây suy biến thành một đường thẳng, hoặc mọi phần tử trong mảng đều bằng nhau.

Hãy ghi chép lại mọi lỗi bạn từng mắc vào một cuốn sổ nhỏ và đọc lại cuốn sổ đó 15 phút trước mỗi buổi thi hoặc buổi luyện tập quan trọng.

Thói quen 3: Kỷ luật phân bổ thời gian trong phòng thi

Trong một kỳ thi kéo dài 180 phút với 3 đến 4 bài, việc phân bổ thời gian là yếu tố sống còn:

• 20 phút đầu: Đọc toàn bộ các bài trong đề, gạch chân các giới hạn của từng Subtask và đánh giá sơ bộ mức độ khả thi của từng bài ra giấy nháp.
• 60 phút tiếp theo: Giải quyết dứt điểm bài dễ nhất để lấy trọn vẹn điểm số nền tảng, tạo tâm lý tự tin cho cả buổi thi.
• 70 phút giữa giờ: Khai thác tối đa các Subtask có thể làm được ở các bài còn lại. Đừng bao giờ bỏ trắng một bài nào khi bạn hoàn toàn có thể viết một hàm quay lui hoặc quy hoạch động đơn giản trong 15 phút để lấy từ một đến hai điểm quý giá.
• 30 phút cuối giờ: Dừng việc suy nghĩ các thuật toán mới. Dành toàn bộ thời gian để kiểm tra lại tên tệp nhập xuất (freopen hoặc luồng chuẩn), kiểm tra giới hạn mảng toàn cục và sử dụng kỹ thuật sinh test đối chiếu (Stress Testing) để đảm bảo code không bị lỗi ở các ca biên nhỏ.

Luyện ngay trên Big-O Coding

Để bắt đầu hành trình chinh phục các kỳ thi Học sinh giỏi và Olympic Tin học một cách bài bản, bạn hãy thực hành ngay 3 bài toán tiêu biểu đại diện cho kỹ thuật Cửa sổ trượt, Tìm kiếm nhị phân và Cây khung nhỏ nhất trong lộ trình Olympic 250 dưới đây:

Nguồn tham khảo

• USACO Guide — Introduction to Competitive Programming
• CP-Algorithms — Algorithms and Data Structures for CP
• Wikipedia — Competitive Programming Overview