08. Apa itu berpikir komputasional

Bagian 1 melatih tangan: sintaks, compile, array. Bagian ini melatih kepala. Berpikir komputasional adalah cara menyusun sebuah persoalan sehingga komputer bisa menyelesaikannya — dan di OSN, bagian inilah yang menentukan nilai, bukan kecepatan mengetik.

Ada empat kebiasaan yang membentuknya.

1. Dekomposisi: memecah menjadi bagian kecil

Persoalan besar jarang bisa diselesaikan sekaligus. Pecah menjadi langkah-langkah yang masing-masing bisa diuji sendiri.

Contoh soal: diberikan n bilangan, cetak berapa banyak pasangan berbeda yang jumlahnya sama dengan k.

Pecahannya:

1. Baca n, k, dan n bilangan. (Sudah bisa sejak Bab 07.)
2. Tentukan apa arti "pasangan berbeda" — apakah (i, j) dan (j, i) dihitung sekali atau dua kali?
3. Periksa semua pasangan dan cacah yang jumlahnya k.
4. Cetak hasil cacahan.

Setelah dipecah, tidak satu pun langkah yang sulit. Kesulitan soal biasanya terletak pada langkah 2 dan 3, bukan pada kodenya.

Dekomposisi yang baik menghasilkan langkah-langkah yang bisa diuji sendiri-sendiri. Perhatikan bahwa langkah 1 sudah bisa dijalankan dan diperiksa sebelum langkah 3 ditulis sama sekali:

int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i];
cerr << "terbaca: n=" << n << " k=" << k << " a[0]=" << a[0] << "\n";

Kebiasaan ini — menjalankan program yang masih setengah jadi untuk memastikan bagian yang sudah ada benar — menghemat banyak waktu saat ada yang salah, karena kamu tahu persis di bagian mana kesalahannya belum mungkin ada.

2. Pengenalan pola: mencari yang berulang

Setelah mengerjakan banyak soal, bentuk yang sama muncul berkali-kali:

Mengenali pola bukan berarti menghafal kode. Artinya, ketika membaca soal baru, kamu langsung teringat pada soal lama yang bentuknya sama.

Tabel itu tumbuh sendiri seiring latihan, dan cara menumbuhkannya sederhana: setiap kali selesai satu soal, tulis satu baris di buku catatanmu berisi bentuk kalimat soalnya dan alat yang dipakai. Setelah lima puluh soal, catatan itu jauh lebih berguna daripada lima puluh berkas kode, karena yang dicari saat lomba adalah idenya, bukan kodenya.

3. Abstraksi: membuang yang tidak penting

Soal OSN sering dibungkus cerita: pedagang, kue, kereta api, tanaman. Tugas pertama adalah membuang ceritanya dan menyisakan intinya.

Bu Dengklek punya n ember berisi ikan. Ember ke-i berisi a[i] ikan. Ia ingin memindahkan seluruh ikan ke satu ember, dan setiap perpindahan satu ikan memerlukan satu detik. Berapa detik paling sedikit yang dibutuhkan?

Buang ceritanya: diberikan n bilangan, berapa jumlah seluruhnya dikurangi nilai terbesar? Setelah diabstraksikan, jawabannya dua baris kode.

Beberapa contoh lain, cerita dibuang, intinya disisakan:

4. Algoritma: urutan langkah yang pasti

Algoritma adalah urutan langkah yang jelas, berhingga, dan menghasilkan jawaban yang sama setiap kali dijalankan pada masukan yang sama. "Cari yang paling bagus" bukan algoritma. "Telusuri seluruh data, simpan nilai terbesar yang pernah dilihat, cetak nilai itu" adalah algoritma.

Tiga sifat yang wajib dimiliki sebuah algoritma:

Satu algoritma yang sama bisa ditulis dalam bahasa apa pun — Indonesia, flowchart, pseudocode, C++. Yang dinilai OSN adalah algoritmanya; C++ hanya alat untuk menjalankannya.

Cara menuliskannya dibahas di Bab 09 (flowchart dan pseudocode), dan cara memeriksanya di Bab 10.

Membaca soal OSN

Soal lomba hampir selalu punya bagian yang sama. Biasakan membacanya dengan urutan berikut — bukan dari atas ke bawah:

1. Format masukan dan keluaran. Ini menentukan bentuk kodemu.
2. Batasan. Ini menentukan algoritma apa yang boleh dipakai. n ≤ 1000 dan n ≤ 1.000.000 adalah dua soal yang berbeda.
3. Contoh kasus. Ini memastikan pemahamanmu benar. Kerjakan dengan tangan sebelum menulis kode.
4. Ceritanya. Dibaca terakhir, untuk mengisi detail yang belum jelas.

Contoh potongan soal dan apa yang seharusnya kamu simpulkan dari setiap bagiannya:

Masukan. Baris pertama berisi dua bilangan bulat n dan k. Baris kedua berisi n bilangan bulat a₁ … aₙ. Keluaran. Satu bilangan bulat, yaitu jawabannya. Batasan. 1 ≤ n ≤ 200.000, 1 ≤ aᵢ ≤ 10⁹.

Yang langsung diketahui bahkan sebelum ceritanya dibaca:

• Bentuk kodenya: cin >> n >> k; lalu satu perulangan membaca n angka.
• Keluarannya satu baris satu angka — tanpa kalimat, tanpa satuan.
• n sampai 200.000 berarti perulangan bersarang tidak mungkin; yang dicari sekitar O(n log n) (Bab 10).
• aᵢ sampai 10⁹ dan bisa dijumlahkan sebanyak 200.000 kali, jadi penampung jumlahnya harus long long.
• n bisa bernilai 1 — kasus tepi yang wajib diuji.

Lima kesimpulan itu diperoleh dari membaca dua paragraf pendek, sebelum memikirkan idenya sama sekali.

Contoh lengkap: dari soal ke rencana

Kue Bu Dengklek. Bu Dengklek membuat n kue dengan tingkat kemanisan a[1..n]. Ia ingin memilih dua kue berbeda sehingga selisih kemanisannya sekecil mungkin. Cetak selisih terkecil itu. Batasan: 2 ≤ n ≤ 200.000, 1 ≤ a[i] ≤ 10⁹.

Abstraksi. Diberikan n bilangan, cetak selisih terkecil antara dua bilangan yang berbeda posisi.

Rencana pertama (langsung). Periksa semua pasangan, catat selisih terkecil. Jumlah pasangannya sekitar n²/2 — untuk n = 200.000 itu 2 × 10¹⁰ langkah. Terlalu lambat.

Pengenalan pola. "Selisih terkecil" mengingatkan pada data yang berurutan: pada barisan terurut, dua bilangan yang paling mirip pasti bertetangga. Kalau tidak bertetangga, pasti ada bilangan di antaranya yang lebih mirip dengan salah satunya.

Rencana kedua. Urutkan (n log n), lalu telusuri sekali sambil membandingkan tiap elemen dengan tetangga di depannya (n). Total sekitar 3,5 juta langkah untuk n = 200.000. Cukup cepat.

Dekomposisi. (1) baca data, (2) sort, (3) telusuri pasangan bertetangga sambil menyimpan selisih terkecil, (4) cetak.

Perhatikan bahwa seluruh pemikiran di atas terjadi sebelum menulis kode, dan kodenya sendiri hanya sepuluh baris.

Pekerjaan rumah

Daftar periksa sebelum menulis kode

Lima pertanyaan ini dijawab di kertas, berurutan. Jawaban yang macet di salah satu nomor berarti belum waktunya menyentuh papan ketik:

1. Bisakah soal ini kutulis ulang sebagai "diberikan ... cetak ..."?
2. Apa keluarannya untuk contoh kasus di soal, kalau kukerjakan dengan tangan? Apakah hasilnya cocok?
3. Apa rencanaku, dalam satu kalimat?
4. Berapa langkah yang dikerjakan rencana itu untuk n terbesar di batasan, dan apakah muat dalam batas waktu?
5. Kasus tepi apa yang mungkin merusaknya — n = 1, semua nilai sama, nilai terbesar sesuai batasan?

Nomor 2 adalah yang paling sering dilewati dan paling sering menyelamatkan. Mengerjakan contoh kasus dengan tangan sering memperlihatkan bahwa pemahamanmu tentang soal itu keliru — dan itu jenis kesalahan yang tidak bisa diperbaiki dengan menyunting kode.

Tips OSN

Soal OSN sengaja dibungkus cerita. Nama tokoh, latar, dan satuan yang dipakai hampir selalu tidak berpengaruh pada jawabannya. Langkah pertama yang terlatih adalah membuang bungkusnya: tulis ulang soal menjadi satu kalimat "diberikan ..., cetak ...". Kalau kalimat itu tidak bisa ditulis, soalnya belum dimengerti — dan menulis kode sebelum itu hampir selalu berakhir dengan membuang seluruh kode.

Kerjakan contoh soal dengan tangan sebelum menulis kode. Contoh pada soal bukan sekadar pelengkap: ia satu-satunya tempat maksud penulis soal bisa diperiksa. Kalau hasil hitungan tanganmu berbeda dengan contoh, berarti pemahamanmu yang salah, bukan contohnya.

Batasan menentukan bentuk penyelesaian, bukan kecepatan kode. Urutan berpikir yang benar:

1. Baca batasannya.
2. Hitung berapa langkah yang dibolehkan (sekitar 10⁸ per detik).
3. Baru pilih cara.

Batasan 10¹⁸ tidak pernah berarti "tulis perulangan yang cepat"; ia berarti "jangan ada perulangan sepanjang itu". Soal Permen Berputar di bawah adalah contoh yang paling jelas: simulasi membagikan permen satu per satu adalah jawaban yang benar sekaligus jawaban yang mustahil dijalankan.

Tanyakan: apa yang benar-benar perlu diingat? Banyak soal yang terlihat menuntut penyimpanan seluruh data sebenarnya hanya memerlukan satu atau dua penampung berjalan. "Berapa kali rekor dipecahkan" tidak memerlukan seluruh daftar waktu — cukup catatan terbaik sejauh ini. Pertanyaan ini sering mengubah soal yang tampak berat menjadi satu perulangan.

Pisahkan tiga pertanyaan yang berbeda. Saat membaca soal, jawab ketiganya secara terpisah:

Kalau buntu, kerjakan versi kecilnya dulu. Menulis jawaban lambat yang pasti benar untuk N kecil memberi dua hal sekaligus: nilai dari subsoal berbatas kecil, dan alat untuk memeriksa jawaban cepat yang ditulis kemudian. Cara membandingkan keduanya secara otomatis dibahas di Bab 11.

Ringkasan

• Dekomposisi: pecah soal menjadi langkah yang masing-masing bisa diuji sendiri; langkah yang masih samar berarti belum selesai dipecah.
• Pengenalan pola: kumpulkan pasangan "bentuk kalimat soal → alat" seiring latihan. Pola memberi dugaan awal; batasan yang memutuskan.
• Abstraksi: buang ceritanya, tulis ulang sebagai "diberikan ... cetak ...".
• Algoritma: urutan langkah yang jelas, berhingga, dan menentukan.
• Baca soal dengan urutan: format masukan-keluaran, batasan, contoh kasus, baru ceritanya.
• Kerjakan contoh kasus dengan tangan sebelum menulis kode.

Latihan bergaya OSN

Ketiga soal berikut sengaja ditulis berbelit seperti soal sungguhan. Sebelum menulis kode, tulis dulu ulang masing-masing menjadi satu kalimat "diberikan ..., cetak ...".

Kerangka ketiganya ada di exercises/08/osn/.

Soal 1 — Panen Mangga

Pak Dengklek punya kebun mangga dan sebuah gudang yang mula-mula kosong. Selama N hari berturut-turut ia memetik mangga: pada hari ke-i ia memetik Aᵢ buah dan memasukkannya ke gudang.

Pak Dengklek malas pergi ke pasar, jadi ia hanya berjualan kalau isi gudangnya sudah banyak. Aturannya: setiap sore, kalau isi gudang sudah mencapai K buah atau lebih, seluruh isinya dibawa ke pasar dan habis terjual pada hari itu juga, sehingga gudang kembali kosong.

Tentukan berapa hari Pak Dengklek pergi ke pasar dan berapa mangga yang tersisa di gudang setelah hari ke-N.

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

Format keluaran. Satu baris berisi dua bilangan bulat: banyaknya hari penjualan dan sisa mangga di gudang.

Batasan.

• 1 ≤ N ≤ 200.000
• 1 ≤ K ≤ 10⁹
• 0 ≤ Aᵢ ≤ 10⁹

Contoh masukan

5 10
3 4 5 2 9

Contoh keluaran

2 0

Penjelasan. Isi gudang berturut-turut 3, 7, lalu 12 — pada hari ketiga isinya mencapai 10, jadi dijual dan gudang kosong. Hari keempat 2, hari kelima 11, dijual lagi. Dua hari penjualan, gudang berakhir kosong.

Kerangkanya: exercises/08/osn/01-panen-mangga.cpp

Soal 2 — Rekor Baru

Sebuah lomba lari diikuti N pelari yang berlari satu per satu, sesuai urutan nomor dadanya. Panitia mencatat waktu tempuh setiap pelari.

Seorang pelari disebut memecahkan rekor kalau waktunya lebih cepat daripada semua pelari yang berlari sebelum dia. Pelari pertama otomatis memecahkan rekor, karena belum ada pembanding. Pelari yang waktunya sama persis dengan rekor yang berlaku tidak dianggap memecahkan rekor.

Hitung berapa kali rekor dipecahkan sepanjang lomba.

Format masukan. Baris pertama berisi bilangan bulat N. Baris kedua berisi N bilangan bulat T₁ T₂ … T_N, waktu tempuh setiap pelari sesuai urutan berlari.

Format keluaran. Satu baris berisi banyaknya rekor yang dipecahkan.

Batasan.

• 1 ≤ N ≤ 200.000
• 1 ≤ Tᵢ ≤ 10⁹

Contoh masukan

6
15 12 14 10 10 9

Contoh keluaran

4

Penjelasan. Rekor dipecahkan oleh pelari dengan waktu 15, 12, 10, dan 9. Pelari berwaktu 14 tidak memecahkan rekor karena 12 sudah lebih cepat, dan pelari kelima berwaktu 10 juga tidak, karena harus lebih cepat, bukan sama.

Kerangkanya: exercises/08/osn/02-rekor-baru.cpp

Soal 3 — Permen Berputar

N anak duduk melingkar dan dinomori 1 sampai N searah jarum jam. Seorang guru membagikan M permen satu per satu: permen pertama untuk anak nomor 1, permen kedua untuk anak nomor 2, dan seterusnya. Setelah anak nomor N, pembagian kembali ke anak nomor 1, terus berputar sampai permennya habis.

Tentukan nomor anak yang menerima permen terakhir, dan berapa permen yang diterima anak nomor 1.

Format masukan. Satu baris berisi dua bilangan bulat N dan M.

Format keluaran. Satu baris berisi dua bilangan bulat: nomor anak yang menerima permen terakhir, lalu banyaknya permen yang diterima anak nomor 1.

Batasan.

• 1 ≤ N ≤ 10⁹
• 1 ≤ M ≤ 10¹⁸

Contoh masukan

3 7

Contoh keluaran

1 3

Penjelasan. Permen dibagikan ke anak 1, 2, 3, 1, 2, 3, 1. Permen ketujuh jatuh ke anak nomor 1, dan anak nomor 1 menerima tiga permen. Perhatikan batasan M: jawabannya tidak boleh dicari dengan membagikan permen satu per satu.

Kerangkanya: exercises/08/osn/03-permen-berputar.cpp

Bingung atau sudah selesai? Buka halaman pembahasan PR.