Tutorial
A. Khảo sát trái cây
Category. Đếm/constructive (bài toán cực trị theo cột).
Hint. Trong một lớp, mỗi học sinh chỉ được tính một lần cho “thích một loại quả nào đó”. Vì thế số học sinh tối thiểu của lớp đó không thể nhỏ hơn số học sinh nhiều nhất đang thích một loại quả trong lớp ấy.
Solution. Với mỗi lớp (tương ứng một cột), đáp án tối thiểu chính là giá trị lớn nhất của các tần suất “thích” theo từng loại quả trong cột đó. Lý do: ta có thể luôn hiện thực hoá cấu hình tối ưu bằng cách sắp xếp học sinh theo thứ tự 
và để học sinh thứ 
chọn những loại quả có tần suất 
; như vậy không có ai bị đếm hai lần và số học sinh cần có đúng bằng cực đại theo cột. Đáp án chung là tổng các cực đại của tất cả các cột.
Complexity. Duyệt lấy max theo cột: 
.
B. Cân bằng xiên nướng
Category. Xác suất – tổ hợp nhị phân (đếm đường đi 
).
Hint.
- Có hai bộ đếm
(ban đầu 
). Với mỗi 
, chọn ngẫu nhiên chỉ số bắt đầu 
, rồi phân bổ luân phiên đơn vị vào 
- Nếu chẵn
mỗi bên nhận đúng 
không đổi. - Nếu lẻ:
- bắt đầu ở
tăng 
, 
tăng 
tăng 
; - bắt đầu ở
giảm .
Solution. Gọi 
là số lượng 
lẻ. Bài toán rút gọn thành thực hiện phép cộng độc lập, mỗi phép biến thiên hiệu 
là 
hoặc 
với xác suất 
.
Ta cần xác suất để 
sau bước:
- Nếu
chẵn: cần đúng số lần 
bằng 
số cách hợp lệ 
. - Nếu lẻ: tổng cuối là
. Số cách 
.
Xác suất yêu cầu:
(vì các chẵn không ảnh hưởng đến hiệu).
Complexity. Tiền xử lý đếm và tính tổ hợp: 
cho duyệt dữ liệu ( 
chi phí tổ hợp, có thể tiền xử lý factorial hoặc dùng công thức/tiện tính theo ràng buộc 
).
C. Buổi trà thư giãn
Category. Quy hoạch động trên đoạn (interval DP).
Hint. Uống các cốc từ một dãy; trạng thái “còn lại” luôn là một đoạn liên tiếp. Khi biết biên trái–phải của đoạn còn lại, ta khôi phục được số cốc đã uống.
Solution. Đặt 
giá trị (hoặc tổng hạnh phúc/điểm) tốt nhất khi còn đoạn 
. Ở mỗi bước chỉ có 
chuyển tiếp: uống cốc trái nhất hoặc phải nhất của đoạn còn lại, rồi cập nhật sang 
hoặc 
. Duyệt theo độ dài đoạn từ ngắn đến dài để đảm bảo các trạng thái con đã có trước khi tính trạng thái lớn hơn. Kết quả là 
.
Complexity. Số trạng thái 
, mỗi trạng thái 2 chuyển tiếp 
thời gian, bộ nhớ (có thể tối ưu tuỳ bài).
D. Người sống sót
Category. Tham lam với sắp xếp (greedy + sorting).
Hint. Mỗi người “sống sót” cần dùng một số lần kỹ năng (hoặc tài nguyên) nhất định. Nếu ta luôn ưu tiên người cần ít tài nguyên hơn trước, số người cứu được sẽ tối đa.
Solution. Tính cho từng người số lần sử dụng kỹ năng cần thiết để cứu họ (lưu ý dùng kiểu số đủ lớn, ví dụ long long). Sắp xếp các giá trị này tăng dần rồi lấy lần lượt cho đến khi không đủ tài nguyên/budget nữa; đếm số người đã lấy. Đây là chiến lược chuẩn kiểu “nhặt đồ rẻ trước” để tối đa hoá số lượng.
Complexity. Tính nhu cầu: ; sắp xếp: 
; duyệt tích luỹ: .
E. Đồ thị tối giản
Category. Đếm cấu hình đồ thị theo khoảng cách (combinatorics on levels/BFS layers).
Hint.
- Sắp xếp/nhóm các đỉnh theo khoảng cách từ đỉnh : lớp
- Với đồ thị “tối thiểu”, mỗi đỉnh ở lớp
phải có chính xác một cạnh nối tới một đỉnh ở lớp 
(đảm bảo có đường đi và tránh dư thừa).
Solution. Đếm số đỉnh theo từng lớp. Với lớp 
, gọi 
là số đỉnh ở lớp 
và 
là số đỉnh ở lớp .
Nếu tồn tại lớp mà 
nhưng 
không thể kết nối đáp án 
.
Ngược lại, mỗi đỉnh của lớp chọn một “cha” trong lớp có 
cách. Nhân tất cả các lớp: 
(kèm mô-đun nếu đề yêu cầu). Việc tính làm được bằng sắp xếp/đếm.
Complexity. Sắp xếp/đếm theo khoảng cách: hoặc nếu đã có mảng khoảng cách; phép nhân lặp: 
.
F. Tái tạo số
Category. Xây dựng (constructive) – toán nhị phân.
Hint. Biết 
và 
đều có đúng 
bit “1” và 
bit “0” (độ dài 
); biết thêm 
có 
bit “1”. Cần chỉ ra điều kiện tồn tại và cách dựng 
theo 
.
Solution.
- Kết luận chuẩn: nếu
và 
thì tồn tại khi và chỉ khi 
. - Một cách dựng điển hình (khi
): cố định
- Nếu
: đặt 
có dạng
(trực giác: “chen” một số lượng mượn–mang để tạo đúng 
bit “1” trong 
).
- Nếu
: đặt
- Trường hợp biên
hoặc 
xử lý riêng (ràng buộc tương ứng). Lập luận mượn/không mượn theo từng khối đảm bảo có đúng bit “1” và độ dài 
.
Complexity. Dựng trực tiếp theo khối: 
.