Một bài học quý báu mà thầy Thắng có truyền lại cho đội O trong kỳ thi Olympic như sau:
Vào một năm nào đó, kỳ thi của đội anh Hinh hay anh Hùng dự ACM-ICPC có bài toán cần giải đại loại là cho 1 khoảng và in ra các số nguyên tố trong khoảng đó. Tất nhiên kết quả phải được đưa ra dưới x giây.
Xét về kỹ thuật thông thường ta buộc phải kiểm tra từng số trong khoảng đó và xác định xem đó là có phải số nguyên tố hay không? Với bài toán kinh điển kiểm tra có phải số nguyên tố hay không thì có nhiều thuật toán, nhưng số càng lớn thì càng cần nhiều thời gian hơn để kiểm tra. Và việc xử lý vấn đề thời gian là yếu tố quan trọng nhất vì với các thuật toán hiện tại thì không thể xử lý được trong khoảng thời gian mà ban tổ chức đưa ra…
Vì thi ACM-ICPC không chấm thuật toán mà tính pass hay không thông qua tập test của ban tổ chức. Tất nhiên nếu có danh sách tập test và kết quả của ban tổ chức thì chỉ cần IF ELSE cũng đạt điểm.
Một ý tưởng xử lý rất thông minh đó là ta tiến hành liệt kê ra 1 tập sẵn các số nguyên tố nằm trong phạm vi của đề của ban tổ chức trước, sau đó chương trình chỉ cần đọc file và lấy danh sách số nguyên tố trong khoảng mà đề bài yêu cầu. Độ phức tạp sẽ O(n).
Kết quả của đội là đã giải thành công bài toán, bài đã chấp nhận, file sinh danh sách số nguyên tố gần 1GB, mất gần hết thời gian cả cuộc thi.
Đây là bài toán kinh điển về kinh nghiệm xử lý vấn đề, nó thay đổi tư duy và cách tiếp cận bài toán. Cũng như là phải hiểu rõ phương thức và hoàn cảnh. Nó có thể ứng dụng trong nhiều trường hợp trong công việc và đời sống.
P/S: Tất nhiên cách này không thể áp dụng được trong cuộc thi Olympic vì cuộc thi Olympic là cuộc thi thuật toán, khi ta chưa thể code được chương trình nhưng ta đưa ra được quan điểm, giải thuật xử lý đúng đắn thì ban tổ chức vẫn có thể cộng điểm cho chúng ta.
Với bài toán trên nếu giới hạn dung lượng file thì cũng không thể đạt điểm cho bài toán này.