Rumah penerbitan "DMK Press" menerbitkan buku "pemrograman Olympiad" dengan subtitle "Mempelajari dan meningkatkan algoritma dalam kompetisi". Ini telah menjadi angin segar bagi semua orang yang tertarik, mempersiapkan dan mempersiapkan diri untuk berpartisipasi, atau hanya merencanakan di masa depan, dalam jenis kegiatan intelektual seperti berbagai acara pemrograman olahraga. Di Rusia, mereka tidak kenal baik.
Edisi Rusia dari Guide to Competitive Programming (Springer International Publishing AG) diterbitkan dengan dukungan Pusat Pengembangan Pendidikan MIPT IT dan direkturnya Alexei Maleev, Mail.Ru Group, serta proyek ICPC Lokakarya Moskow.
“Pemrograman Olimpiade menjadi semakin populer setiap tahun di kalangan siswa dan siswa. Sebuah contoh yang bagus dari hal ini adalah kenyataan bahwa pada tahun 2019, kami, ICPC Lokakarya Moskow, pada bulan November kami akan mengadakan persiapan kamp pelatihan kesepuluh untuk Piala Dunia di berbagai belahan dunia, mereka telah berlalu di Singapura, dan Eropa dan Amerika Selatan, dan Rusia - dari Vladivostok ke Moskow. Pada awal Oktober, Kontes Pemrograman Moskow diadakan di Moskow, di mana 2.284 orang ambil bagian di 18 venue universitas-universitas Moskow - ini adalah rekor absolut untuk skala kompetisi, yang diadakan dengan dukungan Rosmolodezh.
Kami sangat senang dengan minat yang besar dari para pemain, dan siap mendukungnya dalam segala hal - misalnya, untuk siswa universitas Moskow, kami melakukan pelatihan gratis untuk ICPC dengan partisipasi pelatih terbaik. Dan, tentu saja, selalu bermanfaat bagi peserta untuk mengkonsolidasikan materi, menganalisis tugas, dan meningkatkan pengetahuan mereka. Karena itu, saya sangat senang buku Anda telah muncul, dan saya ucapkan selamat kepada kita semua untuk ini. Kami berharap bahwa di final ICPC di Moskow pada Juni 2020 sudah akan ada orang-orang yang membacanya dan menjadi pahlawan edisi kedua yang dilengkapi. ”
Alexey Maleev, Direktur final Piala Dunia ICPC 2020 di Moskow, Wakil Rektor MIPT, pendiri proyek ICPC Lokakarya Moskwa.
"Panduan untuk Pemrograman Kompetitif" telah diterjemahkan ke dalam bahasa Rusia dari bahasa Inggris. Selain bahasa Inggris dan Rusia, publikasi dalam bahasa Korea dirilis.
Penulis buku ini adalah Antti Laaxsonen, seorang guru dan peneliti dari Universitas Helsinki Aalto (Finlandia) [3] dengan pengalaman luas dalam pengajaran pemrograman dan algoritma, dan pelatih tim Finlandia di kompetisi pemrograman internasional. Dia memiliki peringkat tinggi 2347 dan status "master internasional" di portal Codeforces dengan julukan "pllk" [4]. Pada 2008, ia A. Laaxsonen menjadi salah satu penyelenggara Olimpiade Informatika di negaranya. Pada 2016 - pengawas ilmiah Olimpiade Baltik di Informatika.
Target pembaca buku ini adalah semua yang tertarik dan / atau bekerja di bidang pemrograman Olympiad. Tetapi, untuk asimilasi penuh bahan, pengetahuan dasar-dasar pemrograman diperlukan, sedangkan penulis tidak mengharuskan pembaca untuk memiliki pengalaman dalam merancang algoritma atau berpartisipasi dalam kompetisi. Semua ini memungkinkan kami untuk merekomendasikan karya ini kepada berbagai pembaca yang tertarik. Untuk pemula, ini akan menjadi pengantar pemrograman Olimpiade modern, spesialis berpengalaman akan membantu untuk mensistematisasikan pengetahuan, akan menjadi alat referensi bagi mereka.
Penyampaian materi dalam buku dilakukan dari yang sederhana sampai yang kompleks. Pertama, ia berkenalan dengan tujuan dan sasaran buku, dengan pemrograman Olympiad, koleksi tugas CSES [5] dan buku-buku lain yang relevan tentang pemrograman Olympiad.
Setelah menerima landasan teori yang diperlukan, pembaca akan siap untuk melanjutkan ke praktik. Teknik pemrograman adalah topik selanjutnya. Di dalamnya, penulis menyertakan dasar-dasar bahasa C ++ (standar C11), yang mengimplementasikan semua contoh dalam buku; analisis algoritma rekursif dan operasi bitwise.
Dalam bab-bab buku ini, pembaca akan dapat menemukan informasi tentang sebagian besar topik "standar" dan contoh-contoh penerapan algoritma yang ditawarkan kepada peserta dalam olimpiade pemrograman: struktur data, pemrograman dinamis, algoritma grafik dan algoritma pohon, kisaran permintaan, dan manipulasi baris.
Secara terpisah, saya ingin menyoroti sejumlah bab buku ini. Misalnya, bab "Masalah Desain yang Dipilih untuk Algoritma". Ini termasuk algoritma dengan tampilan paralel debit, analisis depresiasi, dan menemukan nilai minimum. Pembaca ditawari algoritma untuk menemukan jarak Hamming, solusi dari masalah pencapaian dalam grafik, metode dua-pointer, pencarian ternary, meminimalkan jumlah dan topik menarik lainnya untuk "Olimpiade" dan pelatih mereka.
Sebagai contoh, saya akan memberikan contoh tugas dari bab "Pertanyaan yang dipilih untuk merancang algoritma".
Mari kita pertimbangkan algoritma dengan tampilan paralel bit di mana operasi bitwise digunakan untuk pemrosesan data yang efisien. Dalam kasus yang umum, kita dapat mengganti loop untuk dengan operasi bitwise, yang secara signifikan mengurangi waktu berjalan dari algoritma.
Algoritma Penjelajahan Paralel
Algoritma dengan tampilan paralel angka didasarkan pada fakta bahwa digit individu nomor dapat dimanipulasi secara paralel menggunakan operasi bitwise. Oleh karena itu, salah satu metode perancangan algoritma adalah untuk menyajikan langkah-langkah algoritma sedemikian rupa sehingga mereka dapat diimplementasikan secara efektif menggunakan operasi bitwise.
Jarak Hamming Jarak Hamming
hamming (a, b) antara garis a dan b dengan panjang yang sama adalah jumlah posisi di mana garis-garis ini berbeda. Sebagai contoh:
hamming (01101, 11001) = 2.
Pertimbangkan tugas berikut: diberikan n bit string panjang k, hitung jarak Hamming minimum antara dua string. Misalnya, untuk baris [00111, 01101, 11110], jawabannya adalah 2, karena
- hamming (00111, 01101) = 2;
- hamming (00111, 11110) = 3;
- hamming (01101, 11110) = 3.
Masalahnya dapat diselesaikan "langsung" dengan menghitung jarak Hamming antara setiap dua garis. Kompleksitas waktu dari algoritma semacam itu adalah (n
k). Untuk menghitung jarak antara garis a dan b, gunakan fungsi berikut:
int hamming(string a, string b) { int d = 0 for (int i = 0; i < k; i++) { if (a[i] != b[i]) d++; } return d; }
Tetapi karena string terdiri dari bit, solusinya dapat dioptimalkan dengan menyimpan string sebagai bilangan bulat dan menghitung jarak di antara mereka menggunakan operasi bitwise. Secara khusus, jika k ≤ 32, maka string dapat disimpan sebagai nilai dari tipe int dan untuk menghitung jaraknya gunakan fungsi ini:
int hamming(int a, int b) { return __builtin_popcount(a^b); }
Di sini operasi EKSKLUSIF ATAU membangun garis di mana unit-unit berada pada posisi-posisi di mana a dan b berbeda. Kemudian jumlah digit unit dihitung dengan fungsi __builtin_popcount. Tabel menunjukkan hasil membandingkan algoritma asli dan algoritma dengan tampilan paralel dari bit dalam hal run time pada komputer modern. Algoritma dengan tampilan bit paralel ternyata sekitar 20 kali lebih cepat.
Tabel: Menjalankan waktu algoritma menghitung jarak Hamming minimum untuk string n bit panjang k = 30
Bab-bab "Matematika" dan "Geometri" layak mendapat perhatian. Seperti yang sudah ditebak pembaca, mereka dikhususkan untuk memecahkan masalah matematika dan geometris dengan menggunakan bahasa pemrograman C ++ dan pembuatan algoritma yang sesuai. Dalam bab "matematika", lima topik besar menunggu kita: "Teori Angka", "Kombinatorik", "Matriks", "Kemungkinan" dan "Teori Game". Dan di "geometrik": "Teknis berarti dalam geometri", "Algoritma berdasarkan garis sapuan". Dengan demikian, presentasi kompleks dari pembangunan algoritma untuk memecahkan masalah matematika dan geometris membuat buku ini "menemukan" untuk "olympiadniki", karena dengan latar belakang kekurangan buku tentang hal ini, ini jarang terjadi.
Sejumlah masalah, penulis memutuskan untuk memasukkan dalam bab "Topik tambahan". Perkembangan mereka "terkadang dapat membantu memecahkan masalah olimpiade yang paling sulit". Ini adalah "Root kuadrat dalam algoritma", "Dan lagi tentang pohon segmen", "Duchi", "Optimasi pemrograman dinamis" dan "Lain-lain". Berdasarkan nama penjelasan tambahan, mereka memerlukan subpos pada ranting pohon dan pada hal-hal yang berbeda.
Adapun pohon-pohon segmen, pembaca akan berkenalan dengan propagasi malas, pohon dinamis, struktur data di simpul, pohon dua dimensi. Dan di “Miscellaneous” ia menunggu: pertemuan di tengah (membagi ruang pencarian menjadi dua bagian, kira-kira sama, melakukan pencarian di setiap bagian, dan kemudian menggabungkan hasilnya), menghitung set, pencarian biner paralel, konektivitas dinamis.
Lengkapi informasi referensi buku tentang matematika dan daftar pustaka yang luas (32 sumber).
Jadi, buku "Olimpiade pemrograman" oleh Antti Laaxsonen adalah pengantar yang sangat baik untuk dunia pemrograman olahraga. Pada saat yang sama, panduan referensi yang luar biasa. Buku ini cocok untuk pemula "olympiadnikov" dan akan membantu dalam pengorganisasian pengetahuan yang berpengalaman. Ini akan bermanfaat bagi pelatih.
Sekali lagi, kami mencatat bahwa semua contoh dalam buku ini diimplementasikan dalam bahasa pemrograman C ++. Ia paling laris di Olimpiade. Tetapi seseorang mungkin menemukan ini kelemahan dari buku ini, karena bahasa lain yang populer - Python, Java. Mereka yang lebih suka bahasa pemrograman ini dapat menyelesaikan masalah yang diajukan dalam sebuah buku dalam bahasa favorit mereka. Ini akan menjadi latihan yang bagus. Pada akhirnya, justru dalam mencari solusi optimal, tugas-tugas Olympiad selesai.
Artikel ini disiapkan oleh: Igor Shtompel, penulis dan presenter bagian "Karir \ Pendidikan" dalam jurnal
"System Administrator"