11. Brute force

Brute force berarti mencoba semua kemungkinan lalu memilih yang memenuhi syarat. Ia sering diremehkan, padahal di OSN brute force punya tiga kegunaan: menjadi jawaban penuh untuk soal berbatasan kecil, menjadi jawaban sebagian untuk soal berbatasan besar, dan menjadi pembanding untuk menguji penyelesaian yang lebih pintar.

Langkah menyusun brute force

1. Tentukan apa yang dicoba — semua elemen? semua pasangan? semua himpunan bagian? semua urutan?
2. Hitung berapa banyak kemungkinannya.
3. Bandingkan dengan tabel batasan di Bab 10.
4. Kalau muat, tulis perulangannya. Kalau tidak, cari pengamatan yang memangkas jumlah kemungkinan.

Langkah 2 dan 3 tidak boleh dilewati. Brute force yang tidak dihitung dulu adalah penyebab paling umum jawaban Time Limit Exceeded.

Banyaknya kemungkinan untuk keempat bentuk yang dibahas bab ini:

Betapa cepatnya dua baris terakhir membesar:

Itulah sebabnya batasan soal adalah petunjuk yang hampir tidak pernah berbohong: n ≤ 20 hampir selalu berarti "coba semua himpunan bagian", dan n ≤ 10 hampir selalu berarti "coba semua urutan".

Bentuk 1: semua elemen

Kemungkinannya n, jadi O(n). Ini brute force paling sederhana — dan sering sudah merupakan penyelesaian terbaik.

// cari elemen terbesar
int besar = a[0];
for (int i = 1; i < n; i++) if (a[i] > besar) besar = a[i];

Bentuk 2: semua pasangan

Kemungkinannya n(n−1)/2, jadi O(n²). Aman sampai sekitar n = 5.000.

// berapa pasangan yang jumlahnya k?
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++;

Perhatikan j = i + 1, bukan j = 0. Dengan begitu setiap pasangan dihitung sekali dan elemen tidak dipasangkan dengan dirinya sendiri. Untuk n = 4, pasangan yang diperiksa persis enam:

Kalau j dimulai dari 0, jumlahnya menjadi 16: setiap pasangan terhitung dua kali dan setiap elemen dipasangkan dengan dirinya sendiri. Pada soal "berapa banyak pasangan", dua kesalahan itu masing-masing mengubah jawaban.

Bentuk 3: semua himpunan bagian

Kalau setiap barang hanya punya dua keadaan — diambil atau tidak — maka n barang punya 2ⁿ kemungkinan. Aman sampai sekitar n = 22.

Cara menuliskannya memakai bilangan biner: bilangan mask dari 0 sampai 2ⁿ − 1 mewakili satu pilihan, dan bit ke-i menyatakan apakah barang ke-i diambil.

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];   // bit ke-i menyala
    }
    if (jumlah == target) banyak++;
}

Cara membacanya: setiap bilangan bulat sekaligus merupakan daftar "ya/tidak". Untuk n = 3 dan barang a = {5, 7, 2}, kedelapan nilai mask mewakili kedelapan pilihan:

Perhatikan bahwa bit paling kanan adalah bit ke-0, yaitu barang pertama. Kolom biner itu persis hitungan biner dari 0 sampai 7, jadi perulangan for (int mask = 0; mask < (1 << n); mask++) dijamin melewati setiap kemungkinan tepat satu kali — tidak ada yang terlewat dan tidak ada yang dobel. Itulah keunggulan cara ini dibanding menulis perulangan bersarang sebanyak n tingkat, yang bahkan tidak mungkin ditulis kalau n baru diketahui saat program berjalan.

Jumlah langkahnya n · 2ⁿ. Untuk n = 20 itu sekitar 21 juta — masih aman. Untuk n = 30 menjadi 32 miliar — tidak.

Bentuk 4: semua urutan

Kalau yang dicari susunan (siapa lebih dulu, jalur mana yang ditempuh), jumlah kemungkinannya n!. Aman hanya sampai sekitar n = 10 (10! = 3,6 juta).

next_permutation dari <algorithm> mengubah isinya menjadi urutan berikutnya menurut kamus, dan mengembalikan false begitu tidak ada lagi urutan sesudahnya. Untuk {0, 1, 2} urutan yang dihasilkannya:

012  021  102  120  201  210

Karena ia hanya melangkah "maju", datanya harus dimulai dalam keadaan terurut menaik — kalau tidak, sebagian urutan tidak pernah muncul:

#include <algorithm>

int p[] = {0, 1, 2, 3};
sort(p, p + n);
do {
    // p sekarang berisi satu urutan
} while (next_permutation(p, p + n));

Memangkas kemungkinan

Brute force tidak harus benar-benar memeriksa semuanya. Dua cara memangkas:

Berhenti lebih awal. Begitu jawaban sudah pasti, keluar.

for (long long i = 2; i * i <= n; i++)
    if (n % i == 0) return false;       // tidak perlu diteruskan

Menghitung sisanya, bukan mencarinya. Kalau dua di antara tiga nilai sudah dipilih, nilai ketiga sering bisa dihitung langsung — satu perulangan bersarang hilang.

// a + b + c = k, cari banyaknya tripel: cukup dua perulangan
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++) {
        int c = k - a[i] - a[j];
        // lalu cari c dengan cara yang cepat
    }

Nilai sebagian

Soal OSN sering berbatasan bertingkat, misalnya:

• Subsoal 1 (30 poin): n ≤ 20
• Subsoal 2 (30 poin): n ≤ 2.000
• Subsoal 3 (40 poin): n ≤ 200.000

Brute force O(2ⁿ) menjawab subsoal 1. Brute force O(n²) menjawab subsoal 1 dan 2. Enam puluh poin dari penyelesaian yang "bodoh" jauh lebih baik daripada nol poin dari penyelesaian pintar yang tidak selesai ditulis.

Contoh lengkap: jumlah himpunan bagian

Diberikan n barang dengan berat a[1..n] dan sebuah target k. Berapa banyak cara memilih sebagian barang (boleh nol barang) sehingga total beratnya tepat k? Batasan: n ≤ 20, a[i] ≤ 10⁹.

Berapa kemungkinannya? Setiap barang diambil atau tidak: 2²⁰ ≈ 1 juta. Setiap kemungkinan perlu n langkah untuk menjumlahkan: 21 juta. Masuk.

Kodenya:

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++;
}
cout << banyak << "\n";

Kalau batasannya n ≤ 40, cara ini mati — dan penyelesaiannya adalah membelah data menjadi dua bagian, masing-masing 2²⁰. Teknik itu di luar cakupan buku ini, tetapi pola pikirnya sama: hitung dulu, baru putuskan.

Pekerjaan rumah

Kesalahan yang paling sering

Tips OSN

Batasan kecil adalah undangan terbuka. Angka-angka berikut hampir selalu berarti "coba semua kemungkinan", dan penulis soal memang meletakkannya di situ supaya brute force muat:

Kalau batasannya terlihat "terlalu kecil", jangan curiga — itu justru jawabannya.

Brute force adalah jawaban yang sah, bukan jawaban memalukan. Pada soal bersubsoal, jawaban brute force menyelesaikan subsoal berbatas kecil dan memberi nilai nyata. Peserta yang menghabiskan seluruh waktunya mencari jawaban sempurna dan tidak mengirim apa pun mendapat nol.

Tulis brute force lebih dulu walaupun kamu tahu cara cepatnya. Ia menjadi pembanding untuk menguji jawaban cepat pada masukan acak, seperti pada bagian Menguji dengan pembanding di Bab 10. Banyak kesalahan halus pada jawaban cepat hanya bisa ditemukan dengan cara ini.

Susun perulangan supaya tidak menghitung dua kali. Untuk memilih pasangan atau tripel dari posisi yang berbeda, tulis j mulai dari i + 1 dan k mulai dari j + 1. Cara ini sekaligus menghindarkan pembagian di akhir dan menjamin setiap kombinasi terhitung tepat sekali.

Pangkas sedini mungkin. Pemeriksaan yang bisa dilakukan di perulangan luar jangan ditunda ke perulangan dalam. Memindahkan satu syarat dari tingkat terdalam ke tingkat kedua sering memotong waktu jalan sampai sepuluh kali lipat, tanpa mengubah jawabannya sama sekali.

Kenali batas atas jawaban sebelum memilih tipe. Brute force sering menjumlahkan sangat banyak kemungkinan. Jumlah tripel pada N = 500 saja sudah 20 juta; kalau yang dihitung nilainya, bukan cacahnya, long long hampir selalu diperlukan.

Ringkasan

• Brute force berarti mencoba semua kemungkinan; ia berguna sebagai jawaban penuh untuk batasan kecil, jawaban sebagian untuk batasan besar, dan pembanding untuk menguji penyelesaian cepat.
• Urutan kerjanya: tentukan apa yang dicoba, hitung banyaknya, bandingkan dengan tabel batasan Bab 10, baru tulis kodenya.
• Empat bentuk bakunya: semua elemen O(n), semua pasangan O(n²), semua himpunan bagian O(2ⁿ), semua urutan O(n!).
• Himpunan bagian ditulis dengan mask biner; 1 << n adalah 2ⁿ dan mask & (1 << i) memeriksa bit ke-i.
• Semua urutan dihasilkan next_permutation, dan datanya harus terurut lebih dulu.
• Pemangkasan bisa menghapus satu tingkat perulangan, tetapi tidak bisa mengubah 2ⁿ menjadi n². Kalau batasannya jauh di luar jangkauan, yang dibutuhkan ide lain — Bab 12 atau Bab 13.

Latihan bergaya OSN

Ketiga soal berikut adalah tiga bentuk brute force yang paling sering muncul: semua tripel, semua himpunan bagian, dan semua urutan. Perhatikan batasannya — masing-masing dipilih supaya tepat muat.

Kerangka ketiganya ada di exercises/11/osn/.

Soal 1 — Tripel Berjumlah Nol

Diberikan N bilangan bulat. Hitung ada berapa tripel posisi (i, j, k) dengan i < j < k sehingga Aᵢ + A_j + A_k = 0.

Format masukan. Baris pertama berisi bilangan bulat N. Baris kedua berisi N bilangan bulat.

Format keluaran. Satu baris berisi banyaknya tripel.

Batasan.

• 3 ≤ N ≤ 500
• −10⁹ ≤ Aᵢ ≤ 10⁹

Contoh masukan

6
-1 0 1 2 -1 -4

Contoh keluaran

3

Penjelasan. Tripel yang berjumlah nol adalah posisi (1, 2, 3) yang berisi −1, 0, 1; posisi (2, 3, 5) yang berisi 0, 1, −1; dan posisi (1, 4, 5) yang berisi −1, 2, −1. Yang dihitung adalah tripel posisi, jadi dua tripel yang isinya sama tetapi posisinya berbeda dihitung dua kali.

Kerangkanya: exercises/11/osn/01-tripel-nol.cpp

Soal 2 — Himpunan Bagian Terdekat

Seorang panitia punya N kardus dengan berat berbeda dan ingin memuat sebagian ke dalam mobil yang daya angkutnya kira-kira S. Ia boleh memilih kardus mana pun, termasuk tidak memilih sama sekali.

Tentukan total berat yang paling dekat ke S — boleh kurang, boleh lebih. Kalau ada dua pilihan yang jaraknya ke S sama, pilih total berat yang lebih kecil.

Format masukan. Baris pertama berisi dua bilangan bulat N dan S. Baris kedua berisi N bilangan bulat.

Format keluaran. Satu baris berisi total berat yang paling dekat ke S.

Batasan.

• 1 ≤ N ≤ 20
• 1 ≤ S ≤ 10¹⁸
• 1 ≤ Aᵢ ≤ 10⁹

Contoh masukan

4 10
3 34 4 12

Contoh keluaran

12

Penjelasan. Total yang mungkin antara lain 0, 3, 4, 7, 12, 15, 16, dan seterusnya. Yang paling dekat ke 10 adalah 12, yang berjarak 2; pilihan 7 berjarak 3.

Kerangkanya: exercises/11/osn/02-himpunan-terdekat.cpp

Soal 3 — Tur Terpendek

Seorang kurir harus berangkat dari kota pertama, mengunjungi semua kota tepat satu kali, lalu kembali ke kota pertama. Jarak antar kota diberikan dalam bentuk tabel. Tentukan total jarak terpendek yang mungkin.

Format masukan. Baris pertama berisi bilangan bulat N. N baris berikutnya masing-masing berisi N bilangan bulat; bilangan ke-j pada baris ke-i adalah jarak dari kota ke-i ke kota ke-j.

Format keluaran. Satu baris berisi total jarak terpendek.

Batasan.

• 2 ≤ N ≤ 8
• 0 ≤ jarak ≤ 1000, dan jarak dari sebuah kota ke dirinya sendiri adalah 0.

Contoh masukan

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

Contoh keluaran

80

Penjelasan. Salah satu tur terpendek adalah kota 1 → 2 → 4 → 3 → 1, dengan total 10 + 25 + 30 + 15 = 80.

Kerangkanya: exercises/11/osn/03-tur-terpendek.cpp

Bingung atau sudah selesai? Buka halaman pembahasan PR.