PEMROGRAMAN
                                                    KOMPETITIF
                                                    DASAR
                                                     Panduan Memulai OSN Informatika,
                                                     ACM-ICPC, dan Sederajat
         Ikatan Alumni
         Tim Olimpiade                                             William Gozali & Alham Fikri Aji
         Komputer Indonesia
    Abstrak
      Buku persiapan OSN informatika, atau disebut juga OSN komputer, yang ditulis
   oleh Ikatan Alumni Tim Olimpiade Komputer Indonesia (TOKI). Buku elektronik ini dapat
   diunduh (download) dan bersifat gratis. Seluruh materi disesuaikan dengan kurikulum
   OSNsehinggaseluruh siswa calon peserta OSN dapat belajar dengan lebih mudah. Buku
   ini juga dapat digunakan bagi pelajar yang hendak memulai partisipasi pada ACM-ICPC.
          PEMROGRAMANKOMPETITIFDASAR,VERSI1.9
          Dipublikasikan oleh CV. Nulisbuku Jendela Dunia
            Penulis                AlhamFikri Aji (IA-TOKI),
                                   William Gozali (IA-TOKI)
            Kontributor            AgusSentosaHermawan(NUS),
                                   Ali Jaya Meilio Lie (Université de Grenoble Alpes),
                                   Arianto Wibowo (IA-TOKI),
                                   Ashar Fuadi (IA-TOKI),
                                   Cakra Wishnu Wardhana (UI),
                                   Jonathan Irvin Gunawan (Google),
                                   Maximilianus Maria Kolbe Lie (BINUS),
                                   MuhammadAyazDzulfikar(UI),
                                   MuhammadFairuzi Teguh (UI),
                                   Reynaldo Wijaya Hendry (UI)
            Penyunting             Ilham Winata Kurnia (Google),
                                   Suhendry Effendy (NUS)
            Desain dan tata letak  AlhamFikri Aji,
                                   Ali Jaya Meilio Lie,
                                   Pusaka Kaleb Setyabudi (Google),
                                   William Gozali
          Versi elektronik buku ini dapat diakses secara gratis di URL berikut: https://toki.id/
          buku-pemrograman-kompetitif-dasar
          KaryainidilisensikandibawahlisensiCreativeCommonsAttribution-NonCommercial-
          NoDerivatives 4.0 International (CC BY-NC-ND 4.0)
          Hal ini berarti Anda bebas untuk menggunakan dan mendistribusikan buku ini, dengan
          ketentuan:
              • Attribution: Apabila Anda menggunakan materi-materi pada buku ini, Anda harus
                memberikan kredit kepada tim penulis dan Ikatan Alumni TOKI.
              • NonCommercial: Andatidak boleh menggunakan buku ini untuk keperluan komer-
                sial, seperti menjual ulang buku ini.
              • NoDerivatives: Anda tidak boleh mengubah konten buku ini dalam bentuk apapun.
          Masukandanpertanyaan dapat disampaikan kepada penulis di info@toki.id.
          ISBN978-602-6598-89-9
         Daftar Isi
        KataPengantar                                                                                      v
        UcapanTerimaKasih                                                                                 vi
        1 PerkenalanPemrogramanKompetitif                                                                  1
            Kompetensi Dasar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .           1
            Tentang Pemrograman Kompetitif . . . . . . . . . . . . . . . . . . . . . . . . .               1
            Contoh Soal Pemrograman Kompetitif . . . . . . . . . . . . . . . . . . . . . . .               2
                  Solusi Sederhana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .         3
                  Solusi yang Lebih Baik . . . . . . . . . . . . . . . . . . . . . . . . . . . . .         4
                  Solusi yang Lebih Baik Lagi! . . . . . . . . . . . . . . . . . . . . . . . . . .         5
            Mengenal Kompetisi Pemrograman . . . . . . . . . . . . . . . . . . . . . . . . .               7
                  Olimpiade Sains Nasional dan International Olympiad in Informatics             . . .     7
                  ACM-ICPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .           8
            Penulisan Kode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .         9
            Perkenalan Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .            9
        2 MatematikaDiskretDasar                                                                         11
            Arimetika Modular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        11
            Bilangan Prima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .       12
                  Uji Keprimaan (Primality Testing) . . . . . . . . . . . . . . . . . . . . . . .        12
                  Pembangkitan Bilangan Prima (Prime Generation) . . . . . . . . . . . . . .             12
            FPBdanKPK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .          14
            Pigeonhole Principle (PHP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .         16
            Kombinatorika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        17
                  Aturan Perkalian dan Aturan Penjumlahan . . . . . . . . . . . . . . . . . .            17
                  Permutasi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      19
                  Kombinasi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      22
                  Segitiga Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      24
        3 PencariandanPengurutan                                                                         26
            Pencarian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      26
                  Sequential Search      . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   26
                  Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      26
                  Rangkuman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        30
            Pengurutan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .       30
                  Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      31
                  Selection Sort     . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   32
                  Insertion Sort     . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   33
                  Counting Sort      . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   35
                  Rangkuman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        38
        4 BruteForce                                                                                     40
            KonsepBruteForce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .           40
            Penyelesaian dengan Teknik Brute Force . . . . . . . . . . . . . . . . . . . . . .           40
                                                                                                            i