Đọc giới hạn của đề để chọn thuật toán

Mức độ: Cơ bản

Đề thi luôn cho giới hạn của dữ liệu: n ≤ 20, n ≤ 10⁵, a_i ≤ 10⁹… Những con số này không chỉ để bảo đảm dữ liệu “không quá lớn”: chúng là gợi ý về thuật toán người ra đề mong đợi. Đọc giới hạn trước khi nghĩ lời giải giúp loại ngay những cách chắc chắn không đủ nhanh và hướng tới cách đúng.

Số bước theo giới hạn n

Thay n lớn nhất vào độ phức tạp của cách làm để biết số bước. Một máy chấm bình thường chạy C++ được cỡ 10⁸ phép tính đơn giản mỗi giây; Python chậm hơn nhiều lần (thường 10 đến 50 lần), nên với Python cần số bước nhỏ hơn hẳn.

Giới hạn n	Số bước chấp nhận được thường gặp	Thuật toán hay gặp
n ≤ 10	n! (khoảng 3,6 × 106)	thử mọi hoán vị, quay lui
n ≤ 20	2n × n (khoảng 2 × 107)	duyệt tập con, quy hoạch động bitmask
n ≤ 40	2n/2 (khoảng 106)	meet in the middle
n ≤ 500	n3 (khoảng 108)	Floyd, quy hoạch động ba chiều
n ≤ 5000	n2 (khoảng 2,5 × 107)	quy hoạch động hai chiều, thử mọi cặp
n ≤ 105 đến 106	n log n hoặc n	sắp xếp, tìm kiếm nhị phân, hai con trỏ, cây phân đoạn
n ≤ 109 đến 1018	$\sqrt{n}$, log n hoặc công thức	toán, lũy thừa nhanh, tìm kiếm nhị phân

Ví dụ: đề cho n ≤ 2 × 10⁵ mà cách nghĩ đầu tiên là thử mọi cặp (n² / 2 = 2 × 10¹⁰ bước) thì chắc chắn phải tìm cách khác, cỡ n log n. Ngược lại đề cho n ≤ 100 thì đừng cố tìm cách n log n phức tạp: n³ = 10⁶ bước là quá đủ.

Subtask: lấy điểm từng phần

Đề học sinh giỏi thường chia điểm theo subtask: 30% số điểm có n ≤ 1000, 70% còn lại n ≤ 10⁵… Mỗi subtask là một gợi ý: cách n² lấy được 30%, cách n log n lấy được 100%.

Chiến lược an toàn:

1. Viết cách đơn giản nhất chạy đúng cho subtask nhỏ trước. Cách này cũng dùng làm chương trình vét cạn để kiểm tra cách nhanh.
2. Còn thời gian thì nghĩ cách nhanh cho subtask lớn.
3. Có thể nộp một chương trình gộp: n nhỏ thì chạy cách đơn giản, n lớn thì chạy cách nhanh. Nếu cách nhanh có lỗi, vẫn giữ được điểm subtask nhỏ.

Những giới hạn khác cần để ý

Giới hạn	Điều cần nghĩ tới
giá trị tới 109, cộng hoặc nhân nhiều số	tổng vượt 2,1 × 109 thì C++ phải dùng long long
giá trị tới 1018	nhân hai số tràn cả long long; dùng __int128 hoặc nhân theo modulo
giá trị tới 109, cần mảng đếm	không làm mảng 109 ô được; rời rạc hóa hoặc dùng map
“in ra kết quả chia lấy dư 109 + 7”	đáp số rất lớn, thường là bài đếm (quy hoạch động, tổ hợp)
giới hạn bộ nhớ (ví dụ 256 MB)	mảng 108 số int đã tốn 400 MB; bảng quy hoạch động lớn phải giữ hai hàng
q câu hỏi tới 105	không trả lời từng câu bằng cách duyệt lại cả dữ liệu; chuẩn bị trước (tổng tiền tố, bảng thưa…)

Đọc và ghi nhanh

Dữ liệu 10⁶ số đọc chậm thì chương trình đúng vẫn quá thời gian.

• C++: thêm ios::sync_with_stdio(false); cin.tie(nullptr); ở đầu main, in xuống dòng bằng "\n" thay vì endl (endl xả bộ đệm mỗi lần in).
• Python: đọc cả dữ liệu một lần bằng sys.stdin.read().split() thay vì gọi input() nhiều lần, gom kết quả vào danh sách rồi in một lần bằng "\n".join(...).