10. Menelusuri dan menghitung langkah

Dua keterampilan memisahkan peserta yang nilainya penuh dari yang nilainya setengah: bisa menelusuri algoritma dengan tangan untuk memastikan jawabannya benar, dan bisa menghitung langkahnya untuk memastikan programnya cukup cepat. Keduanya dikerjakan sebelum menekan tombol compile.

Menelusuri dengan tabel

Menelusuri berarti menjalankan algoritma di kertas, satu baris satu waktu, sambil mencatat isi setiap variabel. Buat satu kolom per variabel dan satu baris per langkah.

Algoritma yang ditelusuri:

BACA n              // n = 4
jumlah <- 0
i <- 1
SELAMA i <= n
    jumlah <- jumlah + i * i
    i <- i + 1
CETAK jumlah

Tabelnya:

Perhatikan: nilai i pada kolom pertama adalah nilai sesudah baris i <- i + 1 dijalankan. Tetapkan aturanmu sendiri lalu pakai terus, supaya tabelnya tidak membingungkan diri sendiri.

Empat aturan supaya tabel penelusuran benar-benar menangkap kesalahan:

1. Satu baris untuk setiap kali isi perulangan dijalankan, bukan satu baris per baris kode.
2. Satu kolom untuk setiap variabel yang berubah, ditambah satu kolom untuk hasil pemeriksaan syaratnya.
3. Tulis nilai apa adanya, termasuk kalau terlihat salah. Godaan terbesar saat menelusuri adalah menuliskan nilai yang seharusnya, bukan yang benar-benar dihasilkan langkah itu.
4. Jangan berhenti di putaran terakhir. Sebagian besar kesalahan satu langkah justru muncul pada pemeriksaan syarat yang terakhir, saat perulangan berhenti.

Kasus uji dan kasus tepi

Program yang benar untuk contoh di soal belum tentu benar. Uji juga kasus tepi, yaitu masukan di ujung batas:

Sebagian besar nilai yang hilang di OSN bukan karena algoritmanya salah, melainkan karena satu kasus tepi tidak pernah diuji.

Untuk setiap jenis soal, kasus tepinya bisa ditebak sebelum kodenya selesai:

Cara cepat membangkitkan kasus tepi: ambil batasan di soal, lalu coba nilai tepat di batas dan satu di dalam batas. Untuk 1 ≤ n ≤ 200.000, itu berarti n = 1, n = 2, dan n = 200.000.

Menghitung jumlah langkah

Hitung berapa kali bagian terdalam sebuah program dijalankan, sebagai fungsi dari n.

for (int i = 0; i < n; i++)              // n kali
    cout << a[i];

for (int i = 0; i < n; i++)              // n * n kali
    for (int j = 0; j < n; j++)
        ...

for (int i = 0; i < n; i++)              // n * (n-1) / 2 kali
    for (int j = i + 1; j < n; j++)
        ...

for (int i = 1; i <= n; i *= 2)          // log2(n) kali
    ...

Yang ditulis biasanya hanya bentuk pertumbuhannya, dengan mengabaikan angka pengali dan suku yang lebih kecil:

Alasan angka pengali diabaikan: ketika n membesar, bentuk pertumbuhannya yang menentukan. Program O(n²) dengan pengali kecil tetap kalah jauh dari program O(n log n) begitu n mencapai ratusan ribu.

Seberapa jauh, bisa dilihat dari tabel berikut. Angkanya jumlah langkah, bukan detik:

Perhatikan kolom O(n²): dari n = 1.000 ke n = 100.000, datanya menjadi 100 kali lipat tetapi pekerjaannya menjadi 10.000 kali lipat. Inilah sebabnya penyelesaian yang "cukup cepat" pada contoh kasus bisa sama sekali tidak selesai pada data sesungguhnya.

Cara cepat mengenali bentuk pertumbuhan tanpa menghitung: lihat apa yang terjadi kalau n digandakan.

Jumlah langkah beberapa operasi yang sudah kamu pakai:

Dari batasan ke pilihan algoritma

Komputer penilai mengerjakan kira-kira 10⁸ operasi sederhana per detik. Batas waktu soal biasanya 1 atau 2 detik. Dari sana, batasan n di soal langsung memberi tahu algoritma seperti apa yang dicari:

Angka 10⁸ per detik adalah perkiraan yang sengaja dibuat aman. Perulangan yang sangat sederhana bisa berjalan jauh lebih cepat dari itu, sedangkan langkah yang menyentuh memori secara melompat-lompat bisa jauh lebih lambat. Untuk memilih algoritma, perkiraan aman itulah yang dipakai.

Contoh membacanya: soal dengan n ≤ 200.000 hampir pasti tidak menginginkan perulangan bersarang. Kalau rencanamu berbentuk "periksa semua pasangan", berarti ada pengamatan yang belum ditemukan — misalnya "urutkan dulu", seperti pada contoh Bab 08.

Mengukur waktu sungguhan

Perkiraan di atas tetap perlu diperiksa. Cara termudah di komputer sendiri:

#include <ctime>

clock_t t0 = clock();
// ... bagian yang diukur ...
double detik = (double)(clock() - t0) / CLOCKS_PER_SEC;
cerr << detik << " detik\n";

Perhatikan cerr, bukan cout: keluaran cerr tidak ikut dinilai oleh penilai daring, jadi aman dipakai untuk pesan bantuan. Meski begitu, biasakan menghapusnya sebelum mengirim jawaban.

Ketika angka pengali ikut menentukan

Bentuk pertumbuhan menentukan pilihan algoritma, tetapi ada satu hal yang sering membuat penyelesaian O(n) yang benar tetap kehabisan waktu: kecepatan membaca masukan. Secara bawaan cin disetel agar bisa dipakai bersama scanf, dan penyesuaian itu memakan waktu. Dua baris di awal main mematikannya:

ios::sync_with_stdio(false);
cin.tie(nullptr);

Pada pengukuran membaca satu juta bilangan bulat, waktunya turun dari 0,21 detik menjadi 0,04 detik — sekitar lima kali lebih cepat, tanpa mengubah satu pun baris algoritma. Untuk soal dengan masukan ratusan ribu angka, biasakan menulis kedua baris itu.

Menguji dengan pembanding

Kalau sebuah penyelesaian cepat terasa meragukan, uji dengan penyelesaian lambat yang jelas benar:

1. Tulis versi lambat yang pasti benar (misalnya memeriksa semua pasangan).
2. Buat data acak berukuran kecil.
3. Jalankan keduanya, bandingkan keluarannya.
4. Ulangi ratusan kali. Begitu ada yang berbeda, kamu punya contoh kasus kecil yang bisa ditelusuri dengan tangan.

Kuncinya ada pada langkah 2: datanya harus kecil. Perbedaan yang ditemukan pada array berisi empat angka bisa ditelusuri dengan tangan dalam satu menit; perbedaan pada array berisi seratus ribu angka tidak memberi tahu apa pun.

for (int uji = 0; uji < 1000; uji++) {
    int n = rand() % 6 + 1;                  // 1 sampai 6 elemen
    for (int i = 0; i < n; i++) a[i] = rand() % 21 - 10;   // -10 sampai 10
    if (cepat(n) != lambat(n)) {
        cerr << "beda pada n=" << n << ":";
        for (int i = 0; i < n; i++) cerr << " " << a[i];
        cerr << "\n  cepat=" << cepat(n) << " lambat=" << lambat(n) << "\n";
        break;
    }
}

Cara ini menemukan bug yang tidak terlihat dengan membaca kode, dan ia juga satu-satunya cara praktis untuk menguji dugaan greedy di Bab 12. Contohnya ada di exercises/10/04-uji-banding.cpp.

Pekerjaan rumah

BACA n
a <- 0
b <- 1
UNTUK i DARI 1 SAMPAI n
    c <- a + b
    a <- b
    b <- c
CETAK a

Tips OSN

Batasan dibaca sebagai perintah, bukan keterangan. Sebelum memutuskan cara, pasangkan batasan terbesar pada soal dengan tabel ini. Angkanya memakai patokan 10⁸ operasi sederhana per detik.

Batasan N ≤ 200.000 yang muncul berulang-ulang di soal OSN adalah isyarat paling jelas: N² = 4 × 10¹⁰ tidak mungkin, jadi yang dicari penyelesaian satu kali baca atau satu kali urut.

Nyatakan biayanya sebelum mengetik. Tulis satu baris di kertas coretan: "N ≤ 2 × 10⁵, cara saya N², berarti 4 × 10¹⁰ — tidak muat". Kalimat sependek itu mencegah setengah jam mengetik jawaban yang sudah pasti kena Time Limit Exceeded.

Jawaban lambat tetap layak dikirim. Kalau soal dibagi menjadi subsoal, jawaban N² biasanya menyelesaikan subsoal berbatas kecil. Kirim dulu, baru perbaiki. Yang tidak boleh adalah kehabisan waktu tanpa mengirim apa pun.

Jawaban lambat juga alat penguji. Cara membandingkannya otomatis dibahas di bab ini: jalankan versi lambat dan versi cepat pada masukan acak yang sama, dan bandingkan keluarannya dengan diff. Kalau berbeda, kamu punya contoh kecil yang salah — jauh lebih berguna daripada vonis Wrong Answer tanpa keterangan.

Masukan besar perlu pembacaan cepat. Untuk N ratusan ribu ke atas, dua baris ini pantas menjadi kebiasaan di awal main:

ios::sync_with_stdio(false);
cin.tie(nullptr);

Setelah menulisnya, jangan mencampur cin dengan scanf dalam satu program.

Ukur, jangan menebak. clock() dari <ctime> cukup untuk mengukur bagian yang dicurigai lambat. Menebak bagian mana yang lambat hampir selalu meleset, dan mengoptimalkan bagian yang bukan penyebabnya tidak mengubah apa-apa.

Ringkasan

• Menelusuri dengan tabel memeriksa kebenaran; menghitung langkah memeriksa kecepatan. Keduanya dikerjakan sebelum compile.
• Tabel penelusuran: satu baris per putaran, satu kolom per variabel, tulis nilai apa adanya, dan jangan berhenti sebelum pemeriksaan terakhir.
• Kasus tepi yang wajib: n = 1, semua nilai sama, semua negatif, tidak ada jawaban, dan nilai terbesar sesuai batasan.
• Notasi O menyembunyikan angka pengali dan menyisakan bentuk pertumbuhannya. Cara cepat mengenalinya: lihat apa yang terjadi kalau n digandakan.
• Perkiraan aman: 10⁸ operasi sederhana per detik. Pakai tabel batasan untuk memilih algoritma sebelum menulis kode.
• ios::sync_with_stdio(false); cin.tie(nullptr); mempercepat pembacaan masukan besar tanpa mengubah algoritma.
• Penguji pembanding dengan data acak kecil menemukan bug yang tidak terlihat saat membaca kode.

Latihan bergaya OSN

Ketiga soal berikut punya jawaban langsung yang mudah ditulis dan pasti terlalu lambat. Sebelum mengetik, hitung dulu jumlah langkah jawaban langsung itu, lalu cari bentuk yang muat.

Kerangka ketiganya ada di exercises/10/osn/.

Soal 1 — Subarray Maksimum

Diberikan barisan N bilangan bulat. Pilih sepotong bagian yang letaknya berurutan dan tidak kosong, sehingga jumlah isinya sebesar mungkin. Tentukan jumlah itu.

Format masukan. Baris pertama berisi bilangan bulat N. Baris kedua berisi N bilangan bulat A₁ A₂ … A_N.

Format keluaran. Satu baris berisi jumlah terbesar yang bisa dicapai.

Batasan.

• 1 ≤ N ≤ 200.000
• −10⁹ ≤ Aᵢ ≤ 10⁹

Contoh masukan

8
-2 1 -3 4 -1 2 1 -5

Contoh keluaran

6

Penjelasan. Potongan 4 -1 2 1 berjumlah 6, dan tidak ada potongan lain yang lebih besar. Perhatikan bahwa potongannya tidak boleh kosong: kalau semua bilangannya negatif, jawabannya adalah bilangan negatif yang terbesar, bukan 0.

Kerangkanya: exercises/10/osn/01-subarray-maksimum.cpp

Soal 2 — Pasangan Berjumlah K

Diberikan N bilangan bulat dan sebuah bilangan K. Hitung ada berapa pasangan posisi (i, j) dengan i < j sehingga Aᵢ + A_j = K.

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

Format keluaran. Satu baris berisi banyaknya pasangan.

Batasan.

• 2 ≤ N ≤ 200.000
• 1 ≤ Aᵢ ≤ 10⁶
• 2 ≤ K ≤ 2 × 10⁶

Contoh masukan

5 7
1 6 3 4 2

Contoh keluaran

2

Penjelasan. Pasangannya adalah (1, 6) dan (3, 4). Angka 2 tidak punya pasangan karena 5 tidak ada dalam daftar. Yang dihitung adalah pasangan posisi: kalau masukannya 2 2 2 2 dengan K = 4, jawabannya 6, karena ada enam cara memilih dua posisi berbeda.

Kerangkanya: exercises/10/osn/02-pasangan-berjumlah.cpp

Soal 3 — Jumlah Rentang

Diberikan barisan N bilangan bulat dan Q pertanyaan. Setiap pertanyaan berisi dua nomor posisi L dan R; jawabannya adalah jumlah A_L sampai A_R, termasuk kedua ujungnya.

Format masukan. Baris pertama berisi dua bilangan bulat N dan Q. Baris kedua berisi N bilangan bulat. Q baris berikutnya masing-masing berisi dua bilangan bulat L dan R.

Format keluaran. Q baris, satu jawaban per pertanyaan.

Batasan.

• 1 ≤ N, Q ≤ 200.000
• −10⁹ ≤ Aᵢ ≤ 10⁹
• 1 ≤ L ≤ R ≤ N

Contoh masukan

5 3
1 2 3 4 5
1 5
2 3
4 4

Contoh keluaran

15
5
4

Penjelasan. Pertanyaan pertama menjumlahkan seluruh barisan, yang kedua menjumlahkan 2 + 3, dan yang ketiga hanya satu angka. Menjumlahkan ulang setiap pertanyaan memerlukan N × Q = 4 × 10¹⁰ penjumlahan — hitung sendiri sebelum memutuskan.

Kerangkanya: exercises/10/osn/03-jumlah-rentang.cpp

Bingung atau sudah selesai? Buka halaman pembahasan PR.