Membaca Batasan, Memilih Kompleksitas

Setiap soal mencantumkan batas untuk n dan nilainya. Batasan tersebut secara tidak langsung memberi tahu kompleksitas yang diharapkan pembuat soal. 🔍

Sebelum merancang apa pun, cari nilai terbesar n dalam batasan. Ukuran n menentukan apakah diperlukan solusi kuadratik, linear, atau logaritmik.

Ketika n paling besar 20, bahkan pencarian menyeluruh eksponensial masih sesuai batas. Batas kecil merupakan kesempatan untuk mencoba setiap kombinasi tanpa khawatir.

Jika n mencapai beberapa ratus, solusi O(n^3) masih dapat lolos. Perulangan tiga tingkat atau DP dasar pada pasangan masih layak digunakan.

Untuk n sekitar 5000, targetkan O(n^2). Perulangan bersarang pada larik membutuhkan sekitar 2,5 dikali 10^7 langkah, yang masih sesuai anggaran.

Ketika n mencapai 10^5 atau 10^6, Anda memerlukan O(n log n) atau O(n). Pengurutan, jumlah prefiks, dan dua penunjuk menjadi alat andalan Anda.

Jika n berjumlah satu miliar, tidak ada perulangan sepanjang n yang dapat bertahan. Anda harus menggunakan O(log n) atau O(1), dengan matematika atau pencarian biner pada jawaban.

Batasan pada nilai juga penting. Bilangan besar memperingatkan adanya luapan dalam bahasa lain dan mungkin mengisyaratkan penggunaan aritmetika modular.

Soal dengan banyak pengujian sering kali membatasi jumlah n, bukan setiap n. Bacalah ini dengan cermat karena hal tersebut mengubah seberapa besar perulangan Anda dapat dibuat dengan aman.

Tentukan kompleksitas target berdasarkan n, lalu pilih algoritma yang mencapainya. Membiarkan n memandu perancangan lebih baik daripada menebak lalu menulis ulang nanti.

Simpan tabel ini dalam ingatan Anda. Peta batasan ke kompleksitas mengubah pembacaan cepat terhadap batas menjadi rencana seketika saat kontes.

Biarkan n menunjukkan kompleksitas yang tepat.

Sekarang Anda membaca batasan sebagai target: n kecil memungkinkan pencarian menyeluruh, 10^5 memerlukan n log n, dan 10^9 menuntut logaritma atau matematika. Biarkan n menentukan pendekatannya. 🗺️