Đọc hiểu đề bài

Đọc đề bài cẩn thận là kỹ năng quan trọng nhất trong lập trình thi đấu. Nhiều lỗi sai không đến từ code mà đến từ việc hiểu sai yêu cầu.

Cấu trúc một đề bài

1. Mô tả bài toán

Phần này mô tả bối cảnh và yêu cầu. Hãy đọc kỹ để hiểu bài toán thực sự yêu cầu gì, không phải câu chuyện bao quanh nó.

2. Đầu vào (Input)

Mô tả chính xác định dạng dữ liệu nhận vào:

• Dòng đầu tiên chứa gì?
• Các dòng tiếp theo có bao nhiêu số?
• Có bao nhiêu test case?

3. Đầu ra (Output)

Mô tả chính xác định dạng kết quả cần in:

• In số hay chuỗi?
• Mỗi kết quả trên một dòng?
• Có khoảng trắng thừa ở cuối không?

4. Ràng buộc (Constraints)

Đây là phần quan trọng nhất để chọn thuật toán:

• $N\le {10}^3$ → $O(N^2)$ được
• $N\le {10}^5$ → cần $O(N\log N)$ hoặc $O(N)$
• $N\le {10}^9$ → cần $O(\log N)$ hoặc $O(1)$

5. Ví dụ (Sample)

Dùng ví dụ để kiểm tra hiểu đúng đề chưa. Hãy tự chạy tay trước khi code.

Quy trình đọc đề hiệu quả

1. Đọc lướt toàn bộ đề một lần.
2. Xác định: Input là gì? Output là gì?
3. Đọc kỹ ràng buộc.
4. Thử chạy tay ví dụ mẫu.
5. Nghĩ các trường hợp đặc biệt (edge cases).

Các lỗi thường gặp

• Đọc sai ràng buộc: Nhầm $N\le {10}^5$ thành $N\le {10}^3$.
• Bỏ qua định dạng output: Đề yêu cầu in YES/NO nhưng in Yes/No.
• Không đọc kỹ số test case: Đề có nhiều test case nhưng chỉ giải một.
• Nhầm 0-indexed và 1-indexed: Đỉnh đồ thị bắt đầu từ 0 hay 1?

Ví dụ phân tích đề

Bài toán: Cho mảng $N$ số nguyên, tìm tổng lớn nhất của một dãy con liên tiếp. Ràng buộc: $1\le N\le {10}^5$, $-{10}^9\le a_i\le {10}^9$

Phân tích:

• Input: số nguyên $N$, sau đó $N$ số nguyên.
• Output: một số nguyên (tổng lớn nhất).
• Ràng buộc $N\le {10}^5$ → cần thuật toán $O(N)$ hoặc $O(N\log N)$.
• Giá trị âm → cần xử lý trường hợp tất cả phần tử đều âm.