Cách luyện Codeforces cho người mới: chọn kỳ thi, chọn bài theo độ khó và đọc lời giải đúng cách

Codeforces là trang thi lập trình trực tuyến do một nhóm lập trình viên ở Saratov (Nga) lập ra năm 2009. Người dùng trên toàn thế giới vào đây để thi các vòng (round) kéo dài từ 2 đến 2,5 giờ, rồi nhận điểm xếp hạng (rating) tăng hoặc giảm theo kết quả. Với học sinh ôn thi học sinh giỏi Tin và sinh viên chuẩn bị kỳ thi ICPC, đây là nơi luyện phản xạ thi đấu tốt nhất vì đề mới liên tục và có bảng xếp hạng thật.

Khó khăn của người mới không nằm ở việc thiếu bài để làm, mà ở chỗ có quá nhiều bài và không biết bắt đầu từ đâu. Bài viết này giải thích cách hệ thống Codeforces vận hành, cách chọn bài vừa sức, cách luyện dạng bài xây dựng (constructive) rất đặc trưng của trang, và thói quen cần giữ sau mỗi kỳ thi.

1. Hiểu hệ thống kỳ thi và màu xếp hạng

Mỗi vòng thi trên Codeforces được dán nhãn theo nhóm người chơi mà nó nhắm tới. Bảng dưới đây tóm tắt các loại vòng hay gặp:

Rating ban đầu của mọi tài khoản mới được hiển thị bằng màu xám (Newbie, dưới 1200). Các mốc màu tiếp theo là xanh lá (Pupil, 1200–1399), xanh lơ (Specialist, 1400–1599), xanh dương (Expert, 1600–1899), tím (Candidate Master, 1900–2099), cam (Master và International Master, 2100–2399) và đỏ (Grandmaster trở lên, từ 2400).

Với người mới, mục tiêu thực tế cho 3–6 tháng đầu là lên được xanh lơ (Specialist). Ở mốc này, bạn đã giải ổn định bài A, B và thỉnh thoảng bài C của vòng Div. 2, tương đương mức làm tốt đề thi chuyên Tin lớp 10 hoặc đề học sinh giỏi cấp tỉnh.

2. Chọn bài luyện theo độ khó thay vì theo thứ tự

Trong mục Problemset, mỗi bài có một con số độ khó (ví dụ 800, 1200, 1600) và các nhãn chủ đề như greedy, math, constructive algorithms, binary search. Con số này cho biết người có rating khoảng bằng số đó có xác suất giải được bài vào khoảng một nửa.

Quy tắc đơn giản để chọn bài là luyện ở mức rating hiện tại cộng thêm 100 đến 300. Nếu bạn đang 1000, hãy làm chủ yếu bài 1100–1300. Bài quá dễ (thấp hơn rating của bạn) chỉ giúp tăng tốc gõ, không giúp bạn nghĩ ra ý tưởng mới. Bài quá khó (cao hơn 500 trở lên) thường khiến bạn ngồi cả buổi mà không học thêm được gì, vì lời giải dùng kiến thức bạn chưa có.

Một buổi luyện 90 phút có thể chia như sau:

1. 15 phút: giải nhanh 1 bài thấp hơn rating hiện tại để khởi động, tập gõ không lỗi ngay lần nộp đầu.
2. 60 phút: dồn sức cho 1–2 bài ở mức rating cộng 200. Tự nghĩ ít nhất 30–40 phút trước khi xem gợi ý.
3. 15 phút: đọc lời giải chính thức (editorial) của bài chưa làm được, rồi tự gõ lại từ đầu mà không nhìn code mẫu.

Ở bước 3, chỉ đọc lời giải là chưa đủ. Bạn cần ghi lại vào sổ tay một câu ngắn: "Mấu chốt của bài này là gì, và lần sau gặp dấu hiệu nào thì nghĩ tới nó?". Sau vài tháng, cuốn sổ này giá trị hơn mọi danh sách bài có sẵn.

3. Luyện dạng bài xây dựng: ví dụ dãy hoán vị có đúng K đỉnh

Dạng bài mà người mới hay gặp khó trên Codeforces là bài xây dựng (constructive): đề yêu cầu bạn tạo ra một dãy, một xâu hay một đồ thị thỏa điều kiện cho trước, chứ không yêu cầu tính một con số. Dạng này hầu như không cần cấu trúc dữ liệu phức tạp, chỉ cần quan sát đúng.

Đề bài: Cho hai số \(N\) và \(K\). Hãy in ra một hoán vị của các số \(1, 2, \dots, N\) sao cho có đúng \(K\) vị trí là đỉnh. Vị trí \(i\) (với \(2 \le i \le N - 1\)) là đỉnh nếu \(p_{i-1} \lt p_i\) và \(p_i \gt p_{i+1}\). Nếu không tồn tại, in \(-1\).

Bước 1: Tìm giới hạn. Hai đỉnh không thể đứng cạnh nhau (vì nếu \(p_i \gt p_{i+1}\) thì \(i+1\) không thể là đỉnh). Vị trí đầu và cuối cũng không thể là đỉnh. Vì vậy, các đỉnh nằm trong khoảng từ vị trí 2 đến \(N-1\) và cách nhau ít nhất một ô, nên số đỉnh tối đa là \(\lfloor (N-1)/2 \rfloor\). Nếu \(K\) lớn hơn số này, in \(-1\).

Bước 2: Dựng mẫu. Đặt \(K\) số lớn nhất \(N, N-1, \dots, N-K+1\) vào các vị trí 2, 4, 6, ..., \(2K\). Các ô còn lại điền lần lượt \(1, 2, 3, \dots\) theo thứ tự tăng dần từ trái sang phải.

Chạy tay với \(N = 7, K = 2\) (giới hạn \(\lfloor 6/2 \rfloor = 3 \ge 2\), nên có đáp án):

Bước 3: Kiểm tra vì sao mẫu luôn đúng. Mỗi số lớn đặt ở vị trí chẵn đều lớn hơn mọi số nhỏ điền xung quanh, nên chắc chắn là đỉnh. Các số nhỏ được điền tăng dần, nên phần đuôi sau đỉnh cuối cùng là một dãy tăng và không sinh thêm đỉnh nào. Tổng số đỉnh là đúng \(K\).

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

// Bài toán Constructive điển hình trên Codeforces: Dựng hoán vị 1..N có đúng K đỉnh cục bộ
vector<int> build_peaks_permutation(int n, int k) {
    if (k > (n - 1) / 2) return {};
    vector<int> res(n, 0);
    int val = n;
    for (int i = 0; i < k; ++i) {
        res[2 * i + 1] = val--;
    }
    int cur = 1;
    for (int i = 0; i < n; ++i) {
        if (res[i] == 0) res[i] = cur++;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    if (!(cin >> n >> k)) {
        n = 7; k = 2;
    }
    auto p = build_peaks_permutation(n, k);
    if (p.empty()) {
        cout << -1 << "\n";
        return 0;
    }
    for (int i = 0; i < n; ++i) {
        cout << p[i] << (i + 1 == n ? "" : " ");
    }
    cout << "\n";
    return 0;
}

import sys

def build_peaks_permutation(n: int, k: int) -> list[int]:
    if k > (n - 1) // 2:
        return []
    res = [0] * n
    val = n
    for i in range(k):
        res[2 * i + 1] = val
        val -= 1
    cur = 1
    for i in range(n):
        if res[i] == 0:
            res[i] = cur
            cur += 1
    return res

def main() -> None:
    data = sys.stdin.read().split()
    if not data:
        n, k = 7, 2
    else:
        n, k = int(data[0]), int(data[1])
    p = build_peaks_permutation(n, k)
    if not p:
        print(-1)
    else:
        print(" ".join(map(str, p)))

if __name__ == "__main__":
    main()

Với đầu vào 7 2, chương trình in:

1 7 2 6 3 4 5

Ba thói quen giúp bạn làm tốt dạng bài xây dựng:

• Thử tay với \(N\) nhỏ (\(N = 3, 4, 5\)) và viết ra mọi đáp án hợp lệ để tìm quy luật.
• Tìm giới hạn trước khi dựng. Câu hỏi "khi nào thì không có đáp án?" thường dẫn thẳng tới cách dựng.
• Viết hàm kiểm tra riêng. Hàm đếm số đỉnh chỉ có vài dòng, chạy nó trên mọi cặp \((N, K)\) nhỏ để chắc chắn mẫu của bạn đúng. Đây chính là tinh thần của kỹ thuật sinh test và đối chiếu code.

4. Thói quen trong và sau mỗi kỳ thi

Điểm rating chỉ thay đổi khi bạn thi thật, nên hãy tham gia đều ít nhất một vòng mỗi tuần, ưu tiên Div. 3, Div. 4 và Div. 2. Một số lưu ý thực tế:

• Đọc kỹ ràng buộc trước khi code. Tổng \(N\) của mọi bộ test thường bị giới hạn (ví dụ tổng \(N \le 2 \cdot 10^5\)), điều này cho phép bạn làm \(\mathcal{O}(N)\) cho từng bộ test mà không lo quá giờ.
• Dùng nhập xuất nhanh. Nhiều bài có tới \(10^4\) bộ test trong một lần chạy. Hãy xem cách tăng tốc nhập xuất trong C++ và Python để không bị quá thời gian vì đọc dữ liệu chậm.
• Cẩn thận tràn số. Kết quả vượt \(2^{31} - 1\) là nguyên nhân hàng đầu khiến bài bị sai test ẩn. Khi nghi ngờ, dùng long long.
• Làm lại bài sau kỳ thi (upsolve). Trong vòng 24 giờ sau khi thi, hãy giải lại bài kế tiếp sau bài cuối cùng bạn làm được. Đây là bài sát sức nhất và giúp bạn tiến bộ nhanh nhất.
• Không quá để ý rating trong tháng đầu. Rating dao động mạnh khi số kỳ thi còn ít. Hãy theo dõi số bài giải được mỗi kỳ thay vì con số rating.

Nếu bạn đang phân vân nên chọn nền tảng nào cho mục tiêu của mình, bài So sánh LeetCode, Codeforces và HackerRank phân tích rõ điểm mạnh của từng trang. Còn nếu muốn có một lộ trình tổng thể từ cơ bản đến thi học sinh giỏi, hãy xem Lộ trình lập trình thi đấu và HSG Tin học.

Luyện ngay trên Big-O Coding

Ba bài dưới đây giúp bạn làm quen với dạng bài xây dựng, tham lam và xử lý mảng, đúng nhóm kỹ năng của bài A, B trên Codeforces:

Nguồn tham khảo

• Wikipedia — Codeforces
• USACO Guide — How to Practice
• USACO Guide — Introduction to Competitive Programming