Perkenalan Pemrograman Kompetitif

Pemrograman kompetitif merupakan terjemahan bebas dari istilah competitive programming. Secara lebih spesifik, pemrograman kompetitif merupakan kompetisi menyelesaikan suatu masalah secara algoritmik dengan cara menulis program komputer. Program komputer tersebut harus dapat menghasilkan jawaban dalam jangka waktu tertentu dan dengan batasan memori tertentu.

Fokus dari pemrograman kompetitif adalah kemampuan menemukan algoritma penyelesaian masalah dan mengimplementasikan algoritma tersebut menjadi sebuah program komputer. Sehingga, aspek-aspek pemrograman yang lain seperti antarmuka grafis, jaringan, basis data, dan lain-lain biasanya tidak perlu diperhatikan.

Di Indonesia sendiri, pemrograman kompetitif ini terkadang disebut dengan lomba komputer, olimpiade komputer, atau olimpiade informatika.

Mengapa kita mempelajari pemrograman kompetitif?

  • Mengasah otak dan melatih kemampuan problem solving.
  • Sangat membantu ketika seseorang berminat untuk melanjutkan studi ke arah TI dan memerlukan keterampilan pemrograman.
  • Persiapan untuk menghadapi lomba-lomba pemrograman kompetitif baik nasional maupun online. Dengan mengikuti lomba-lomba, kita bisa menambah teman sehobi, dan kalau beruntung bisa mendapat hadiahnya.
  • Melatih kedisplinan berlatih.
  • Bagi sebagian orang, berhasil menyelesaikan soal memberikan kepuasan tersendiri. Sehingga pemrograman kompetitif menjadi suatu hobi.

Contoh Soal

Langsung saja kita bahas sebuah contoh soal yang muncul pada sebuah kompetisi.

Kandang Bebek
Batas Waktu: 1 detik
Batas Memori: 64 MB

Pak Dengklek memiliki N ekor bebek. Ia ingin menempatkan bebek-bebeknya tersebut pada kandang-kandang. Ia juga ingin agar setiap kandang berisi paling banyak M ekor bebek.

Tentukan jumlah kandang paling sedikit yang diperlukan Pak Dengklek.

Batasan
1 ≤ N ≤ 1.000.000.000
1 ≤ M ≤ 1.000.000.000

Format Masukan
Sebuah baris berisi sebuah bilangan bulat N dan M, dipisahkan oleh sebuah spasi.

Format Keluaran
Sebuah baris berisi jumlah kandang paling sedikit.

Contoh Masukan

12 5

Contoh Keluaran

3

Penjelasan Contoh Soal

Dari contoh soal di atas, kita bisa lihat bahwa ‘masalah’ yang dimaksud pada pemrograman kompetitif memiliki bagian-bagian berikut:

  • Deskripsi soal, dalam soal ini Pak Dengklek ingin mengetahui jumlah kandang minimal yang ia perlukan untuk menempatkan bebek-bebeknya.
  • Batas waktu, dalam soal ini 1 detik, artinya program tidak boleh berjalan lebih dari 1 detik (akan dinyatakan salah jika demikian).
  • Batas memori, dalam soal ini 64 MB, artinya program tidak boleh menggunakan lebih dari 64 MB memori selama berjalan (akan dinyatakan salah jika demikian).
  • Batasan masukan, dalam soal ini 1 ≤ N ≤ 1.000.000.000 dan 1 ≤ M ≤ 1.000.000.000. Artinya, program yang dibuat dijamin hanya akan menerima masukan N dan M sesuai batasan tersebut. Program tidak perlu memikirkan cara untuk menyelesaikan soal tersebut jika N lebih besar dari 1 juta, dan lain-lain.
  • Format masukan, dalam soal ini terletak pada bagian Format Masukan, menyatakan bagaimana masukan akan diberikan pada program. Masukan ini biasanya diberikan melalui standard input, yaitu keyboard komputer, atau dari file jika disebutkan demikian.
  • Format keluaran, dalam soal ini terletak pada bagian Format Keluaran, menyatakan bagaimana program harus memberikan keluaran. Keluaran ini biasanya harus diberikan oleh program ke standard output, yaitu layar komputer, atau ke file jika disebutkan demikian.

Cara Pengerjaan Soal

Setelah membaca soal, secara umum peserta mengetikkan program solusinya dalam bahasa yang diperbolehkan pada kompetisi tersebut (biasanya terbatas pada Pascal, C, C++, dan Java). Setelah itu, peserta akan mengirimkan kode sumber programnya ke server kompetisi tersebut. Server tersebut bertindak sebagai juri yang akan menilai apakah program peserta tersebut benar atau tidak.

Untuk mengetahui program tersebut benar atau tidak, server akan memberikan beberapa ‘kasus uji’. Sebuah kasus uji terdiri atas sebuah masukan dan sebuah keluaran yang benar dari masukan tersebut. Jika program peserta berhasil mengeluarkan keluaran yang sama, maka program dikatakan lolos kasus uji tersebut.

Terdapat dua jenis penilaian pada kompetisi, yaitu gaya IOI dan gaya ICPC. Dalam gaya IOI, setiap kasus uji yang lolos diberi nilai, jadi peserta bisa mendapat nilai yang beragam di soal tersebut. Dalam gaya ICPC, peserta mendapat nilai hanya jika programnya lolos pada semua kasus uji. Kompetisi tingkat mahasiswa pada umumnya hanya menggunakan gaya ICPC.

Penyelesaian Contoh Soal

Mari kita bahas bagaimana menyelesaikan contoh soal di atas.

Agar jumlah kandang sesedikit mungkin, tentu saja untuk setiap kandang jumlah bebek di dalamnya harus sebanyak mungkin (kalau bisa M ekor, kalau tidak bisa barulah kurang dari M). Dengan kata lain, selama Pak Dengklek masih memiliki ≥ M ekor bebek, buat kandang baru dan masukkan M bebek tersebut ke dalamnya. Jika bebek habis, selesai. Jika masih ada dan < M, buat kandang baru dan masukkan semuanya, lalu selesai. Dengan cara ini dijamin jumlah kandangnya paling sedikit.

Berikut ini contoh solusi soal dalam bahasa Pascal:

var
    N, M, kandang : longint;
begin
    readln(N, M);
    kandang := 0;
    while N > 0 do begin
        inc(kandang);
        if N >= M then
            N := N - M
        else
            N := 0;
    end;
    writeln(kandang);
end.

Sayangnya, solusi di atas tidak cukup cepat. Apabila N = 1.000.000.000 dan M = 1, maka program di atas akan menjalankan loop sebanyak 1 miliar kali, yang tidak cukup cepat dilakukan dalam 1 detik.

Adakah cara yang lebih cepat dalam menyelesaikan soal di atas? Tentu saja! Ternyata, secara matematis banyaknya kandang yang diperlukan adalah N / M, dibulatkan ke atas (silakan dibuktikan sendiri!). Sehingga, solusinya menjadi sangat pendek seperti ini.

var
    N, M : longint;
begin
    readln(N, M);
    writeln((N + M - 1) div M);
end.

(“(a + b – 1) div b” merupakan cara cepat untuk menuliskan ekspresi “a / b, dibulatkan ke atas”.)

Dengan contoh ini, ditunjukkan bahwa masalah yang diberikan dalam pemrograman bukanlah semata masalah pemrograman saja, melainkan masalah analitis yang mendalam. Pemrograman hanyalah sebagai realisasinya saja. Seringkali, program untuk menjawab masalah tersebut merupakan program yang singkat.