Thuật toán

Đây là mục lớn nhất của wiki: nơi tập hợp các kỹ thuật giải toán, từ những paradigm nền tảng (tham lam, chia để trị, hai con trỏ) đến các nhóm chủ đề chuyên sâu (quy hoạch động, đồ thị, xâu, toán học, hình học, luồng mạng). Mỗi trang đều có ý tưởng, ví dụ chạy tay, lỗi thường gặp và bài tập luyện.

Kỹ thuật nền tảng

• Tham lam (Greedy): chọn tối ưu cục bộ ở mỗi bước; khi nào đúng và cách chứng minh.
• Chia để trị: chia bài toán thành các phần con rồi gộp kết quả.
• Two Pointers: hai con trỏ quét mảng/xâu trong $O(N)$ thay vì $O(N^2)$.
• Sắp xếp & Tìm kiếm nhị phân: nền tảng của vô số lời giải; binary search trên đáp số.
• Ternary Search: tìm cực trị của hàm unimodal.
• Nén tọa độ: ánh xạ giá trị lớn về chỉ số nhỏ.
• Quay lui và nhánh cận: duyệt mọi cấu hình có cắt tỉa, nhánh cận cho bài tối ưu; công cụ gom subtask nhỏ.
• Meet in the Middle: chia đôi không gian tìm kiếm để giảm mũ.
• CDQ Divide and Conquer: chia để trị offline cho bài toán nhiều chiều.
• Tham lam với hàng đợi ưu tiên: lập lịch theo hạn chót, tham lam "đổi ý", gộp Huffman, xóa lười.
• Xử lý truy vấn offline: sắp truy vấn rồi quét, xử lý ngược thời gian, chặt nhị phân song song.
• Tối ưu phân thức (Dinkelbach): cực trị một tỉ số (trung bình, mật độ) bằng cách lặp tuyến tính hóa.

Nhóm chủ đề lớn (có trang con)

• Quy hoạch động (DP): paradigm rộng nhất (DP chữ số, khoảng, bitmask, trên cây, tối ưu hóa...). Nên đầu tư nhiều nhất.
• Thuật toán đồ thị: DFS/BFS, đường đi ngắn nhất, SCC, cầu, khớp, Euler, 0-1 BFS, 2-SAT.
• Thuật toán xâu: hashing, KMP, Z, Manacher, Suffix Array/Automaton, Aho-Corasick.
• Toán học: số học modular, tổ hợp, FFT, nhân ma trận, sàng, Miller-Rabin.
• Hình học tính toán: tích có hướng, bao lồi, quét đường thẳng, điểm trong đa giác.
• Luồng mạng (Network Flow): max flow (Dinic), min cost flow, ghép cặp hai phía.
• Lý thuyết trò chơi: thế thắng/thua, hàm Grundy, Nim.

Gợi ý thứ tự học

Nắm vững nhóm Kỹ thuật nền tảng trước (đặc biệt sắp xếp + tìm kiếm nhị phân, tham lam, hai con trỏ). Sau đó đầu tư mạnh vào Quy hoạch động và Thuật toán đồ thị: hai chủ đề xuất hiện nhiều nhất trong các kỳ thi. Các nhóm còn lại học theo nhu cầu. Đừng quên đối chiếu Độ phức tạp khi chọn thuật toán.