11. Brute force — Pembahasan PR

Berkas .cpp jawabannya ada di exercises/11/homework/solutions/.

Halaman ini dibuka sesudah mencoba sendiri. Bandingkan jalan pikiranmu dengan bagian Cara berpikir, bukan kodenya baris per baris: dua kode yang berbeda bentuk bisa sama-sama benar, dan yang perlu ditiru adalah cara sampai ke sana. Bagian Uji di tiap soal berisi masukan dan keluaran yang sudah diperiksa — jalankan jawabanmu sendiri dengan masukan itu sebelum merasa selesai.

Menjalankan salah satu jawabannya:

g++ -std=c++17 -O2 -o jawab exercises/11/homework/solutions/01-pasangan.cpp
./jawab

Soal 1 — Pasangan berjumlah k

Soal. Cacah pasangan (i, j), i < j, dengan a[i] + a[j] == k.

Cara berpikir. Hitung dulu: n ≤ 2.000 berarti n²/2 = 2 juta pasangan. Aman. Brute force dua perulangan sudah merupakan jawaban penuh.

Kunci kebenarannya ada pada j = i + 1. Kalau ditulis j = 0, setiap pasangan terhitung dua kali dan elemen ikut dipasangkan dengan dirinya sendiri.

Pembahasan.

int banyak = 0;
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        if (a[i] + a[j] == k) banyak++;

Uji.

Baris kedua adalah kasus tepi yang penting: nilai yang sama tidak boleh membuat program berhenti menghitung. Jawabannya 6, yaitu seluruh pasangan 4 × 3 / 2. Baris ketiga menguji n = 1, saat perulangan dalam tidak pernah berjalan.

Kesalahan umum.

• Memakai int untuk pencacah ketika soal memungkinkan jawaban lebih dari 2 × 10⁹ (misalnya semua elemen sama dan k pas). Untuk n = 2.000 maksimalnya sekitar 2 juta, jadi int cukup di sini — tetapi periksa batasnya setiap kali.
• Menjumlahkan a[i] + a[j] dalam int ketika elemennya mendekati 10⁹. Dua elemen sebesar itu sudah melewati batas.

Soal 2 — Tripel Pythagoras

Soal. Cacah tripel a < b < c ≤ n dengan a² + b² = c².

Cara berpikir. Tiga perulangan bersarang dengan syarat a < b < c memberi sekitar n³/6 langkah. Untuk n = 300 itu 4,5 juta — masuk dengan mudah.

Tetapi ini juga contoh pemangkasan dari bab: c tidak perlu dicari. Setelah a dan b dipilih, c dihitung sebagai akar dari a² + b², lalu diperiksa apakah bilangan bulat. Jumlah langkahnya turun menjadi n²/2 = 45.000.

Pembahasan (tiga perulangan).

int banyak = 0;
for (int a = 1; a <= n; a++)
    for (int b = a + 1; b <= n; b++)
        for (int c = b + 1; c <= n; c++)
            if (a * a + b * b == c * c) banyak++;

Pembahasan (dua perulangan).

int kuadrat = a * a + b * b;
int c = (int)sqrt((double)kuadrat);
for (int d = c - 1; d <= c + 1; d++)
    if (d > b && d <= n && d * d == kuadrat) banyak++;

Pemeriksaan c − 1 sampai c + 1 ada karena sqrt bekerja dengan double dan bisa meleset satu. Kebiasaan ini menyelamatkan banyak jawaban.

Untuk n = 20 jawabannya 6, untuk n = 300 jawabannya 209.

Uji.

Versi tiga perulangan memerlukan sekitar 300³/6 ≈ 4,5 juta langkah untuk n = 300, sedangkan versi dua perulangan (berkas 02b-tripel-cepat.cpp) sekitar 45.000. Keduanya menjawab 209; bedanya baru terasa kalau batasnya dinaikkan.

Kesalahan umum.

• Menulis b = 1 dan c = 1 sebagai batas bawah, lalu menghitung tripel yang sama beberapa kali dalam urutan berbeda.
• Mempercayai (int)sqrt(...) tanpa memeriksa tetangganya.

Soal 3 — Himpunan bagian berjumlah k

Soal. Cacah himpunan bagian yang jumlahnya k, n ≤ 20.

Cara berpikir. 2²⁰ ≈ 1 juta kemungkinan, masing-masing butuh 20 langkah penjumlahan: 21 juta. Masuk.

Setiap bilangan mask dari 0 sampai 2ⁿ − 1 adalah satu himpunan bagian. mask & (1 << i) memeriksa apakah barang ke-i ikut terpilih.

Pembahasan.

int banyak = 0;
for (int mask = 0; mask < (1 << n); mask++) {
    long long jumlah = 0;
    for (int i = 0; i < n; i++)
        if (mask & (1 << i)) jumlah += a[i];
    if (jumlah == k) banyak++;
}

Uji.

Baris kedua adalah inti soalnya: mask = 0 mewakili "tidak mengambil apa pun" dan jumlahnya 0, jadi ia terhitung ketika k = 0. Program yang memulai perulangan dari mask = 1 akan menjawab 0 di sini.

Kesalahan umum.

• Menulis 1 << n dengan n sampai 31 atau lebih; hasilnya meluap. Untuk n besar gunakan 1LL << n.
• Memakai int untuk jumlah. Dua puluh elemen bernilai 10⁹ menghasilkan 2 × 10¹⁰.
• Lupa bahwa mask = 0 adalah himpunan kosong dengan jumlah 0 — yang memang harus ikut terhitung ketika k = 0.

Soal 4 — Urutan terbaik

Soal. Jalur terpendek mengunjungi semua kota, mulai dari kota 0, n ≤ 8.

Cara berpikir. Kota 0 tetap di awal, jadi yang diatur urutannya hanya n − 1 kota sisanya: paling banyak 7! = 5.040 urutan. Setiap urutan memerlukan n langkah untuk menjumlahkan jaraknya. Sangat ringan.

next_permutation menghasilkan urutan berikutnya dan mengembalikan false setelah urutan terakhir — karena itu datanya harus terurut sebelum perulangan do ... while dimulai.

Pembahasan.

int kota[16];
int m = 0;
for (int i = 1; i < n; i++) kota[m++] = i;
sort(kota, kota + m);

int terpendek = 2000000000;
do {
    int panjang = 0, sekarang = 0;
    for (int i = 0; i < m; i++) {
        panjang += jarak[sekarang][kota[i]];
        sekarang = kota[i];
    }
    if (panjang < terpendek) terpendek = panjang;
} while (next_permutation(kota, kota + m));

Untuk contoh 4 kota pada berkas PR, jawabannya 65 (jalur 0 → 2 → 1 → 3: 15 + 35 + 25 = 75; jalur 0 → 1 → 3 → 2: 10 + 25 + 30 = 65).

Uji.

Kasus kedua adalah contoh klasik: jalur terpendek yang mengunjungi keempat kota dari kota 0 adalah 0 → 1 → 3 → 2 dengan panjang 10 + 25 + 30 = 65. Jumlah urutan yang dicoba (n−1)! = 6, cukup sedikit untuk diperiksa dengan tangan — dan itu memang gunanya menguji dengan n kecil.

Kesalahan umum.

• Ikut mempermutasikan kota 0, sehingga jalur yang tidak berawal di kota 0 ikut dihitung.
• Lupa sort sebelum do ... while, sehingga sebagian urutan terlewat.
• Lupa kasus n = 1, ketika tidak ada perpindahan sama sekali.

Tantangan — Nilai sebagian

Soal. Tulis versi O(n²) dan O(n) untuk selisih terbesar a[j] − a[i] dengan i < j, lalu bandingkan.

Cara berpikir. Versi lambat adalah definisi soal yang ditulis apa adanya. Versi cepat berasal dari satu pengamatan: saat berada di posisi j, nilai a[i] terbaik adalah yang terkecil di antara semua posisi sebelum j. Jadi cukup satu variabel terkecil yang diperbarui sambil berjalan.

Urutan di dalam perulangan penting: hitung dulu selisih memakai terkecil yang lama (yang pasti berasal dari indeks lebih kecil), baru perbarui terkecil. Kalau dibalik, a[j] − a[j] ikut terhitung dan syarat i < j dilanggar.

Pembahasan.

int cepat(int a[], int n) {
    int terbaik = -2000000000;
    int terkecil = a[0];
    for (int j = 1; j < n; j++) {
        if (a[j] - terkecil > terbaik) terbaik = a[j] - terkecil;
        if (a[j] < terkecil) terkecil = a[j];
    }
    return terbaik;
}

Hasil pengukuran pada n = 50.000 (komputer penulis):

Untuk n = 200.000, versi O(n²) memerlukan sekitar 16 kali lipat dari 0,57 detik — sekitar 9 detik, jauh melewati batas waktu. Versi O(n) tetap sepersekian milidetik. Inilah bentuk nyata tabel batasan Bab 10.

Uji. Program jawabannya mencetak sendiri hasil perbandingannya:

2000 uji cocok
lambat: 999886 (0.580913 detik)
cepat : 999886 (2.4e-05 detik)

Dua baris terakhir untuk n = 50.000. Jawabannya sama, tetapi versi O(n²) memerlukan sekitar 1,25 miliar pasangan sedangkan versi O(n) hanya 50.000 langkah — pada pengukuran ini sekitar dua puluh ribu kali lebih cepat. Inilah bentuk nilai sebagian yang dimaksud Bab 11: versi lambat tetap benar dan tetap bernilai pada subsoal kecil.

Kesalahan umum.

• Memperbarui terkecil sebelum menghitung selisih.
• Memberi nilai awal terbaik = 0. Untuk data menurun seperti 5 3 1, jawabannya negatif dan versi itu salah.

Latihan bergaya OSN — pembahasan

Berkas jawabannya ada di exercises/11/osn/solutions/.

Soal 1 — Tripel Berjumlah Nol

Hitung dulu. Banyaknya tripel posisi dari 500 data adalah 500 × 499 × 498 / 6 ≈ 2,07 × 10⁷. Di bawah 10⁸, jadi tiga perulangan bersarang muat. Diukur pada mesin penulis, jawaban di bawah selesai dalam 0,03 detik untuk N = 500.

Cara berpikir. Satu-satunya keputusan di sini adalah batas perulangan. Menulis ketiganya dari 0 sampai N akan menghitung setiap tripel enam kali dan juga menghitung tripel yang memakai posisi yang sama dua kali. Menulis j mulai dari i + 1 dan k mulai dari j + 1 menyelesaikan keduanya sekaligus, tanpa pembagian dan tanpa pemeriksaan tambahan.

Pembahasan.

long long banyak = 0;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
            if (a[i] + a[j] + a[k] == 0) banyak++;
        }
    }
}

Penjumlahan tiga bilangan sebesar 10⁹ mencapai 3 × 10⁹, jadi a harus long long. Kalau a bertipe int, penjumlahannya meluap dan tripel yang sebenarnya tidak berjumlah nol bisa ikut terhitung.

Uji.

Kasus ketiga berguna sebagai pemeriksaan batas perulangan: jawabannya harus 4, yaitu banyaknya cara memilih 3 posisi dari 4. Jawaban 24 berarti urutannya ikut terhitung; jawaban 64 berarti posisi yang sama boleh dipakai ulang.

Kesalahan umum.

• Memulai j dan k dari 0, sehingga tripel terhitung berkali-kali.
• Memakai int untuk data.
• Memakai pencacah int untuk hasil — pada N = 500 dengan data yang seluruhnya nol, jawabannya lebih dari 20 juta, masih muat di int, tetapi jarak amannya tipis.

Soal 2 — Himpunan Bagian Terdekat

Hitung dulu. N ≤ 20 berarti 2²⁰ = 1.048.576 himpunan bagian, dan menjumlahkan isi masing-masing memerlukan sampai 20 langkah — sekitar 2 × 10⁷ operasi. Muat. Diukur pada mesin penulis: 0,10 detik untuk N = 20.

Cara berpikir. Setiap himpunan bagian bisa diwakili satu bilangan bulat antara 0 dan 2^N − 1. Bit ke-i yang menyala berarti elemen ke-i ikut dipilih. Dengan begitu "mencoba semua himpunan bagian" menjadi perulangan biasa.

Dua hal yang perlu dibaca teliti dari soal. Pertama, himpunan bagian kosong boleh dipilih, jadi jawaban awalnya 0 dengan jarak S. Kedua, kalau ada seri, yang dipilih adalah total yang lebih kecil — syarat itu harus ditulis, tidak muncul dengan sendirinya.

Pembahasan.

long long terbaik = 0;                      // himpunan bagian kosong
long long selisihTerbaik = s;               // |0 - s|

for (int mask = 1; mask < (1 << n); mask++) {
    long long jumlah = 0;
    for (int i = 0; i < n; i++) {
        if (mask & (1 << i)) jumlah += a[i];
    }

    long long selisih = jumlah - s;
    if (selisih < 0) selisih = -selisih;

    if (selisih < selisihTerbaik ||
        (selisih == selisihTerbaik && jumlah < terbaik)) {
        selisihTerbaik = selisih;
        terbaik = jumlah;
    }
}

Jumlah 20 elemen bernilai 10⁹ mencapai 2 × 10¹⁰, dan S sendiri bisa 10¹⁸, jadi semuanya long long.

Uji.

Kasus ketiga: 3 berjarak 4 dari 7, dan 11 juga berjarak 4. Jawabannya 3.

Kesalahan umum.

• Memulai mask dari 1 tanpa menyiapkan himpunan bagian kosong sebagai jawaban awal, sehingga kasus kedua salah.
• Menulis 1 << i dengan i sampai 31 pada tipe int — untuk N ≤ 20 masih aman, tetapi kebiasaan 1LL << i lebih tahan saat batasannya dinaikkan.
• Lupa aturan seri, sehingga jawabannya bergantung pada urutan penelusuran.

Soal 3 — Tur Terpendek

Hitung dulu. Kota pertama dikunci sebagai titik berangkat, jadi yang dicoba adalah urutan N − 1 kota sisanya: 7! = 5.040 urutan untuk N = 8, masing-masing dihitung dalam 8 langkah. Sekitar 40.000 operasi — sangat ringan. Diukur pada mesin penulis: 0,004 detik.

Mengunci kota pertama bukan sekadar mempercepat: tanpa itu, setiap tur terhitung N kali, karena tur yang sama bisa ditulis mulai dari kota mana saja.

Cara berpikir. next_permutation dari <algorithm> mengubah sebuah vector menjadi urutan berikutnya menurut abjad, dan mengembalikan false kalau sudah urutan terakhir. Pola bakunya:

sort(v.begin(), v.end());
do {
    // periksa satu urutan
} while (next_permutation(v.begin(), v.end()));

Isian v di sini adalah nomor kota 1 sampai N − 1, yang memang sudah urut naik saat dibuat, jadi sort tidak diperlukan. Kalau data awalnya belum urut, sort wajib — tanpa itu sebagian urutan tidak pernah dicoba.

Pembahasan.

vector<int> urutan;
for (int i = 1; i < n; i++) urutan.push_back(i);

long long terbaik = -1;
do {
    long long total = 0;
    int sekarang = 0;
    for (int kota : urutan) {
        total += d[sekarang][kota];
        sekarang = kota;
    }
    total += d[sekarang][0];

    if (terbaik < 0 || total < terbaik) terbaik = total;
} while (next_permutation(urutan.begin(), urutan.end()));

Perhatikan total += d[sekarang][0] di akhir: kurirnya harus kembali, dan ruas terakhir itu sangat sering terlupa.

Uji.

Kasus kedua adalah pemeriksaan ruas pulang: jawabannya 10, bukan 5.

Kesalahan umum.

• Lupa menambahkan jarak kembali ke kota pertama.
• Mencoba semua N! urutan termasuk kota pertama. Jawabannya tetap benar, tetapi delapan kali lebih lambat dan lebih mudah salah tulis.
• Memulai terbaik dari 0, sehingga tidak pernah ada tur yang lebih kecil.

Kalau masih tersendat

• Tidak tahu apa yang harus dicoba → Bab 11, empat bentuknya: semua elemen, semua pasangan, semua himpunan bagian, semua urutan.
• Bingung pada mask dan operasi bit → Bab 11, tabel mask ↔︎ himpunan bagian dalam biner.
• Brute force-mu kehabisan waktu → Bab 11, langkah 2 dan 3: hitung dulu banyaknya kemungkinan, baru tulis kodenya.

Strategi lomba yang perlu dibiasakan: tulis brute force lebih dulu, amankan poin subsoal kecilnya, baru pikirkan penyelesaian penuh.