10. Menelusuri dan menghitung langkah — Pembahasan PR

Soal 1 dan 2 dikerjakan di kertas. Berkas .cpp untuk soal 3 sampai tantangan ada di exercises/10/homework/solutions/.

Halaman ini dibuka sesudah mencoba sendiri. Untuk soal kertas, tulis dulu jawabanmu, baru bandingkan — membaca jawaban orang lain terasa jelas padahal belum tentu bisa diulang sendiri. Bagian Uji berisi masukan dan keluaran yang sudah diperiksa untuk soal berkode.

Menjalankan salah satu jawabannya:

g++ -std=c++17 -O2 -o jawab exercises/10/homework/solutions/03-kasus-tepi.cpp
./jawab

Soal 1 — Tabel penelusuran

Soal. Telusuri algoritma tiga baris di dalam perulangan untuk n = 5.

Cara berpikir. Ada tiga variabel yang berubah, dan urutannya penting: c dihitung dulu dari nilai a dan b yang lama, baru a dan b digeser. Karena itu tabelnya perlu kolom c.

Jawaban.

Keluarannya 5. Algoritma ini menghitung suku ke-n barisan Fibonacci — sama dengan fib_cepat di Bab 06.

Kesalahan umum.

• Memperbarui a lebih dulu, lalu memakai a yang baru untuk menghitung b. Hasilnya menjadi deret pangkat dua, bukan Fibonacci.
• Mencetak b, bukan a. Nilainya selalu satu suku terlalu jauh.

Soal 2 — Pilih algoritma

Cara berpikir. Pakai tabel di bab ini terbalik: dari batasan n, cari jumlah langkah yang masih di bawah kira-kira 10⁸.

Jawaban.

a. n ≤ 18 → aman sampai O(2ⁿ) (2¹⁸ ≈ 262.000), bahkan O(n · 2ⁿ). Contoh: mencoba semua himpunan bagian dari 18 barang untuk mencari kombinasi terbaik (Bab 11).

b. n ≤ 2.000 → aman sampai O(n²) (4 juta). Contoh: memeriksa semua pasangan, atau tabel dynamic programming berukuran n × n (Bab 13).

c. n ≤ 300.000 → aman sampai O(n log n) (sekitar 5,5 juta). Contoh: sort lalu satu penelusuran, seperti penyelesaian greedy di Bab 12. O(n²) berarti 9 × 10¹⁰ langkah: jauh terlalu lambat.

d. n ≤ 10¹² → nilainya terlalu besar untuk ditelusuri satu per satu. Yang aman O(√n) (10⁶ langkah, misalnya uji prima dengan cara akar) atau O(log n) (pangkat modulo cepat, Bab 14).

Kesalahan umum.

• Menjawab berdasarkan besarnya angka n saja tanpa mengalikan dengan jumlah langkah per elemen. n ≤ 300.000 dengan O(n) di dalam setiap kasus uji, dan ada 100 kasus uji, berarti 3 × 10⁷ — masih aman, tetapi perlu dihitung.

Soal 3 — Perbaiki kasus tepi

Soal. Program rata-rata bilangan positif yang gagal di tiga kasus tepi.

Cara berpikir. Jalankan dulu tiga kasus tepi itu sebelum membaca kode: hasilnya langsung menunjukkan letak masalahnya. n = 1 memberi jawaban yang jelas salah, data tanpa bilangan positif memberi nan atau inf.

Jawaban.

1. Perulangan dimulai dari i = 1, sehingga a[0] tidak pernah diperiksa. Untuk n = 1, tidak ada data yang diproses sama sekali.
2. Pembagian dengan banyak tanpa memeriksa banyak == 0. Pembagian nol pada double menghasilkan nan atau inf, bukan pesan error.
3. Penampung jumlah bertipe int. Untuk 100.000 bilangan bernilai 10⁹, jumlahnya 10¹⁴ dan meluap.

Pembahasan.

long long jumlah = 0;
int banyak = 0;

for (int i = 0; i < n; i++) {
    if (a[i] > 0) {
        jumlah += a[i];
        banyak++;
    }
}

double rata = (banyak == 0) ? 0.0 : (double)jumlah / banyak;
cout << fixed << setprecision(2) << rata << "\n";

Uji.

Baris ketiga adalah kesalahan yang paling berbahaya dari ketiganya: tanpa pemeriksaan banyak == 0, programnya membagi dengan nol dan mencetak nan atau inf — dan di penilai daring itu dinilai salah, bukan Runtime Error, sehingga penyebabnya lebih sulit dilacak.

Kesalahan umum.

• Memperbaiki hanya satu dari tiga. Kasus tepi diperiksa satu per satu, bukan sekaligus.
• Memakai if (banyak > 0) untuk mencetak, tetapi lupa mencetak apa pun ketika banyak == 0. Penilai menganggap keluaran kosong sebagai salah.

Soal 4 — Hitung langkahnya

Jawaban.

Perbandingan inilah cara memeriksa dugaan tanpa menghitung rumus: kalau n digandakan dan jumlah langkahnya ikut dua kali lipat, bentuknya linear; kalau menjadi empat kali, kuadratik; kalau hanya bertambah satu, logaritmik.

Uji. Jalankan untuk n = 100 lalu n = 200:

A O(n)       : 100        A O(n)       : 200
B O(n^2)     : 10000      B O(n^2)     : 40000
C O(log n)   : 7          C O(log n)   : 8
D O(n log n) : 700        D O(n log n) : 1600

Bandingkan kolom kiri dan kanan: A menjadi dua kali lipat, B empat kali lipat, C bertambah satu, dan D sedikit di atas dua kali lipat. Inilah tabel "kalau n digandakan" di Bab 10, tetapi kali ini dihitung oleh programnya sendiri, bukan diperkirakan.

Kesalahan umum.

• Menebak potongan D sebagai O(n²). Perulangan dalamnya mengali dua, bukan menambah satu, sehingga hanya berjalan log₂ n kali.
• Memakai int untuk pencacah O(n²) dengan n besar.

Tantangan — Penguji pembanding

Soal. Temukan bug di fungsi cepat memakai penguji acak.

Cara berpikir. Inti cara ini adalah data kecil. Kalau n dibatasi sampai 6 dan nilainya −10 sampai 10, contoh kasus yang gagal cukup kecil untuk ditelusuri dengan tangan. Membuat data acak berukuran 100.000 memang lebih mirip soal sungguhan, tetapi tidak membantu mencari bug.

srand(12345) membuat urutan angka acaknya sama setiap kali dijalankan, sehingga kasus yang gagal bisa diulang.

Bug-nya. Batas perulangan i < n - 1 di cepat() melewatkan elemen terakhir. Penguji menemukannya pada percobaan pertama dengan data 4 4 0 -4: jawaban benar 8, jawaban cepat() 4, karena -4 tidak pernah diperiksa.

Pembahasan.

for (int uji = 1; uji <= 1000; uji++) {
    int n = rand() % 6 + 1;
    int a[10];
    for (int i = 0; i < n; i++) a[i] = rand() % 21 - 10;

    if (lambat(a, n) != cepat(a, n)) {
        cout << "berbeda: n = " << n << "\n";
        for (int i = 0; i < n; i++) cout << a[i] << " ";
        cout << "\n";
        break;
    }
}

Perbaikannya satu karakter: i < n - 1 menjadi i < n.

Uji. Program jawabannya mencetak:

versi lama gagal pada uji ke-1, n = 4
4 4 0 -4
lambat = 8, cepat_bug = 4
versi perbaikan cocok pada 1000 uji

Perhatikan betapa kecil kasus penyangkalnya: empat angka. Itu memang tujuan penguji pembanding — bukan sekadar memberi tahu bahwa ada bug, melainkan memberi kasus terkecil yang bisa ditelusuri dengan tangan.

Telusuri sendiri 4 4 0 -4. Nilai terbesarnya 4, terkecilnya −4, jadi selisih terbesarnya 4 − (−4) = 8. Versi ber-bug berhenti di i < n - 1 sehingga hanya melihat 4 4 0: terbesar 4, terkecil 0, selisih 4. Sekali dilihat pada data sekecil ini, letak kesalahannya langsung jelas — sedangkan pada data berisi seratus ribu angka, yang terlihat hanya dua bilangan besar yang berbeda tanpa petunjuk apa pun.

Kesalahan umum.

• Membandingkan dua fungsi yang sama-sama ditulis dengan asumsi yang sama. Versi lambat harus ditulis sepolos mungkin — periksa semua kemungkinan — supaya kebenarannya tidak diragukan.
• Lupa break setelah menemukan perbedaan, sehingga layar penuh keluaran dan kasus pertamanya tidak terlihat.

Latihan bergaya OSN — pembahasan

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

Soal 1 — Subarray Maksimum

Hitung dulu. Jawaban langsungnya: coba semua pasangan ujung kiri dan ujung kanan, lalu jumlahkan isinya. Itu N² / 2 potongan, dan menjumlahkan isi setiap potongan membuatnya N³. Dengan sedikit perbaikan — menambahkan satu elemen sekaligus saat ujung kanan bergeser — biayanya turun menjadi N² = 4 × 10¹⁰ untuk N = 200.000. Masih jauh terlalu besar.

Angka sesungguhnya, diukur dengan clock() pada mesin penulis (g++ 13, -O2), memakai versi N²:

Perhatikan polanya: N dilipatduakan, waktunya melipat empat. Itu tanda khas N². Versi satu kali baca di bawah menyelesaikan N = 200.000 dalam 0,0003 detik pada mesin yang sama.

Cara berpikir. Kuncinya satu pertanyaan: berapa jumlah terbesar dari potongan yang berakhir tepat di posisi i? Jawabannya hanya dua kemungkinan — potongan itu hanya berisi A[i] sendiri, atau A[i] disambung ke potongan terbaik yang berakhir di posisi sebelumnya. Ambil yang lebih besar.

Kalau jawaban untuk setiap posisi sudah diketahui, jawaban soalnya adalah yang terbesar di antara semuanya. Keduanya bisa dihitung dalam satu kali baca, tanpa menyimpan data sama sekali.

Cara ini dikenal sebagai algoritma Kadane, dan sebenarnya adalah bentuk paling sederhana dari dynamic programming di Bab 13.

Pembahasan.

long long terbaik = 0, sampaiSini = 0;

for (int i = 0; i < n; i++) {
    long long x;
    cin >> x;

    if (i == 0) {
        sampaiSini = x;
        terbaik = x;
    } else {
        if (sampaiSini + x > x) sampaiSini = sampaiSini + x;
        else sampaiSini = x;

        if (sampaiSini > terbaik) terbaik = sampaiSini;
    }
}

cout << terbaik << "\n";

Elemen pertama ditangani terpisah supaya terbaik tidak pernah bermula dari 0 — kalau bermula dari 0, jawabannya salah pada barisan yang seluruhnya negatif.

Uji.

Kesalahan umum.

• Memulai terbaik dari 0, sehingga barisan yang seluruhnya negatif dijawab 0. Ini kesalahan nomor satu pada soal ini.
• Memakai int untuk penjumlahan. 200.000 × 10⁹ = 2 × 10¹⁴.
• Mengosongkan sampaiSini menjadi 0 ketika negatif, lalu mencetak terbaik yang tidak pernah diperbarui pada kasus semua negatif.

Soal 2 — Pasangan Berjumlah K

Hitung dulu. Memeriksa semua pasangan adalah N² / 2 = 2 × 10¹⁰ perbandingan. Tidak muat.

Cara berpikir. Petunjuknya ada pada batasan nilai: Aᵢ ≤ 10⁶, jauh lebih kecil daripada ruang pasangan. Jadi pakai array pencacah seperti di Bab 07, lalu balik pertanyaannya: untuk setiap nilai v yang muncul, pasangannya harus bernilai K − v. Banyaknya pasangan yang terbentuk adalah cacah[v] × cacah[K − v].

Dua penyesuaian:

• Setiap pasangan terhitung dua kali, sekali dari sisi v dan sekali dari sisi K − v. Karena itu hasilnya dibagi dua di akhir.
• Kalau v dan K − v bernilai sama, dua angka yang dipilih berasal dari kotak yang sama, jadi banyaknya pasangan cacah[v] × (cacah[v] − 1) — dan pembagian dua di akhir membuatnya menjadi rumus kombinasi yang benar.

Pembahasan.

const int BATAS = 1000000;
long long cacah[BATAS + 1];          // di luar main: terlalu besar untuk stack

// ... baca data, cacah[x]++ ...

long long hasil = 0;
for (int v = 1; v <= BATAS; v++) {
    if (cacah[v] == 0) continue;

    long long pasangan = k - v;
    if (pasangan < 1 || pasangan > BATAS) continue;

    if (pasangan == v) hasil += cacah[v] * (cacah[v] - 1);
    else hasil += cacah[v] * cacah[pasangan];
}

cout << hasil / 2 << "\n";

Pemeriksaan pasangan < 1 || pasangan > BATAS wajib: tanpa itu, K yang besar membuat program membaca cacah di luar batas array.

Uji.

Jumlah pasangan pada kasus terburuk — 200.000 angka yang semuanya sama — mencapai sekitar 2 × 10¹⁰, jadi penampungnya harus long long.

Kesalahan umum.

• Lupa membagi dua, sehingga setiap jawaban menjadi dua kali lipat.
• Memakai cacah[v] * cacah[v] untuk kasus v = K − v, yang ikut menghitung "pasangan" satu angka dengan dirinya sendiri.
• Mendeklarasikan long long cacah[1000001] di dalam main. Ukurannya 8 MB, biasanya melebihi stack, dan programnya berhenti sebelum baris pertama.
• Memakai int untuk hasil.

Soal 3 — Jumlah Rentang

Hitung dulu. Menjumlahkan ulang setiap pertanyaan memerlukan sampai N penjumlahan per pertanyaan, jadi N × Q = 4 × 10¹⁰. Tidak muat.

Cara berpikir. Semua pertanyaan menanyakan hal yang mirip, dan jawabannya bisa disiapkan sekali di depan. Buat pre[i] = jumlah A₁ sampai Aᵢ, dengan pre[0] = 0. Maka jumlah A_L sampai A_R adalah pre[R] − pre[L−1]: seluruh awalan sampai R, dikurangi bagian yang tidak diminta.

Biayanya menjadi N untuk menyiapkan ditambah satu pengurangan per pertanyaan. Teknik ini disebut jumlah awalan (prefix sum) dan muncul sangat sering di soal OSN.

Penomoran mulai 1 dipakai di sini justru untuk menghindari kesalahan: pre[0] = 0 membuat L = 1 tidak perlu ditangani sebagai kasus khusus.

Pembahasan.

vector<long long> pre(n + 1, 0);
for (int i = 1; i <= n; i++) {
    long long x;
    cin >> x;
    pre[i] = pre[i - 1] + x;
}

for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    cout << pre[r] - pre[l - 1] << "\n";
}

Dengan Q sampai 200.000 baris keluaran, dua baris ios::sync_with_stdio dan cin.tie di awal main berpengaruh nyata, dan endl harus diganti "\n".

Uji. Untuk contoh soal, keluarannya 15, 5, 4. Tambahkan dua uji sendiri: L = R = 1 (satu elemen di ujung kiri) dan L = 1, R = N (seluruh barisan), karena keduanya menyentuh pre[0] dan pre[n].

Kesalahan umum.

• Menulis pre[r] - pre[l], yang membuang satu elemen di ujung kiri.
• Membuat pre berukuran n, sehingga pre[n] berada di luar batas.
• Memakai int untuk pre. 200.000 × 10⁹ = 2 × 10¹⁴.
• Menyimpan array aslinya juga padahal tidak pernah dipakai lagi — tidak salah, tetapi memori dan waktu bacanya bisa dihemat.

Kalau masih tersendat

• Tidak tahu di baris mana kesalahannya → Bab 10, bagian Menelusuri dengan tabel dan keempat aturannya.
• Jawaban benar tetapi Time Limit Exceeded → Bab 10, tabel Dari batasan ke pilihan algoritma.
• Jawaban benar di komputermu tetapi salah di penilai → Bab 10, tabel kasus tepi.

Dua keterampilan bab ini dipakai di seluruh sisa buku: menelusuri untuk memeriksa kebenaran, dan menghitung langkah untuk memeriksa kecepatan.