Lập trình thi đấu

Đề thi học sinh giỏi Tin học hay tuyển sinh chuyên Tin thường có giới hạn kiểu n ≤ 10⁵ hoặc n ≤ 10⁶. Với giới hạn đó, cách thử hết mọi khả năng thường cần tới 10¹⁰ phép tính trở lên, chỉ lấy được điểm các test nhỏ. Lập trình thi đấu là các kỹ thuật giúp đưa số phép tính xuống còn khoảng 10⁶ đến 10⁸, đủ để chương trình chạy kịp giới hạn của đề.

Mỗi bài trong mục này gồm:

• Lý thuyết giải thích vì sao kỹ thuật đúng và vì sao nó nhanh, kèm bảng chạy tay.
• Chương trình Python và C++ cho từng ý quan trọng.
• Bài luyện tập có đáp số để tự kiểm tra (miễn phí). Lời giải chi tiết các bài luyện tập có trong bộ tài liệu có phí.

Dành cho ai?

• Học sinh THCS, THPT ôn thi học sinh giỏi Tin học và tuyển sinh chuyên Tin lớp 10.
• Học sinh thi Tin học trẻ Bảng B, C (lập trình Python, C++).
• Thầy cô dạy đội tuyển cần một lộ trình có bài luyện tập theo từng kỹ thuật.

Mục này dành cho các bạn đã viết được chương trình có vòng lặp, mảng, hàm. Kiến thức nền (độ phức tạp, sắp xếp, tìm kiếm nhị phân, ngăn xếp, hàng đợi, BFS, DFS…) có ở mục CTDL & Giải thuật. Phần toán (số học, tổ hợp, hình học tọa độ, lý thuyết trò chơi…) có ở mục Toán tin.

Mức độ

Mỗi bài có icon mức độ trong mục lục và ở đầu bài:

Cơ bản

Kỹ thuật dùng nhiều trong đề học sinh giỏi cấp huyện, cấp tỉnh. Các bạn nên bắt đầu từ đây.

Nâng cao

Kiến thức cho thi học sinh giỏi cấp tỉnh, tuyển sinh chuyên Tin lớp 10.

Chuyên sâu

Kiến thức cho thi học sinh giỏi quốc gia, lập trình thi đấu (ICPC).

Ước lượng thời gian chạy

Các bài trong mục này so sánh hai cách làm bằng số phép tính, không bằng thời gian: thời gian chạy thật phụ thuộc rất nhiều vào máy, ngôn ngữ, trình biên dịch và cách viết code.

Để biết cách làm nào hợp với giới hạn của đề, các bạn thay n lớn nhất vào số bước. Ví dụ n = 10⁵: thử mọi cặp mất khoảng 5 × 10⁹ bước, còn kỹ thuật hai con trỏ chỉ mất khoảng 2 × 10⁵ bước, ít hơn khoảng 25 000 lần.

Lộ trình

Các bạn học lần lượt từ trên xuống. Mỗi bài có lý thuyết, chương trình Python và C++, và từ 10 đến 28 bài luyện tập (trừ hai bài kỹ năng thi).

Nền tảng

Các bài này có ở mục CTDL & Giải thuật, nên đọc trước khi vào phần kỹ thuật.

Bài	Ở đâu
Độ phức tạp thuật toán	CTDL & Giải thuật
Đệ quy, quay lui	CTDL & Giải thuật
Sắp xếp, tìm kiếm nhị phân	CTDL & Giải thuật
Thuật toán tham lam	CTDL & Giải thuật
Ngăn xếp, hàng đợi, heap	CTDL & Giải thuật
Tổng tiền tố và mảng hiệu	Toán tin

Kỹ thuật cơ bản

Bài	Mức độ
Hai con trỏ và cửa sổ trượt
Mảng đánh dấu và đếm tần suất
Rời rạc hóa (nén số)
Tìm kiếm nhị phân theo đáp án
Meet in the middle
Tìm kiếm tam phân
Tham lam trong thi đấu

Cấu trúc dữ liệu

Bài	Mức độ
Ngăn xếp đơn điệu, hàng đợi đơn điệu
Bảng thưa (Sparse Table)
Disjoint Set Union (DSU)
Cây Fenwick (BIT)
Cây phân đoạn (Segment Tree)

Quy hoạch động

Bài	Mức độ
Dãy con tăng dài nhất (LIS)
Xâu con chung dài nhất (LCS)
Bài toán cái túi
Quy hoạch động trên đoạn
Quy hoạch động trạng thái bit (bitmask)
Quy hoạch động trên cây
Quy hoạch động chữ số (ở Toán tin)

Đồ thị

Bài	Mức độ
BFS, DFS và ứng dụng trên lưới
Sắp xếp tô-pô
Đường đi ngắn nhất: Dijkstra, BFS 0-1, Bellman-Ford, Floyd
Cây khung nhỏ nhất: Kruskal, Prim
Tổ tiên chung gần nhất (LCA)
Khớp, cầu và thành phần liên thông mạnh
Đường đi và chu trình Euler
Đồ thị hai phía và ghép cặp

Xử lý xâu

Bài	Mức độ
Hash xâu
KMP và Z-function
Cây tiền tố (Trie)

Kỹ năng thi

Bài	Mức độ
Đọc giới hạn của đề để chọn thuật toán
Sinh test và stress test

Toán trong lập trình thi đấu

Số học (số nguyên tố, sàng, ƯCLN, modulo, lũy thừa nhanh, nghịch đảo modulo, định lý số dư Trung Hoa), tổ hợp, nguyên lý bù trừ, hình học tọa độ, lý thuyết trò chơi, xác suất có ở mục Toán tin.