Pemrograman Kompetitif · Pelajaran 10 dari 10
Strategi saat lomba
7 menit baca · BelajarCode
Kemampuan teknis saja belum cukup. Banyak peserta kehilangan nilai karena salah strategi.
Baca batasan soal
Batasan seperti "N ≤ 100.000" adalah petunjuk tentang kompleksitas yang dibutuhkan. Perkiraan berikut berlaku untuk C++ dengan batas waktu sekitar satu detik. Python lebih lambat, jadi berikan ruang lebih.
| Batas N | Kompleksitas yang masih cukup | Contoh teknik |
|---|---|---|
| N ≤ 10 | O(N!) | Mencoba semua permutasi |
| N ≤ 20 | O(2ᴺ) | Mencoba semua himpunan bagian |
| N ≤ 500 | O(N³) | Tiga perulangan bersarang |
| N ≤ 5.000 | O(N²) | Dua perulangan bersarang |
| N ≤ 1.000.000 | O(N log N) atau O(N) | Pengurutan, pencarian biner, satu kali lintasan |
Uji kasus batas
Sebelum mengirim jawaban, uji programmu dengan:
- Masukan terkecil, misalnya N = 1 atau N = 0 jika diizinkan.
- Masukan terbesar, untuk memeriksa kecepatan.
- Semua nilai sama, atau semua sudah urut.
- Bilangan negatif dan nol jika diizinkan.
- Jawaban yang sangat besar. Di C++, jawaban bisa melebihi batas tipe
int. Python aman karena bilangan bulatnya tidak terbatas.
Uji silang dengan brute force
Tulis versi brute force yang lambat tetapi pasti benar, lalu bandingkan dengan versi cepatmu pada ratusan data acak kecil.
1import random23def lambat(data, target):4 for i in range(len(data)):5 for j in range(i + 1, len(data)):6 if data[i] + data[j] == target:7 return True8 return False910def cepat(data, target):11 dilihat = set()12 for x in data:13 if target - x in dilihat:14 return True15 dilihat.add(x)16 return False1718random.seed(2026)19for uji in range(300):20 data = [random.randint(-10, 10) for _ in range(random.randint(0, 8))]21 target = random.randint(-15, 15)22 if lambat(data, target) != cepat(data, target):23 print("BERBEDA:", data, target)24 break25else:26 print("300 uji acak: semua cocok")300 uji acak: semua cocok
else setelah for dijalankan hanya jika perulangan selesai tanpa break. Jika ada perbedaan, kamu langsung mendapat contoh kecil yang membuktikan versi cepat salah.
Atur waktu
- Baca semua soal di awal, perkirakan tingkat kesulitannya.
- Kerjakan yang paling mudah lebih dulu untuk mengamankan nilai.
- Manfaatkan nilai sebagian: banyak soal punya subsoal (subtask) dengan batasan lebih kecil. Solusi brute force sering cukup untuk subsoal awal.
- Jangan terpaku pada satu soal terlalu lama. Pindah, lalu kembali dengan pikiran segar.
Cek pemahaman
Batasan soal adalah N ≤ 200.000. Pendekatan mana yang paling mungkin cukup cepat?
Latihan
Daftar periksa sebelum mengirim
Susun daftar periksa yang akan kamu jalankan sebelum mengirim jawaban soal pemrograman.
Pembahasan
Contoh daftar periksa:
- Format keluaran sudah persis sama dengan contoh, tanpa teks tambahan.
- Program lolos semua contoh di soal.
- Sudah diuji dengan kasus terkecil dan kasus dengan nilai sama semua.
- Kompleksitas sesuai batasan N di soal.
- Tidak ada
input()dengan teks pertanyaan. - Untuk soal yang ragu, sudah dibandingkan dengan versi brute force pada data acak kecil.
- Jika waktunya mepet, kirim dulu versi yang pasti benar untuk subsoal kecil.
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.