Meet in the Middle
Membagi dua eksponen dengan membagi pencarian
Meet in the Middle adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Saat Mencoba Semua Kemungkinan Terlalu Lambat
Beberapa persoalan memiliki N sekitar 40, sehingga mencoba semua 2^N himpunan bagian tidak mungkin dilakukan. Metode temu di tengah menyelamatkan persoalan berukuran menengah ini. 🤝
Gagasan Inti
Bagi masukan menjadi dua bagian. Selesaikan setiap bagian dengan mencoba semua kemungkinan, lalu gabungkan kedua hasil parsial tersebut secara cerdas.
Membagi Eksponen Menjadi Dua
Dua bagian berukuran N/2 masing-masing membutuhkan 2^(N/2), bukan total 2^N. Penyusutan sebesar akar kuadrat ini mengubah 2^40 menjadi 2^20 yang lebih mudah ditangani.
Target Klasik: Jumlah Himpunan Bagian
Tanyakan apakah ada himpunan bagian yang jumlahnya sama dengan target T. Jumlah himpunan bagian dengan N mendekati 40 adalah persoalan temu di tengah yang klasik.
Mengenumerasi Bagian Pertama
Daftarkan setiap jumlah himpunan bagian dari bagian kiri dan simpan semuanya. Dengan N/2 elemen, jumlahnya hanya 2^(N/2).
from itertools import combinations
left = arr[:len(arr)//2]
sums_l = []Mengenumerasi Bagian Kedua
Lakukan hal yang sama untuk bagian kanan dan buat daftar lengkap jumlah himpunan bagiannya. Sekarang Anda memiliki dua daftar yang mudah ditangani.
Menggabungkan dengan Pencarian
Untuk setiap jumlah kanan r, Anda memerlukan jumlah kiri yang sama dengan T dikurangi r. Himpunan berbasis pencincangan atau daftar terurut membuat pemeriksaan ini cepat.
need = T - r
found = need in left_setDua Cara untuk Mencocokkan
Untuk target yang tepat, gunakan himpunan berbasis pencincangan. Untuk menghitung atau mencari jumlah terdekat, urutkan salah satu bagian lalu lakukan pencarian biner di dalamnya.
Biaya Waktu
Total pekerjaan kira-kira 2^(N/2) dikalikan faktor log untuk pencarian atau pengurutan. Kompleksitas inilah yang membuat N mendekati 40 dapat dikerjakan.
Memori adalah Komprominya
Anda menyimpan satu bagian lengkap, sehingga memori bertambah menjadi 2^(N/2). Simpan hanya yang diperlukan agar tetap berada dalam batas.
Kegunaan Lainnya
Selain jumlah himpunan bagian, gunakan metode ini untuk mencari himpunan bagian maksimum di bawah batas, menghitung pasangan, dan persoalan bergaya logaritma diskret. Metode ini cocok untuk pembagian yang jelas.
Pemeriksaan Singkat
Anda menerapkan metode temu di tengah pada persoalan himpunan bagian dengan N elemen. Berapa perkiraan biaya waktunya?
Rangkuman
Bagi menjadi dua bagian, coba semua kemungkinan pada masing-masing bagian, lalu cocokkan jumlah kiri dan kanan. Anda menukar sedikit memori dengan percepatan yang sangat besar. 🚀
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Meet in the Middle” gratis?
Ya — teks lengkap “Meet in the Middle” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Meet in the Middle”?
Membagi dua eksponen dengan membagi pencarian Kamu berlatih Competitive Programming Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.
Berapa lama pelajaran “Meet in the Middle” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- State Menang & Kalah dalam Permainan
- Nim dan Bilangan Grundy
- Meet in the Middle
- Debug Cepat: Stress Test & Triage