Dari Membaca Soal hingga Accepted, dengan C++ dan Python — Seorang mahasiswi mengirimkan solusi pertamanya ke sebuah online judge tengah malam, dan diberi tahu, dengan huruf merah, bahwa solusinya salah. Programnya mencetak jawaban yang benar di laptopnya.

Ringkasan

Bab 1 menjelaskan apa itu pemrograman kompetitif, apa yang ditawarkan SPOJ, dan apa yang sebenarnya dilakukan juri terhadap program yang dikirim. Bab ini memasang meja kerja, menyelesaikan soal SPOJ pertama, TEST, dan membangun juri kecil buatan sendiri yang mengompilasi, menjalankan, dan membandingkan program seperti yang dilakukan SPOJ.

Bab 2 sampai 4 membahas soal sebelum algoritmanya. Bab 2 mengajari Anda membaca soal seperti juri: anatominya, daftar periksa membaca, tiga bentuk masukan juri, dan frasa-frasa yang menentukan segalanya, pada ADDREV, FCTRL2, dan ONP. Bab 3 mengubah batas waktu menjadi anggaran langkah, menghitung langkah sebuah algoritma, dan menunjukkan bagaimana batasan soal menunjuk ke metodenya, dengan FCTRL, LASTDIG, dan segmented sieve pada PRIME1. Bab 4 mengukur setiap cara membaca dan menulis data dalam kedua bahasa dan menarik aturan untuk masukan dan keluaran yang sangat besar, pada INTEST dan INOUTEST.

Bab 5 sampai 8 membahas segala hal yang berdiri di antara gagasan yang benar dan program yang diterima. Bab 5 menjelaskan apa yang dilakukan juri terhadap kode sumber Anda: flag kompiler yang menemukan bug, flag dan pragma yang mempercepat kode, tangga risiko pragma, dan daftar periksa portabilitas. Bab 6 membelanjakan anggaran kedua, memori: berapa sebenarnya biaya satu elemen, rentang yang terlalu besar untuk disimpan pada PRIME1, tabel yang tidak muat pada LKS, dan stack yang lebih kecil daripada dugaan Anda. Bab 7 mendaftar jebakan implementasi klasik penyebab Wrong answer — overflow, bilangan yang melampaui setiap tipe bawaan, nol yang harus dihilangkan, keadaan yang bocor antarkasus uji, pembagian dan floating point, serta kesalahan selisih satu. Bab 8 membangun perangkat uji yang diandalkan seluruh sisa buku: generator, brute force, dan stress test yang memburu jawaban salah dan langkah lambat yang tersembunyi, pada INVCNT dan PALIN.

Bab 9 sampai 11 adalah inti algoritmanya. Bab 9 mengajarkan pemrograman dinamis melalui enam pola — deretan pilihan, menghitung banyak cara, lintasan pada kisi, knapsack, dua string, dan interval — pada FARIDA, ACODE, BYTESM2, KNAPSACK, EDIST, dan MIXTURES. Bab 10 menunjukkan kapan pilihan greedy aman dan bagaimana argumen pertukaran membuktikannya, pada BUSYMAN, FASHION, BAISED, dan GERGOVIA. Bab 11 mencari jawaban alih-alih menghitungnya, dengan binary search pada jawaban dan dua penunjuk, pada AGGRCOW, EKO, PIE, BOOKS1, dan HOTELS.

Bab 12 dan 13 adalah kotak perkakas. Bab 12 merakit algoritma graf yang paling sering diperlukan dalam lomba: union-find, breadth-first search, pemeriksaan graf bipartit, lintasan terpanjang pada pohon, lintasan terpendek Dijkstra, pengurutan topologis, dan pohon merentang minimum Kruskal. Bab 13 melakukan hal yang sama untuk teori bilangan, geometri, dan string: perpangkatan cepat, fungsi totient Euler, uji keprimaan Miller–Rabin, orientasi, convex hull dan luas poligon, pasangan titik terdekat, Knuth–Morris–Pratt, periode sebuah string, dan suffix array.

Bab 14 menyatukan seluruh keterampilan itu. Bab ini merangkai bab-bab sebelumnya menjadi satu alur kerja dan menempuhnya dari awal sampai akhir pada tiga studi kasus, PPATH, ABCPATH, dan ONEZERO, menunjukkan apa yang harus dilakukan ketika vonisnya bukan Accepted, dan menyarankan langkah berikutnya.

Setiap bab menempuh jalan yang sama: sebuah kisah dan masalah yang dimunculkannya, gagasannya dalam kata-kata sederhana dengan contoh kecil yang dihitung dengan tangan, soal-soal SPOJ sungguhan yang diceritakan ulang dengan kata-kata kita sendiri, gagasan yang dibuktikan kebenarannya dan dihitung biayanya, program acuan dalam C++17 dan Python, menjalankannya, mengujinya terhadap brute force, menyempurnakannya, memakainya sungguh-sungguh, kesalahan yang sering terjadi, ringkasan, soal latihan dengan penyelesaian lengkap, dan daftar pustaka.

Setiap program dalam buku ini sudah dijalankan sebelum keluarannya dicetak. Program-program itu dikumpulkan, bab demi bab, dalam folder kode yang menyertai buku ini, dari Chapter01 sampai Chapter14, masing-masing dengan folder cpp, folder python, folder tests yang berisi generator, brute force, dan skrip stress test, serta README yang menjelaskan cara mengompilasi dan menjalankannya di terminal dan di VS Code, pada Windows, macOS, dan Linux.

Isi Buku

1. Selamat Datang di Pemrograman Kompetitif dan SPOJ
2. Membaca Soal Seperti Juri
3. Memilih Algoritma Sesuai Batasan
4. Input dan Output Cepat
5. Flag Kompiler, Pragma, dan Portabilitas
6. Memori dan Pilihan Struktur Data dalam Batas Byte
7. Jebakan Implementasi Klasik Penyebab Wrong Answer
8. Men-debug TLE dan WA: Stress Test dan Pemeriksa Brute-Force
9. Pola Pemrograman Dinamis
10. Algoritma Greedy dan Argumen Pertukaran
11. Binary Search pada Jawaban dan Dua Penunjuk
12. Perkakas Algoritma Graf
13. Perkakas Teori Bilangan, Geometri, dan String
14. Menuju Accepted: Studi Kasus Utuh dan Langkah Berikutnya