Ôn thi VOI

Trang này là điểm xuất phát cho ai ôn thi VOI (kỳ thi chọn học sinh giỏi quốc gia môn Tin học). Nội dung được tổng hợp từ 119 đề VOI 2005 - 2026 (22 năm; từ 2011 mỗi năm đủ 2 ngày x 3 bài, các năm cũ hơn chỉ còn lưu được 3 đến 7 bài), tất cả đều đã có trên CTOJ để luyện. Phần dự đoán và lộ trình dựa chủ yếu vào giai đoạn hiện đại 2016 - 2026. Độ khó ghi theo thang rating kiểu Codeforces. Mỗi kỹ thuật dưới đây đều có trang wiki riêng với trực giác, ví dụ chạy tay, lỗi thường gặp và mục "Đề VOI" chỉ ra bài nào dùng kỹ thuật đó.

Đề VOI trông như thế nào

• Hình thức: 2 ngày, mỗi ngày 3 bài trong 180 phút; bài chấm theo lô (batch) chuẩn, chấm subtask theo phần trăm, bài nào cũng có subtask nhỏ giải được bằng vét cạn. Chưa từng có bài interactive hay output-only.
• Giới hạn: input lớn dần (${10}^5$ đến ${10}^6$ phần tử là phổ biến), thời gian 1 đến 3 giây (bài cấu trúc dữ liệu nặng có thể tới 4 giây); thời cũ thì ngược lại, input nhỏ nhưng thời gian rất chặt (0.1 đến 0.6 giây). Hình học luôn là hình học nguyên, không có số thực.
• Độ khó tăng đều suốt 22 năm, và sàn tăng nhanh hơn trần (rating trung bình, dễ nhất, khó nhất mỗi năm):

(*) Năm chỉ còn lưu được 3 - 4 bài nên số liệu chỉ mang tính tham khảo; riêng 2005 bị lệch lên vì các bài còn lại đều là bài "đáng nhớ", trong đó có voi05_firewk (2500).

Nhìn tổng thể: trung bình từ khoảng 1400 - 1650 (2006 - 2012) lên 1700 - 1850 (2013 - 2018) rồi 2200 - 2330 (2024 - 2026). Sàn tăng nhanh hơn trần: bài 1000 - 1300 phổ biến tới 2012, bài 1400 còn tới 2020, năm 2026 sàn đã là 2000; trần chỉ tăng từ khoảng 2300 lên 2600.

Hệ quả thực tế: bài mở màn đã lên mức 2000 (năm 2026), không còn bài "lấy điểm miễn phí". Muốn có giải phải giải trọn được bài 2000+ và gom subtask của các bài còn lại.

Ba thời kỳ của đề VOI

Bản đồ kiến thức

Số bài là ước lượng trên 119 bài 2005 - 2026 (một bài có thể thuộc nhiều nhóm).

Chỉ xuất hiện đúng một lần trong 22 năm (biết dạng, không cần luyện sâu): luồng, lát cắt nhỏ nhất (voi14jobset), lý thuyết trò chơi thuần (voi11pgame), nút xung yếu (voi09stnode), nhánh cận (voi06change), tính chất trao đổi của cây khung (voi14aznet), slope trick (voi18seq), plug DP (voi19robot), sàng Lucy (voi22matrix), suffix array (voi25encode), treap (voi25tseq).

Chưa từng xuất hiện trong 2005 - 2026: 2-SAT, FFT, suffix automaton, Aho-Corasick, Li Chao và CHT, hình học số thực, bài interactive. Chỉ cần biết khái niệm, không nên đầu tư sâu.

Xu hướng 2005 - 2026

1. Độ khó tăng gần gấp đôi về mặt bằng. Trung bình từ ~1400 - 1650 (2006 - 2012) lên ~1700 - 1800 (2013 - 2018) rồi ~2200 - 2330 (2024 - 2026). Sàn tăng nhanh hơn trần: bài 1000 - 1300 phổ biến tới 2012, còn 1400 tới 2020, năm 2026 sàn đã là 2000.
2. Đề tiến hóa từ cài đặt sang mô hình hóa rồi sang cấu trúc dữ liệu. Từ 2023 đa số bài có $Q$ truy vấn, xử lý offline, segment tree, Fenwick, treap.
3. Cây là chủ đề nóng nhất hiện nay nhưng hoàn toàn mới: 15 năm đầu không có bài cây chuyên sâu nào; từ 2020 mỗi năm 1 đến 2 bài (HLD, centroid, DP trên cây, LCA).
4. Hình học đổi thế hệ: thời cũ là hình học rời rạc + duyệt (voi05steel, voi11colrec); từ 2016 là sweep line + cấu trúc dữ liệu, có mặt 9/11 năm gần nhất. Luôn là hình học nguyên.
5. Kỹ năng trường tồn: DP (mọi thời kỳ, chỉ đổi độ sâu), tham lam có chứng minh, chặt nhị phân, BFS/Dijkstra, đếm tổ hợp. Digit DP là "mầm cũ nở muộn": gieo năm 2010 (voi10_taxid), thành vũ khí phân loại từ 2019 (aspal, pnum).
6. Kỹ năng đã biến mất: số lớn (bắt buộc 2007 - 2013), SCC và nút xung yếu (2006 - 2009), quay lui nhánh cận làm lời giải chính (đỉnh điểm 2006), cặp ghép (lần cuối 2016), luồng (một lần, 2014). Quay lui vẫn cần, nhưng để gom subtask nhỏ.
7. Kỹ thuật "hàn lâm" xuất hiện một lần rồi thôi, ở mọi thời kỳ, và luôn kèm subtask gỡ điểm: gặp bài lạ thì lấy subtask trước.

Dự đoán cho VOI 2027

Đây là dự đoán xác suất dựa trên tần suất giai đoạn hiện đại 2016 - 2026 (đề cũ hơn khác phong cách nên ít giá trị dự đoán), không phải cam kết. Độ khó dự kiến: trung bình khoảng 2300 - 2400, bài dễ nhất khoảng 1900 - 2100.

Lộ trình ôn luyện (khoảng 18 tuần)

Nguyên tắc chung: mỗi bài tự làm hết subtask nhỏ trước khi đọc lời giải, và sau khi đọc phải cài lại từ đầu không nhìn code.

Giai đoạn 1, củng cố nền (4 tuần). Mục tiêu: mọi kỹ thuật mức 1400 - 1800 thành phản xạ.

• DP cơ bản đến trung bình: voi20_bonus, voi16_seq198, voi23_whome, voi21_noel, voi23_adn.
• Đồ thị nền (BFS, Dijkstra, DSU, cầu khớp): voi18_spone, voi17_metro, voi17_bgame, voi20_build.
• Kỹ năng ngang (tổng tiền tố, hai con trỏ, chặt nhị phân, tham lam): voi19_solpin, voi20_light, voi17_virus, voi22_pair, voi18_queue.
• Viết template riêng cho segment tree (có lazy), Fenwick, heap.

Giai đoạn 2, chuyên đề trọng điểm khối 1 (4 tuần).

• Cây: voi25_ship (LCA), voi20_equake, voi21_comnet, voi23_food (DP trên cây), voi26_pine, voi24_fbuy (HLD), voi24_netw (centroid). HLD + Fenwick phải cài được dưới 30 phút.
• Sweep line + hình học nguyên: voi20_stars, voi22_sseq, voi17_hway, voi22_paint, voi25_roai, voi16_rbull, voi22_inet.

Giai đoạn 3, chuyên đề trọng điểm khối 2 (4 tuần).

• Đếm, digit DP, số học: voi19_aspal, voi25_pnum, voi21_or, voi18_bonus, voi24_noel, voi25_encode, voi26_tet, voi24_wpro, voi17_fibseq; đọc thêm voi22_matrix để biết dạng.
• Cấu trúc dữ liệu nâng cao + offline: voi24_impev, voi23_sdev, voi25_tseq, voi21_bonus, voi26_post.
• Chủ đề phòng bị (hiểu ý tưởng, cài một lần): xâu (voi19_comstr), plug DP (voi19_robot), slope trick (voi18_seq), cặp ghép Kuhn (voi16_exam).

Giai đoạn 4, luyện đề thật (4 tuần). Mỗi tuần 2 buổi thi thử đúng điều kiện (180 phút, 3 bài, không mạng), lần lượt đề VOI 2020, 2023, 2025, 2026 (danh sách ở mục cuối). Chữa hết 3 bài trong 48 giờ, cài lại lời giải chuẩn, ghi sổ lỗi: sai ở đọc đề, thuật toán, cài đặt hay quản lý thời gian. Đề 2021, 2022, 2024 để dành làm đề dự phòng.

Giai đoạn 5, nước rút (2 - 3 tuần). Mỗi ngày 1 bài mức 2000 - 2300 làm trọn vẹn; ôn sổ lỗi và template (segment tree lazy, HLD, Fenwick, Dijkstra, LCA, khung digit DP, hashing); buổi thi thử cuối cách ngày thi ít nhất 5 ngày.

Tự kiểm tra cuối mỗi giai đoạn

Chiến thuật phòng thi

1. 15 phút đầu đọc cả 3 bài, xếp thứ tự làm theo tỉ lệ (điểm subtask dễ lấy) / (thời gian ước tính), không theo thứ tự đề. Xem thêm Tiếp cận bài toán mới và Ước lượng giới hạn.
2. Luôn nộp vét cạn trước. Mỗi bài đều có subtask nhỏ; gom 20 - 40% mỗi bài là chênh lệch một bậc giải.
3. Quy tắc 60 phút: bế tắc một bài quá 60 phút thì chốt subtask rồi chuyển bài, quay lại nếu còn thời gian.
4. Trước khi nộp bản đầy đủ, tự sinh test biên (n nhỏ nhất, giá trị trùng, đồ thị không liên thông, tràn số) và đối chiếu với vét cạn: xem Kỹ thuật debug.
5. Cẩn thận long long, đọc kỹ giới hạn từng subtask. Giới hạn thời gian rất chặt so với input thường là dấu hiệu cần thuật toán nhanh hơn hẳn.

Đề VOI 2005 - 2026 trên CTOJ

Dùng để thi thử theo năm: mỗi buổi 180 phút chọn 3 bài cùng năm. Các bài trong bảng xếp theo mã bài, không theo ngày thi. Đề 2016 - 2026 sát phong cách hiện nay nhất; đề 2005 - 2015 hợp để luyện kỹ năng nền và làm quen dạng cũ.