Những thứ mình ước đã biết trước khi thi HSG Tin tỉnh

Thuật toán & Competitive Programming

Hồi lớp 10, mình cày Segment Tree gần 3 tuần. Implement được, hiểu được, debug được. Rất tự tin.

Vào phòng thi, bài 3 có đoạn cộng dồn trên đoạn con — mình nghĩ ngay đến Segment Tree. Code xong, WA. Ngồi debug 40 phút. Cuối buổi mới nhận ra bài đó dùng Prefix Sum 2D là xong, 15 dòng code, O(1) query. Mình đã WA vì cái gì? Vì quên mất công thức trừ phần giao:

sum(r1,c1,r2,c2) = P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1]

Dấu + ở cuối. Mình bỏ mất dấu +. TLE vì Segment Tree, WA vì công thức. Hỏng bài 3 hoàn toàn.

Đó là kỳ thi mình học được nhiều nhất — không phải vì làm tốt, mà vì làm sai đúng chỗ cần sai.

Vấn đề không phải là biết ít

Sau lần đó mình nhìn lại: mình biết Segment Tree nhưng không nhớ nổi công thức Prefix Sum 2D khi căng thẳng. Đó là vấn đề về độ chắc, không phải độ rộng.

HSG tỉnh không hỏi bạn biết bao nhiêu. Nó hỏi bạn có làm ra không trong 3 tiếng, có bug không, có kịp không. Hai câu hỏi đó khác nhau hoàn toàn.

Những thứ thật sự hay gặp (theo thứ tự ưu tiên)

Nhóm 1 — Không biết thì đừng đi thi

Mình nhấn mạnh Binary Search vì nhiều bạn dùng lower_bound mà không hiểu bên trong làm gì. Vào bài biến thể một chút là bí ngay. Nên tự code binary search từ đầu ít nhất vài chục lần cho đến khi viết không cần nghĩ.

Nhóm 2 — Cần để giải bài 3–4

Sort + Greedy O(n log n)

Gần như mọi bài Greedy đều cần sort trước. Mình từng bỏ qua bước này rồi ngồi nghĩ mãi không ra, cuối cùng sort thử thì thấy pattern ngay.

DP cơ bản

• DP 1 chiều (LIS, Knapsack): O(n²) hoặc O(n×k)
• DP 2 chiều (LCS, Edit Distance): O(n×m)
• DP con liên tiếp (Kadane): O(n) — bài này hay ra lắm, hay bị underestimate

Với DP, mình khuyên thật lòng: đừng học template. Học cách định nghĩa trạng thái. Kỳ thi nào mình định nghĩa sai dp[i] là mình làm hỏng bài đó, dù code có đẹp đến đâu.

Đồ thị

• BFS / DFS: O(V + E) — biết cả hai, biết khi nào dùng cái nào
• Dijkstra: O((V+E) log V) — chỉ dùng khi cạnh có trọng số dương
• Union-Find: O(α(n)) ≈ gần như O(1) — cho bài liên thông, Kruskal
• Floyd-Warshall: O(n³) — chỉ khi n ≤ 300~400, đừng dùng bừa

Toán cơ bản

• Sàng nguyên tố: O(n log log n)
• GCD / LCM: O(log n) — dùng __gcd hoặc tự viết Euclid
• Phân tích thừa số: O(√n)

Nhóm 3 — Lợi thế nếu biết

• Fenwick Tree (BIT): O(log n) update & query — nhẹ hơn Segment Tree nhiều
• Segment Tree cơ bản: O(log n) — khi cần lazy propagation
• Hashing chuỗi: O(n) build, O(1) compare — so sánh substring nhanh
• DP Bitmask: O(n × 2ⁿ), n ≤ 20

Mình học Segment Tree trước BIT. Sai thứ tự. BIT dễ hơn, code ngắn hơn, đủ dùng cho 80% bài cần range query. Nên học BIT trước.

Cách nghĩ khi ngồi phòng thi

Đọc đề xong, việc đầu tiên không phải nghĩ thuật toán — mà nhìn n. Rồi tính: mình có bao nhiêu "ngân sách" operation?

n ≤ 10⁸     →  O(log n) hoặc O(1), không hơn
n ≤ 10⁶     →  O(n) hoặc O(n log n)
n ≤ 10⁵     →  O(n log n) thoải mái
n ≤ 10³     →  O(n²) được
n ≤ 400     →  O(n³) vừa đủ

Thói quen này giúp mình loại được 2–3 hướng sai ngay trong đầu, trước khi bắt đầu nghĩ chi tiết.

Một thứ mình làm sai nhiều kỳ liên tiếp

Bài 1–2 thường dễ, nhưng mình hay cố làm "đẹp" — viết code tổng quát, đặt tên biến cẩn thận, xử lý edge case kỹ. Mất 45 phút cho bài đáng ra 15 phút.

Kết quả: bài 3 không đủ thời gian, code được 60% rồi hết giờ.

Bây giờ mình có rule: bài 1 và 2 phải xong trong 30–40 phút tổng cộng. Code xấu cũng được, biến tên a b c cũng được, miễn là chạy đúng và nộp.

Kết

Nếu bạn đang ôn và chưa biết bắt đầu từ đâu: học Prefix Sum cho đến khi viết 2D không cần tra công thức. Học Binary Search cho đến khi không bao giờ off-by-one. Học BFS/DFS cho đến khi thấy bài đồ thị là mừng chứ không sợ.

Rồi mới nghĩ đến cái khác.

Mình thi lại năm nay. Nếu bạn cũng đang chuẩn bị, comment lớp mấy và tỉnh nào đi — biết đâu mình share thêm đề cũ hoặc bài tập theo chủ đề được.