Bạn đọc kỹ lại đề bài: Có 60% số test ứng với 60% số điểm có N <= 1000

Khi làm bài thì không những phải đưa ra kết quả đúng mà còn phải chạy nhanh. Bài này giới hạn thời gian cho 1 test là 1 giây, với các test có N lớn (ví dụ N = 10^5) thì code của bạn chạy quá 1 giây và không được điểm của test đó. Với các test có N <= 1000 thì code của bạn chạy được trong 1 giây, và được tính điểm. Như vậy bạn được 60/100 điểm là chuyện bình thường.

Mình muốn bổ sung một chút câu trả lời của xuaan như sau: Thông thường dựa vào giới hạn đầu vào \(n\) mà bạn có thể thiết kế thuật toán cho đúng yêu  cầu bài toán nếu bạn muốn 100 điểm:

1. \(n \sim 10^6\) với các bài toán có giới hạn lớn như thế này thì bạn phải thiết kế thời gian \(O(n)\) cho bài toán. Đôi khi thuật toán \(O(n\log n)\) cũng có thể chấp nhận được nhưng thông thường hằng số phía sau \(O(n \log n)\) là nhỏ. Ví dụ bạn muốn giải bài toán với một dãy số tới 1 triệu phần tử nhưng bước đầu tiên bạn làm là sắp xếp (quicksort) và sau đó có thể giải bài toán trên mảng đã sắp xếp trong thời gian \(O(n)\). Để ý mặc dù là độ phức tạp chung là \(O(n \log n)\) (do bước sắp xếp) nhưng hằng số ẩn sau kí hiệu Big-O là nhỏ vì quicksort có hằng số nhỏ. Với bài toán dãy số tới 1 triệu phần tử như vậy bạn vẫn có thể giải trong thời gian 1s. Đường nhiên nếu bạn code quicksort không cẩn thận thì vẫn có thể TLE như thường.

2. \(n\sim 10^5\) Nếu giới hạn cỡ này thì thường yêu cầu thuật toán \(O(n \log n)\). Hằng số ẩn sau Big-O có thể lớn một chút cũng không sao. Một ví dụ  là những dạng bài kiểu truy vấn, bạn thiết kế một cấu trúc cây trong thời gian \(O(n \log n)\) và sau đó thực hiện truy vấn trên cây, mỗi thao tác truy vấn mất thời gian \(O(\log n)\). Đương nhiên nếu bạn giải được trong \(O(n)\) thì càng tốt. Ngoài ra phương pháp chia để trị thường cho bạn lời giải với độ phức tạp \(O(n \log n)\). Ví dụ bài toán cặp điểm gần nhất, quicksort, mergesort, dãy nghịch thế v...v..  đều dựa trên chia để trị để đạt được thời gian này. Như vậy, bạn có thể đoán được lời giải của bạn không được 100 điểm là do thuật toán cuả bạn là \(O(n^2)\) và sẽ bị TLE với các test có \(n\sim 10^5\).

3. \(n\sim 5000\) thông thường lời giải \(O(n^2)\) sẽ là lời giải 100 điểm cho các bài toán có  giới hạn này. Các thuật toán \(O(n^3)\) sẽ bị TLE.

4. \(n \sim 500\) Nếu code tốt thì thuật toán  \(O(n^3)\) sẽ là lời giải 100 điểm.

5. \(n \sim 20\) Thông thường lời giải cho các bài toán này sẽ là thuật toán quay lui, nhánh cận hoặc đôi khi là quy hoạch động với thời gian \(O(2^n)\)

Hi vọng sẽ giúp bạn trong các lần giải toán tiếp theo.

cảm ơn anh 

cảm ơn anh nhiều