OSN Informatika

Buku ini menyiapkan kamu untuk OSN bidang Informatika: olimpiade yang menguji kemampuan menyelesaikan masalah dengan algoritma, lalu menuliskan penyelesaian itu sebagai program yang benar dan cukup cepat.

Tidak ada pengetahuan awal yang diandaikan. Buku mulai dari memasang compiler, menulis program pertama, sampai teknik yang benar-benar dipakai di soal OSN: brute force, greedy, dynamic programming, aritmetika modulo, FPB/KPK, serta aturan hitung dan permutasi-kombinasi.

Susunan buku

Buku dibagi menjadi lima bagian. Setiap bagian ditutup satu mini-proyek yang hanya memakai hal-hal yang sudah diajarkan sampai titik itu.

  • Bagian 1 — Dasar pemrograman C++. Memasang compiler, program pertama, variabel, percabangan, perulangan, fungsi, array dan vector. C++ diletakkan paling depan supaya seluruh bagian berikutnya bisa langsung dijalankan di komputer, bukan sekadar dibaca.
  • Bagian 2 — Berpikir komputasional. Dekomposisi, pengenalan pola, abstraksi, dan algoritma. Termasuk cara menuliskan algoritma sebagai flowchart dan pseudocode, menelusurinya dengan tangan, serta menghitung jumlah langkahnya.
  • Bagian 3 — Pemecahan masalah. Tiga cara kerja yang paling sering dipakai di OSN: brute force, greedy, dan dynamic programming — kapan masing-masing dipakai dan kapan gagal.
  • Bagian 4 — Teori bilangan. Aritmetika modulo beserta sifat-sifat dan teoremanya, lalu FPB dan KPK dengan algoritma Euclid.
  • Bagian 5 — Kombinatorika. Aturan penjumlahan dan perkalian, permutasi, dan kombinasi — termasuk cara menghitungnya dengan program.

Bentuk tiap bab

Semua bab punya bentuk yang sama:

  • Penjelasan singkat satu ide.
  • Contoh kode yang bisa dibuka dari folder exercises/ dan dijalankan di komputer sendiri.
  • Beberapa kotak Coba ini di tengah bab. Isinya perubahan satu baris yang sebaiknya langsung dikerjakan.
  • Bagian Pekerjaan rumah di akhir bab, berisi tiga sampai lima soal dan satu Tantangan opsional.
  • Halaman pembahasan PR terpisah (tautannya ada di akhir bagian PR) yang menjelaskan cara berpikirnya dulu, baru menampilkan kode.

Kotak di dalam bab

Empat jenis kotak berwarna dipakai berulang kali. Kenali artinya sejak sekarang supaya tahu mana yang boleh dilewati sekilas dan mana yang tidak:

Kotak Isinya
Catatan penjelasan tambahan, latar belakang, atau kebiasaan di lomba
Perhatian kesalahan yang benar-benar sering terjadi dan memakan nilai
Coba ini perubahan satu atau dua baris yang dikerjakan langsung di komputer
Pekerjaan rumah daftar soal di akhir bab

Kotak Perhatian adalah yang paling mahal untuk dilewati. Isinya bukan teori, melainkan daftar cara kehilangan nilai yang sudah terbukti.

Cara membaca contoh kode

Tiga bentuk blok dipakai di seluruh buku, dan artinya berbeda:

Blok kode C++ — ini yang diketik ke dalam file .cpp:

cout << 1 + 2 << "\n";

Blok menjorok tanpa warna — ini keluaran program atau perintah yang diketik di terminal, bukan kode C++:

3

Blok pseudocode — ini bukan bahasa pemrograman mana pun, melainkan algoritma yang ditulis sebagai kalimat pendek (Bab 09 membahas aturannya):

BACA n
CETAK n * 2

Beberapa potongan kode di buku ini sengaja hanya menampilkan bagian yang sedang dibahas, tanpa #include dan int main(). Potongan seperti itu tidak bisa di-compile apa adanya — versi lengkapnya ada di file yang disebut pada kotak Coba ini di dekatnya.

Yang kamu perlukan

  • Komputer dengan Windows 10 atau 11.
  • Compiler C++ (MinGW-w64 atau Visual Studio, dipasang di Bab 01) dan satu editor kode.
  • Kertas dan pensil. Bagian 2 sampai 5 banyak dikerjakan di kertas dulu, persis seperti saat mengerjakan soal OSN.
  • Akun di satu situs penilai daring (online judge) untuk berlatih mengirim jawaban. Bab 01 menjelaskan pilihannya.

Cara memakai buku ini

Satu bab dikerjakan dengan lingkaran lima langkah berikut, berurutan:

  1. Baca babnya sekali sampai habis, tanpa komputer. Tujuannya mengenali ada ide apa saja di dalamnya, bukan menghafal.
  2. Jalankan setiap contoh yang disebut di kotak Coba ini. Membaca kode dan menjalankan kode menghasilkan pemahaman yang sama sekali berbeda.
  3. Rusak contohnya dengan sengaja. Ubah satu angka, hapus satu baris, balik satu tanda pembanding, lalu tebak apa yang akan terjadi sebelum menjalankan ulang. Tebakan yang meleset adalah tempat pemahamanmu bocor, dan itu yang paling berguna untuk diperbaiki.
  4. Kerjakan PR-nya sendiri sampai jalan, tanpa membuka halaman pembahasan.
  5. Baru buka halaman pembahasan, bandingkan dengan jawabanmu — termasuk ketika jawabanmu sudah benar, karena pembahasan sering memuat cara yang lebih pendek atau kasus tepi yang terlewat.

Melompati langkah 2 sampai 4 dan langsung membaca pembahasan adalah cara tercepat merasa paham padahal belum bisa.

Kalau satu soal PR sudah macet lebih dari sekitar setengah jam tanpa kemajuan sama sekali, berhenti menatap layar: telusuri kodenya di kertas dengan masukan yang sangat kecil (Bab 10 mengajarkan caranya). Sebagian besar kemacetan hilang di tabel penelusuran, bukan di layar.

Dua kebiasaan yang perlu dibangun sejak Bagian 1, karena keduanya menentukan nilai di lomba:

  • Selalu jalankan kodemu dengan kasus tepi, bukan hanya contoh yang ada di soal. Nilai yang hilang di OSN jauh lebih sering disebabkan satu kasus tepi yang terlewat daripada algoritma yang salah.
  • Hitung dulu jumlah langkahnya, baru tulis kodenya. Bab 10 memberi tabel yang mengubah batasan soal menjadi pilihan algoritma. Mulai Bagian 3, kebiasaan ini yang membedakan jawaban bernilai penuh dari jawaban yang kehabisan waktu.

Bab berikutnya, Persiapan, memasang compiler dan editor supaya kode di buku ini bisa dijalankan.