Tiếp cận bài toán mới

Khi gặp một bài toán mới, đừng vội code ngay. Hãy theo quy trình dưới đây để tránh mất thời gian vào hướng sai.

Quy trình 5 bước

Bước 1: Đọc kỹ đề

• Đọc toàn bộ đề ít nhất hai lần.
• Gạch chân các từ khóa quan trọng: "lớn nhất", "nhỏ nhất", "đúng một lần", "liên tiếp"...
• Xác định rõ: Input là gì? Output là gì?
• Đọc kỹ ràng buộc ($N$, giá trị các phần tử, số test case).

Bước 2: Thử ví dụ mẫu bằng tay

Trước khi nghĩ thuật toán, hãy tự giải bằng tay các ví dụ trong đề. Điều này giúp bạn:

• Hiểu đúng yêu cầu bài.
• Phát hiện các trường hợp đặc biệt sớm.
• Có trực giác về hướng giải.

Bước 3: Xác định độ phức tạp cần thiết

Từ ràng buộc $N$, xác định thuật toán cần có độ phức tạp gì:

Bước 4: Nghĩ thuật toán

Xem xét từng hướng từ đơn giản đến phức tạp:

1. Brute force có được không? (thường $O(N^2)$ hoặc $O(N!)$)
2. Có thể sắp xếp để đơn giản hóa không?
3. Có thể dùng tìm kiếm nhị phân trên đáp án không?
4. Có cấu trúc con tối ưu → thử DP?
5. Có lựa chọn tham lam rõ ràng → thử Greedy?
6. Bài toán liên quan đến đồ thị → BFS/DFS/Dijkstra...?

Bước 5: Cài đặt và kiểm tra

• Code từng phần nhỏ, kiểm tra từng bước.
• Test với ví dụ trong đề trước.
• Tự tạo thêm test case: trường hợp nhỏ nhất ($N=1$), lớn nhất ($N={10}^5$), trường hợp đặc biệt.

Kỹ thuật: Simplify the Problem

Nếu bài quá khó, hãy đơn giản hóa trước:

• Giả sử $N$ nhỏ (chỉ 5-10 phần tử) — giải brute force.
• Bỏ bớt ràng buộc — giải phiên bản dễ hơn.
• Giải bài 1D trước khi nghĩ đến 2D.

Sau khi hiểu bài đơn giản hơn, dần dần mở rộng lên bài gốc.

Kỹ thuật: Think Backwards

Với một số bài, suy nghĩ ngược lại (từ đáp án về đầu vào) dễ hơn:

• Bài xóa phần tử → thêm phần tử theo thứ tự ngược.
• Bài đồ thị tách → đồ thị gộp (DSU).

Các tín hiệu nhận biết thuật toán