Cách đọc đề và ăn điểm subtask trong thi HSG Tin: từ lời giải vét cạn đến lời giải đầy đủ

Các kỳ thi học sinh giỏi Tin học cấp tỉnh, Tin học trẻ, học sinh giỏi quốc gia (VOI) và phần lớn đề thi vào lớp 10 chuyên Tin đều chấm theo subtask. Mỗi bài được chia thành nhiều nhóm test, mỗi nhóm có ràng buộc riêng (ví dụ \(N \le 100\), \(N \le 5000\), \(N \le 2 \cdot 10^5\)) và một phần điểm riêng. Bạn qua hết test trong nhóm nào thì nhận điểm của nhóm đó.

Cách chấm này thưởng cho người biết đọc đề và chia thời gian. Một thí sinh làm chắc subtask đầu của cả bốn bài thường có điểm cao hơn người làm trọn một bài rồi bỏ trắng ba bài còn lại. Bài viết này đi qua các bước cốt lõi: đọc ràng buộc để biết thuật toán cần đạt độ phức tạp nào, chia thời gian theo subtask, kỹ thuật phân nhánh code an toàn và một ví dụ cụ thể đi từ lời giải vét cạn lên lời giải đầy đủ.

1. Đọc ràng buộc để suy ra độ phức tạp cần đạt

Phần quan trọng nhất của đề không phải câu chuyện dẫn dắt mà là dòng ràng buộc ở cuối. Máy chấm phổ biến xử lý được khoảng \(10^8\) phép tính đơn giản mỗi giây trong C++ (con số ước lượng, phụ thuộc máy chấm và loại phép tính). Từ đó có bảng tra nhanh sau:

Với Python, hãy chia con số trên cho khoảng 10 đến 50 lần, tùy cách viết. Đây là lý do nhiều đội tuyển dùng C++ cho subtask cuối, còn Python vẫn đủ cho các subtask nhỏ.

Khi đọc đề, hãy đánh dấu ngay ba thứ bên lề giấy nháp: giới hạn của từng subtask, phần điểm của từng subtask, và các điều kiện đặc biệt (mảng đã sắp xếp, mọi phần tử bằng nhau, đồ thị là đường thẳng, giá trị chỉ gồm 0 và 1). Điều kiện đặc biệt thường là gợi ý cho một lời giải đơn giản hơn nhiều so với lời giải đầy đủ.

2. Chia thời gian theo subtask và kỹ thuật phân nhánh code

Một kỳ thi 180 phút với 3–4 bài có thể chia theo ba vòng:

1. Vòng đọc (15–20 phút): Đọc hết mọi bài. Với mỗi bài, viết ra subtask nào bạn chắc chắn làm được và mất khoảng bao lâu.
2. Vòng lấy điểm chắc (60–80 phút): Làm subtask dễ của mọi bài. Lời giải vét cạn thường chỉ 15–20 dòng; viết cẩn thận, chạy với ví dụ trong đề rồi nộp hoặc lưu lại.
3. Vòng nâng điểm (thời gian còn lại): Chọn bài có khoảng cách nhỏ nhất giữa lời giải hiện có và subtask tiếp theo. Ưu tiên bài mà bạn đã thấy hướng đi, không phải bài nhiều điểm nhất.

Một lợi ích thường bị bỏ qua: lời giải vét cạn ở vòng 2 không chỉ mang lại điểm. Nó còn là bản đối chiếu đáng tin để kiểm tra lời giải nhanh ở vòng 3. Chỉ cần sinh dữ liệu nhỏ ngẫu nhiên và so kết quả hai chương trình, bạn sẽ bắt được phần lớn lỗi trước khi nộp. Cách làm này được trình bày kỹ trong bài Kỹ thuật sinh test và đối chiếu code.

Kỹ thuật phân nhánh code an toàn trong cùng một tệp

Một sai lầm rất phổ biến là khi viết lời giải nhanh, thí sinh xóa luôn hàm vét cạn cũ. Nếu lời giải nhanh bị lỗi ở một ca biên nào đó, bạn sẽ mất trắng toàn bộ điểm của cả bài!

Cách làm chuẩn trong phòng thi là giữ cả hai hàm trong cùng một tệp nguồn, rồi phân nhánh dựa trên giá trị \(N\) của đầu vào:

if (n <= 2000) {
    solve_subtask1();
} else {
    solve_full();
}

Cách cài đặt này hoạt động như một chiếc phao cứu sinh tự động: nếu hàm solve_full() không may bị sai test ẩn ở giới hạn lớn, chương trình của bạn vẫn đảm bảo vượt qua trọn vẹn 100% các bộ test nhỏ của Subtask 1 và giữ vững 40% số điểm cơ sở.

3. Ví dụ: đếm cặp có tổng nằm trong đoạn [L, R]

Đề bài: Cho mảng \(A\) gồm \(N\) số nguyên và hai số \(L, R\). Đếm số cặp chỉ số \((i, j)\) với \(i \lt j\) sao cho \(L \le A_i + A_j \le R\).

• Subtask 1 (40% điểm): \(N \le 2000\).
• Subtask 2 (60% điểm): \(N \le 2 \cdot 10^5\).

Subtask 1: vét cạn mọi cặp

Với \(N \le 2000\), số cặp là khoảng \(2 \cdot 10^6\), chạy hai vòng lặp lồng nhau hoàn toàn thoải mái. Lời giải này viết trong 3 phút và gần như không thể sai.

Subtask 2: đổi bài toán rồi dùng hai con trỏ

Với \(N = 2 \cdot 10^5\), số cặp là khoảng \(2 \cdot 10^{10}\), quá nhiều để duyệt. Ta cần hai quan sát:

1. Thứ tự phần tử không ảnh hưởng tới số cặp. Số cặp có tổng trong đoạn chỉ phụ thuộc vào tập giá trị, nên ta được phép sắp xếp mảng.
2. Đổi "trong đoạn" thành hiệu của hai lần "nhỏ hơn hoặc bằng". Gọi \(f(x)\) là số cặp có tổng \(\le x\). Khi đó đáp án là \(f(R) - f(L - 1)\).

Hàm \(f(x)\) trên mảng đã sắp xếp tính được bằng hai con trỏ: con trỏ trái ở đầu, con trỏ phải ở cuối. Nếu \(B_{\text{trái}} + B_{\text{phải}} \le x\) thì mọi phần tử từ trái+1 đến phải đều ghép được với \(B_{\text{trái}}\), cộng thêm (phải − trái) cặp rồi dịch con trỏ trái. Ngược lại, dịch con trỏ phải sang trái. Mỗi bước dịch một con trỏ nên \(f(x)\) chạy trong \(\mathcal{O}(N)\), cả bài là \(\mathcal{O}(N \log N)\) do bước sắp xếp.

Chạy tay với \(A = [5, 1, 2, 7, 4, 3]\), \(L = 6\), \(R = 9\). Sau khi sắp xếp, \(B = [1, 2, 3, 4, 5, 7]\). Tính \(f(9)\):

Hai con trỏ gặp nhau, \(f(9) = 12\). Làm tương tự với \(x = L - 1 = 5\) được \(f(5) = 4\) (các cặp 1+2, 1+3, 1+4, 2+3). Đáp án là \(12 - 4 = 8\).

Kiểm tra lại bằng tay: tổng cộng có 15 cặp; 3 cặp có tổng lớn hơn 9 (3+7, 4+7, 5+7) và 4 cặp có tổng nhỏ hơn 6, còn lại \(15 - 3 - 4 = 8\) cặp. Kết quả khớp.

Chương trình dưới đây chứa cả hai hàm và in kết quả của chúng cạnh nhau để bạn thấy chúng luôn bằng nhau:

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

// Đếm cặp (i < j) sao cho L <= a[i] + a[j] <= R bằng cả Subtask 1 O(N^2) và Subtask Full O(N log N)
long long solve_subtask1(const vector<long long>& a, long long l, long long r) {
    int n = (int)a.size();
    long long cnt = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            long long s = a[i] + a[j];
            if (l <= s && s <= r) cnt++;
        }
    }
    return cnt;
}

long long count_le(const vector<long long>& sorted_a, long long bound) {
    int left = 0, right = (int)sorted_a.size() - 1;
    long long cnt = 0;
    while (left < right) {
        if (sorted_a[left] + sorted_a[right] <= bound) {
            cnt += (right - left);
            left++;
        } else {
            right--;
        }
    }
    return cnt;
}

long long solve_full(vector<long long> a, long long l, long long r) {
    sort(a.begin(), a.end());
    return count_le(a, r) - count_le(a, l - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long l, r;
    if (!(cin >> n >> l >> r)) {
        vector<long long> a = {5, 1, 2, 7, 4, 3};
        long long c1 = solve_subtask1(a, 6, 9);
        long long c2 = solve_full(a, 6, 9);
        cout << c1 << "=" << c2 << "\n";
        return 0;
    }
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    cout << solve_subtask1(a, l, r) << "=" << solve_full(a, l, r) << "\n";
    return 0;
}

import sys

def solve_subtask1(a: list[int], l: int, r: int) -> int:
    n = len(a)
    cnt = 0
    for i in range(n):
        for j in range(i + 1, n):
            if l <= a[i] + a[j] <= r:
                cnt += 1
    return cnt

def count_le(sorted_a: list[int], bound: int) -> int:
    left = 0
    right = len(sorted_a) - 1
    cnt = 0
    while left < right:
        if sorted_a[left] + sorted_a[right] <= bound:
            cnt += right - left
            left += 1
        else:
            right -= 1
    return cnt

def solve_full(a: list[int], l: int, r: int) -> int:
    b = sorted(a)
    return count_le(b, r) - count_le(b, l - 1)

def main() -> None:
    data = sys.stdin.read().split()
    if not data:
        a = [5, 1, 2, 7, 4, 3]
        print(f"{solve_subtask1(a, 6, 9)}={solve_full(a, 6, 9)}")
        return
    n = int(data[0])
    l = int(data[1])
    r = int(data[2])
    a = [int(x) for x in data[3:3 + n]]
    print(f"{solve_subtask1(a, l, r)}={solve_full(a, l, r)}")

if __name__ == "__main__":
    main()

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

8=8

Trong bài thi thật, bạn sẽ chỉ in một số. Nhưng khi luyện tập, thói quen in cả hai kết quả như trên giúp phát hiện lỗi ngay khi chạy thử, ví dụ quên trường hợp \(L - 1\) âm hoặc dùng int khi số cặp vượt \(2^{31} - 1\) (với \(N = 2 \cdot 10^5\), số cặp có thể lên tới khoảng \(2 \cdot 10^{10}\), phải dùng long long).

4. Nhận diện các Subtask có ràng buộc đặc biệt

Trong rất nhiều đề thi HSG Quốc gia và Olympic, ban ra đề thường thiết kế từ 1 đến 2 Subtask (thường chiếm 20% đến 30% điểm) với những ràng buộc hình học hoặc cấu trúc rất đặc thù. Nhận diện sớm các dấu hiệu này giúp bạn viết lời giải riêng chỉ trong 10 đến 15 dòng code:

• Đồ thị là một đường thẳng hoặc chu trình: Khi đề bài cho đồ thị tổng quát nhưng có một Subtask ghi "mỗi đỉnh có bậc không quá 2", đồ thị thực chất suy biến thành một mảng một chiều hoặc chu trình đơn. Bạn có thể giải bằng Quy hoạch động trên dãy số hoặc Mảng cộng dồn thay vì phải dùng thuật toán đồ thị phức tạp.
• Trọng số chỉ nhận giá trị 0 hoặc 1: Thay vì dùng thuật toán Dijkstra với độ phức tạp \(\mathcal{O}((V+E)\log V)\), bạn có thể dùng hàng đợi hai đầu std::deque (kỹ thuật 0-1 BFS) để tìm đường đi ngắn nhất trong thời gian tuyến tính \(\mathcal{O}(V + E)\).
• Các giá trị trong mảng đều bằng nhau hoặc mảng đã sắp xếp sẵn: Điều này loại bỏ hoàn toàn các bước tìm kiếm phức tạp; đáp án thường suy ra ngay từ một công thức toán học tổ hợp hoặc nhân chia cơ bản.
• Số lượng phần tử được chọn rất nhỏ (\(K = 1\) hoặc \(K = 2\)): Thay vì phải cài đặt thuật toán quy hoạch động cái túi đầy đủ, bạn chỉ cần một hoặc hai vòng lặp duyệt tay tìm giá trị lớn nhất.

5. Những lỗi khiến mất điểm subtask dễ

• Bỏ subtask nhỏ vì "chắc làm được bài đầy đủ": Nếu cuối giờ lời giải đầy đủ vẫn sai hoặc dính lỗi thời gian thực thi, bạn mất trắng cả bài. Hãy luôn gõ bản vét cạn trước.
• Quên đọc định dạng đầu vào của từng subtask: Một số đề cho subtask có nhiều bộ test trong một tệp, hoặc có giá trị âm chỉ xuất hiện ở subtask cuối.
• Không thử ca biên: Hãy thử \(N = 1\) (không có cặp nào), mọi phần tử bằng nhau, \(L \gt R\), và giá trị lớn nhất để kiểm tra tràn số.
• Đọc dữ liệu chậm ở subtask lớn: Với \(2 \cdot 10^5\) số, đọc từng dòng bằng input() trong Python có thể tốn đáng kể thời gian. Xem thêm cách tăng tốc nhập xuất trong C++ và Python.
• Xung đột biến toàn cục giữa các hàm Subtask: Khi để chung solve_subtask1() và solve_full() trong cùng tệp, hãy chú ý reset toàn bộ mảng đếm, mảng đánh dấu và biến tổng trước khi gọi từng hàm để tránh lỗi dữ liệu bị cộng dồn chéo giữa các lần chạy.

Nếu bạn muốn có một kế hoạch ôn tập tổng thể cho các kỳ thi chấm subtask, bài Lộ trình lập trình thi đấu và HSG Tin học chia chặng theo từng mốc kiến thức. Còn kỹ thuật tìm kiếm trên mảng đã sắp xếp được giải thích chi tiết trong bài Tìm kiếm nhị phân.

Luyện ngay trên Big-O Coding

Ba bài dưới đây có cấu trúc subtask rõ ràng, rất hợp để luyện thói quen viết lời giải vét cạn trước rồi tối ưu bằng sắp xếp, hai con trỏ và tìm kiếm nhị phân:

Nguồn tham khảo

• USACO Guide — Contest Strategy
• USACO Guide — Two Pointers
• CP-Algorithms — Binary search