TOKInews
Mei 2015
Lembar Informasi Tim Olimpiade Komputer Indonesia
Kementerian Pendidikan dan Kebudayaan RI
TOKI 2015, BERSIAP KE KAZAKHSTAN
E
mpat siswa terbaik akan menjadi duta Indonesia dalam ajang olimpiade keilmuan bergengsi tingkat dunia, International Olympiad in Informatics 2015 yang akan di selenggarakan pada tanggal 26 Juli – 2 Agustus 2015 di Almaty, Kazakhstan. Keempat siswa tersebut adalah : (1) Muhammad Ayaz Dzulfikar, SMA YP Vidya Dahana Patra Bontang (2) Agus Sentosa Hermawan, SMA Petra 2 Surabaya (3) Michael Wibawa, SMA Kanisius Jakarta (4) Stacia Edina Johanna, SMA Petra 3 Surabaya. Keempatnya berhasil terpilih setelah melalui proses panjang dalam rangkaian pembinaan dan seleksi yang telah berlangsung selama tahun 2014-2015. Rully Soelaiman, M.Kom (ITS) yang akan menjadi ketua delegasi tim Indonesia mengungkapkan, “Secara kemampuan materi para siswa sudah
sangat siap, kami berani menargetkan minimal 2 perak perak. Yang mereka butuhkan saat ini adalah lebih banyak latihan dan sangat penting untuk terus memantau kondisi psikologi para siswa terutama menyangkut masalah motivasi dan semangat juang agar tetap stabil hingga saat lomba tiba” . Sebelum berangkat, anggota tim masih akan menjalani pembinaan tahap akhir di kampus Fasilkom – UI Depok, sekitar bulan Juni/Juli nanti untuk memantapkan kemampuan para peserta. Tim Olimpiade Komputer Indonesia memohon doa restu dari seluruh masyarakat agar dalam persiapan dan pertandingannya nanti, semuanya dapat berjalan lancar dan berhasil membawa pulang prestasi yang membanggakan
Viva TOKI, Go Get Golds !!
Daftar Isi
01 02 03 04 06
TOKI Bersiap ke Kazakhstan Daftar Isi Selamat Datang di Jogjakarta Perjalanan Panjang TOKI 2015 Indonesia, Tuan Rumah APIO 2015
08 10 12 14 16
Matematika Informatika Untuk Siswa Olimpiade Bahas Soal - OSN 2014 Bahas Soal - OSP 2015 Bincang-bincang Alumni TOKI Hall of Fame
Tim Redaksi TOKINews 2015
Fauzan Joko
Julio Adisantoso
Yugo K. Isal
Yudhi Purwananto Jessica Handojo Ivan Hendradjaya
Ammar Fathin
Tim Olimpiade Komputer Indonesia * www.toki.or.id *
[email protected]
Agenda Kegiatan Peserta 18 Mei 2015
Kedatangan Peserta
Hotel Sahid Rich, Yogyakarta
19 Mei 2015 09:00 - 12:00 13:30 - 15:00 15:00 - 17:00
Upacara Pembukaan Penjelasan Teknis Lomba Practice Session
Jogja Expo Center Kampus Universitas Islam Indonesia Kampus Universitas Islam Indonesia
20 Mei 2015 07:30 - 08:30 08:30 - 13:30
Briefing Peserta Kompetisi Hari 1
Kampus Universitas Islam Indonesia Kampus Universitas Islam Indonesia
21 Mei 2015 07:30 - 08:30 08:30 - 13:30 14:30 - 17:00
Briefing Peserta Kompetisi Hari 2 Penjelasan Umum TOKI
Kampus Universitas Islam Indonesia Kampus Universitas Islam Indonesia Kampus Universitas Islam Indonesia
22 Mei 2015 08:00 - 17:00
Wisata Edukasi
Sekitar Kota Jogjakarta
23 Mei 2015 08:00 - 10:00 13:00 - 17:00
Pendidikan Karakter Upacara Penutupan
-Jogja Expo Center
24 Mei 2015
Kembali ke daerah masing-masing
William Gozali
Selamat Datang di OSN 2015, … Selamat Datang di Jogjakarta, …
B
erbagai julukan yang sering dilontarkan untuk Kota Jogjakarta seperti Kota Perjuangan, Kota Pariwisata, Kota Pelajar, Kota Budaya, dan paling populer yaitu Kota Gudeg. Peran Kota Jogjakarta untuk Indonesia memang sangat besar terutama pada masa sebelum dan sesudah kemerdekaan. Maka tidaklah berlebihan jika Pemerintah pusat memperbolehkan penggunaan nama daerahnya memakai sebutan DIY sekaligus statusnya sebagai Daerah Istimewa. Sebelah Utara dari propinsi Daerah Istimewa Jogjakarta merupakan puncak gunung Merapi yang memiliki ketinggian 2920 meter diatas permukaan laut. Oleh para ahli gunung berapi internasional, gunung merapi sangat terkenal karena bentuk letusannya yang khas dan sejenis dengan letusan gunung api Visuvius di Italia. Di sebelah selatan, wilayah Jogyakarta berbatasan langsung dengan Samudra hindia, tidak heran jika di Jogjakarta juga banyak dite mui pantai pantai yang
sangat indah. Di bagian barat dan timur wilayah DIY berbatasan langsung dengan propinsi Jawa Tengah. Dalam sejarah penyelenggaraan OSN, Jogjakarta dapat dikatakan sebagai tonggak sejarah pelaksanaan Olimpiade Sains Nasional, dimana pelaksanaan olimpiade sains nasional pertama kali juga dilaksanakan di Jogjakarta pada tahun 2002. Belasan tahun berlalu, kembali Jogjakarta menjadi tuan rumah penyelenggaraan OSN di tahun 2015 ini. Untuk bidang Informatika/Komputer, pelaksanaan lomba akan dilaksanakan di Kampus Universitas Islam Indonesia, di Jl. Kalirang KM 14 Jogjakarta, pada saat pelaksanaan OSN pertama kali dahulu, kampus ini pulalah yang menjadi tempat penyelenggaraan lomba bidang Informatika/komputer. Disela-sela pelaksanaan lomba, jangan lupa untuk juga menikmati kota Jogjakarta, keramahan penduduk, keragaman budaya, kesenian, keindahan alam dan tidak lupa berbagai macam kuliner khas Jogjakarta teramat sayang untuk dilewatkan. Selamat Datang, Selamat Bertanding !
Pantai Pok Tunggal, Gunung Kidul (Gambar : https://jogjakini.files.wordpress.com/)
PERJALANAN PANJANG TOKI 2015
T
im Olimpiade Komputer Indonesia 2015 yang saat ini tengah mempersiapkan diri untuk bertanding di ajang International Olympiad in Informatics 2015 di Almaty, Kazakhstan pada bulan juli 2015 yang akan datang merupakan sebuah tim yang dihasilkan oleh proses panjang dan bertahap, cukup banyak waktu, tenaga dan pikiran yang telah dicurahkan, tidak hanya dari peserta, namun juga para pembina, asisten, alumni dan pula dari pihak Kementerian Pendidikan dan Kebudayaan yang memberikan dukungan penuh terhadap seluruh proses seleksi dan pembinaan ini. Diawali dengan seleksi sekolah dan seleksi kabupaten/kota pada bulan April 2014, seleksi dilanjutkan dengan seleksi tingkat provinsi yang dilaksanakan pada bulan Juni 2014. Pada seleksi tahap ini beberapa daerah telah melakukan pembinaan kepada para siswanya agar dapat berhasil dalam menghadapi seleksi tahap berikutnya. Seleksi tingkat provinsi dilaksanakan pada periode yang sama untuk seluruh Indoneisa, namun masih terdapat beberapa kendali teknis yang mengakibatkan seleksi belum dapat dilaksanakan secara benar-benar serentak di seluruh Indonesia. Seleksi tingkat
4
Propinsi diikuti oleh lebih dari 1500 siswa dari seluruh Indonesia. Materi seleksi untuk bidang informatika/komputer adalah ujian tertulis bidang logika, algoritma dan aritmatika, dan pemrograman singkat (pseudocode). Proses penjurian di tingkat ini dilakukan secara terpusat oleh tim juri nasional. Hasil dari seleksi Propinsi ini bakal mengikuti proses lanjutan yaitu dalam Olimpiade Sains Nasional. OSN 2014 Olimpiade Sains Nasional 2014 dilaksanakan di Mataram, Nusa Tenggara Barat pada tanggal 1 – 7 September 2014, untuk bidang Informatika/Komputer dilaksanakan di Hotel Lombok Raya, Mataram dan diikuti oleh 96 peserta dari seluruh Indonesia. OSN 2014 menghasilkan 30 peserta peraih medali (emas : 5, perak : 10, perunggu : 15) yang sekaligus berhak mengikuti kegiatan pembinaan tahap 1. Pembinaan Tahap 1 Pembinaan tahap 1 berlangsung di Institut Teknologi Bandung dimulai dari tanggal 17 Oktober hingga 23 November 2014. Ajang Pelatnas ini bertujuan untuk menambah ilmu pengetahuan, mengasah dan menguji kemampuan para peserta,
mengenal lebih jauh tentang ITB dan kota Bandung, serta mencari teman dan pengalaman baru. Selain diberikan materi teori dan ketrampilan untuk menyelesaikan persoalan dengan pemrograman komputer, pada Pembinaan tahap 1 ini juga sekaligus dilakukan seleksi untuk memilih sisiwasiswa yang lolos untuk mengikuti Pembinaan tahap 2. Seleksi dilakukan dengan mempertimbangkan berbagai komponen, yaitu dinilai dari Latihan, Repeating, Kuis, serta Simulasi 1 dan Simulasi 2. Secara umum persaingan diantara para siswa cukup ketat. Dari hari-ke hari urutan ranking berubah-ubah. Baik dari segi kemampuan, hingga mental diuji setiap saat. Diakhir acara diumumkan 16 peserta yang berhasil lolos untuk mengikuti pembinaan tahap berikutnya Pembinaan Tahap 2 Pembinaan tahap 2 TOKI 2014 dilaksanakan di Jurusan Teknik Informatika, Institut Teknologi Sepuluh Nopember, Surabaya. Kegiatan telah berlangsung pada tanggal 1 - 20 Maret 2015. Sehari sebelum penutupan, para peserta menjalani simulasi akhir yang merupakan poin penilaian terakhir dalam rangkaian pembinaan dan seleksi TOKI 2015 ini. Menurut Bpk. Rully Soelaiman, S.Kom. M.Kom. selaku Pembina dari ITS, selama tiga minggu pelaksanaan pembinaan, para peserta telah mendapatkan berbagai tambahan materi serta mengikuti latihan harian, repeating, 2 kali kuis dan 2 kali simulasi. Seluruh aktivitas pelatihan dilaksanakan dengan memanfaatkan sistem TOKI Learning Center versi terbaru yang dipersiapkan untuk pelaksanaan APIO 2015. Dalam acara penutupan, Bpk. Suharlan S.H. MM. dari Direktorat Pembinaan SMA, Kementerian Pendidikan dan Kebudayaan RI menyampaikan bahwa siapapun nanti yang lolos jangan terlalu
berbangga diri karena perjuangan masih panjang, bagi yang gagal, jangan putus asa karena masih banyak ajang lomba keilmuan yang bisa diikuti untuk mengharumkan nama bangsa dan Negara. Acara di ditutup dengan penayangan dokumentasi kegiatan pelatnas 2 dan pengumuman 8 siswa yang berhasil lolos dan berhak mengikuti pembinaan dan seleksi TOKI 2015 tahap selanjutnya. Pembinaan Tahap 3 Delapan peserta mengikuti pembinaan tahap 3 di kampus Departemen Ilmu Komputer, Institut Pertanian Bogor pada tanggal 20 April s.d. 10 Mei 2015. Kegiatan pembinaan ini sekaligus untuk melakukan seleksi, memilih 4 siswa terbaik yang akan mewakili Indonesia di ajang IOI 2015. Selama pembinaan, para siswa telah mengerjakan 48 soal latihan, 3 soal kuis dan 6 soal simulasi. Pada hari terakhir, para siswa mengikuti APIO 2015 yang hasilnya juga menjadi pertimbangan dalam penentuan peserta terbaik. Penutupan kegiatan dilaksanakan setelah para siswa mengikuti APIO 2015 sekaligus dilakukan pengumuman 4 siswa terbaik sebagai anggota TOKI 2015. Pembinaan Tahap 4 Empat siswa yang telah terpilih untuk mewakili Indonesia dalam IOI 2015 akan mengikuti pembinaan tahap akhir sebelum keberangkatan mereka ke Almaty, Kazakhstan pada tanggal 26 Juli 2015 yang akan datang. Pembinaan akan dilaksanakan di kampus Fasilkom Universitas Indonesia, Depok sekitar bulan Juni/ Juli 2015. Dengan lebih menekankan kepada latihan soal, diskusi dan simulasi soal-soal IOI. Kita doakan bersama semoga semua jerih payah dan usaha yang telah dilakukan ini terbayar lunas dengan prestasi terbaik untuk mengharumkan nama bangsa di dunia Internasional.
5
INDONESIA,
TUAN RUMAH APIO 2015
A
oleh : Ivan Hendrajaya, S.Kom Alumni TOKI Anggota Technical Committee APIO 2015
sia-Pacific Informatics Olympiad (APIO) merupakan Olimpiade Informatika yang diikuti oleh negara-negara di wilayah Asia-Pasifik. APIO digunakan sebagai salah satu persiapan bagi negara-negara peserta menuju International Olympiad in Informatics (IOI). Terdapat 27 negara yang mengikuti APIO 2015. Setiap negara dapat mengirimkan maksimum 600 peserta, tetapi hanya 6 peserta terbaik yang nilainya tidak 0 dari setiap negara yang akan menjadi bagian dari tim resmi negara tersebut (kecuali jika terdapat peserta dengan nilai yang sama). China menjadi negara dengan peserta terbanyak yaitu 366 peserta. Indonesia sendiri diwakili oleh 8 peserta yang juga merupakan peserta Pembinaan ta-
6
hap 3 TOKI 2015. APIO 2015 merupakan salah satu komponen penilaian yang digunakan untuk memilih 4 peserta terbaik yang akan mewakili Indonesia pada IOI 2015 di Kazakhstan. APIO 2015 dilaksanakan secara online dengan 3 soal yang harus diselesaikan dalam waktu 5 jam. Setiap peserta mengikuti APIO pada tempat dan waktu yang ditentukan oleh masing-masing negara dengan diawasi oleh panitia lokal. Indonesia melaksanakan APIO 2015 di Departemen Ilmu Komputer (ILKOM) Institut Pertanian Bogor (IPB) pada hari Sabtu, 9 Mei 2015. Setelah Australia, Thailand, India, China, Iran, Japan, Singapore, Kazakhstan yang menjadi tuan rumah penye-
APIO 2015 di beberapa Negara
Macau re
Singapo
Armenia
lenggaraan APIO sejak tahun 2007 hingga tahun 2014, Indonesia dipercaya menjadi tuan rumah penyelenggaraan APIO 2015. Panitia APIO 2015 terbagi menjadi 3, yaitu Organizing Committee (menangani peserta), Scientific Committee (menangani urusan akademik/soal-soal), dan Technical Committee (menangani permasalahan teknis sistem untuk lomba). Selain menjadi tempat pelaksanaan APIO 2015, ILKOM IPB juga menjadi “Control Center” penyelenggaraan APIO 2015. Panitia APIO 2015 berkumpul untuk menjaga kelancaran lomba dari segala aspek. APIO 2015 menggunakan sistem Judgement Angels (Judgels) yang dibangun oleh Ikatan Alumni - Tim Olimpiade Komputer Indonesia (IA-TOKI). Saat ini Judgels masih berada dalam versi beta, tetapi Judgels sudah digunakan untuk Tim APIO 2015, Alumni TOKI
Pelatnas 2 TOKI 2015, Pelatnas 3 TOKI 2015, dan beberapa kontes terbuka. Selain itu Judgels juga akan digunakan untuk Olimpiade Sains Nasional (OSN) 2015 Bidang Informatika di Yogyakarta. Saat ini Judgels sudah menjadi proyek open source (dapat diakses di https://github. com/ia-toki/judgels). Hal ini dilakukan agar pengembangan Judgels dapat berjalan semakin cepat. Secara keseluruhan APIO 2015 berjalan dengan baik, meskipun tidak terlepas dari beberapa permasalahan. Sebuah kebanggaan tersendiri bagi Indonesia untuk dapat menjadi tuan rumah APIO yang pertama kali diselenggarakan pada tahun 2007. Semoga pada tahuntahun mendatang Indonesia dapat kembali dipercaya menjadi tuan rumah eventevent internasional seperti APIO dan IOI.
image : yorku.ca
PERLUNYA MATEMATIKA INFORMATIKA BAGI SISWA OLIMPIADE Oleh : Julio Adisantoso, M.Kom. Pembina Tim Olimpiade Komputer Indonesia Dosen Ilmu Komputer, Institut Pertanian Bogor
S
eseorang tampak termangu dan wajah berkerut di meja belajar saat membaca soal Olimpiade Sains Nasional bidang Informatika Tingkat Provinsi (OSP). Dia sangat berkeinginan untuk dapat lolos OSP sehingga dapat melaju ke tingkat nasional (OSN). Salah satu soal yang membuat berpikir keras adalah “Ada berapa banyak 0 di belakang representasi desimal dari 200! ?” [S1]. Dia membayangkan bagaimana cara menghitung 200! (200 faktorial), berarti 200x199x... x1? Kalkulator pasti tidak mampu, apalagi dalam olimpiade ini tidak diperkenankan menggunakan kalkulator. Soal lain yang dia bingung adalah, “Pak Dengklek memiliki 3 buah takaran air (A, B, dan C), masing-masing volumenya adalah 35 ml, 48 ml, dan 1000 ml. Jika Pak Dengklek ingin mengambil tepat 22 ml air, maka Pak Dengklek dapat melakukannya dengan menggunakan tiga langkah penakaran, yaitu: takar 2 kali dengan takaran A (2x35=70 ml) yang dituangkan ke takaran C, lalu kurangkan dengan 1 kali takaran B (70-48=22). Jika Pak Dengklek ingin mengukur tepat 10 ml
8
air, berapakah minimal penakaran yang diperlukan?” [S2]. Dua ilustrasi tadi merupakan situasi yang sering dihadapi oleh siswa yang memang belum banyak memahami materi uji dalam olimpiade komputer, baik OSK maupun OSP. Salah satu materi uji dalam OSK dan OSP adalah analitika, logika, dan aritmatika. Untuk dapat memahami komponen ini, siswa harus dibekali oleh kemampuan di bidang Matematika Informatika. Kompetensi yang diharapkan di bidang Matematika Informatika ini adalah mampu memahami dan memakai berbagai teori dan konsep matematika untuk menyelesaikan persoalan-persoalan yang berhubungan dengan bidang informatika yang meliputi: 1. Konsep bilangan bulat dan operasinya (modulo, tambah, kurang, dsb); 2. Faktorisasi; 3. Logika dan aljabar boolean (and, or, xor, not); 4. Himpunan (definisi, operasi, inklusi, eksklusi); 5. Permutasi dan Kombinasi; serta
6. Teori graf (definisi, graf berarah, bidireksional, traversal, shortest path). Jika bekal topik Matematika Informatika sudah cukup diberikan kepada siswa, maka ilustrasi soal [S1] dapat diselesaikan dengan mudah, menggunakan konsep keterbagian dan faktorisasi prima, sehingga tidak perlu menghitung nilai dari 200 faktorial, yaitu [200/5]+[200/25]+[200/125]+... = 49. Jadi ada 49 angka 0 di belakang dari representasi 200!. Mudah kan?! Mengapa bisa demikian? Tanpa memahami konsep keterbagian dan faktorisasi prima, sulit bisa menerima solusi tersebut. Ternyata ada teori yang menyatakan bahwa setiap bilangan bulat positif, selain bilangan prima, dapat difaktorkan menjadi dua atau lebih faktor-faktor bulat penyusunnya. Apabila proses ini diteruskan, maka kita akan dapatkan sebuah representasi dari bilangan tersebut sebagai perkalian dari bilangan-bilangan prima. Dan representasi ini bersifat unik. Sebagai contoh, 60 = 223151. Kita dapat pula menulis 60 = 2231517090 misalnya, jika lebih sesuai dengan konteksnya. Dengan teori ini, kita dapat memandang setiap bilangan bulat positif > 1 seolah-olah sebagai himpunan dari kumpulan bilanganbilangan prima (yang boleh berulang). Contoh lain, berapa faktor persekutuan terbesar (fpb) dari 1176 dan 1260 ? Karena 1176 = 233172 dan 1260 = 22325171, maka dapat diperoleh fpb(1176,1260) = 223171 = 84. Banyak sekali manfaat dari faktorisasi prima ini. Cobalah cari yang lain! Nah, kembali ke ilustrasi soal [S1], karena setiap bilangan dapat ditulis sebagai faktorisasi prima, maka 200!=(2p5q)r. Kita tertarik hanya kepada faktor prima 2 dan 5 karena hasil kalinya menghasilkan sejumlah angka 0 di belakang. Nilai 200! = 1.2.3.4.5.6...200. Dengan demikian, setiap bilangan ke-5, ke-25, …, ke-5^s akan memunculkan banyaknya nilai 0. Oleh karena itu, banyaknya bilangan 0 pada
representasi 200! dapat dihitung dengan [200/5]+[200/25]+[200/125]+... = 49. Demikian pula untuk ilustrasi soal [S2]. Siswa harus memiliki kemampuan di bidang keterbagian, faktor persekutuan terbesar (fpb), Extended Euclid, dan konsep linier Diophantine. Persoalan pada ilustrasi soal [S2] dapat direpresntasikan dalam bentuk persamaan Ax+By=Z=10. Artinya, berapa nilai x dan y sehingga 35x+48y=10. Tentunya tidak semua bilangan bulat x dan y dapat memenuhi persamaan tersebut. Untuk memeriksa kondisi ini, terdapat teori Bezout’s yang menyatakan bahwa Jika d = fpb(A,B) maka ada x dan y bulat sedemikian rupa sehingga d=Ax+By, dan Z=Ax+By jika dan hanya jika fpb(A,B) adalah pembagi dari Z. Dari persoalan tadi, fpb(35,48)=1 yang merupakan pembagi dari 10. Oleh karena itu, dapat dipastikan ada x dan y sehingga 35x+48y=10. Untuk mendapatkan nilai x dan y, dibutuhkan algoritme tertentu yang mendukung, yaitu Extended Euclid seperti berikut: function extended_gcd(a,b) x:=0; lastx:=1; y:=1; lasty:=0; while b<>0 q:=a div b; a,b):=(b, a mod b); (x, lastx):=(lastx-q*x, x); (y, lasty):=(lasty-q*y, y); return (lastx, lasty)
Selain mendukung penyelesaian soal-soal analitika (OSK dan OSP), Matematika Informatika juga memegang peranan yang sangat penting pada tahap pembentukan solusi algoritmik yang nantinya akan diimplementasikan pada soal-soal pemrograman (OSN). Oleh karena itu, guru-guru pembimbing juga perlu memahami beberapa teori dan konsep Matematika Informatika agar dapat membantu siswa yang akan berjuang di ajang olimpiade informatika ini.
9
Bahas Soal :
Soal Cat Rumah (OSN 2014 Sesi 1) Pembahasan oleh : Ammar Fathin Sabili Deskripsi Soal : Pak Dengklek ingin mengecat rumahnya dengan warna favorit bebek-bebeknya yang bisa didapatkan melalui mencampurkan tiga warna dasar (M cc warna merah, K cc warna kuning, B cc warna biru) ke dalam sebuah ember berkapasitas 1.000 cc (M + K + B = 1.000 | M, K, B ϵ riil). Pada suatu waktu, Pak Dengklek dapat menambahkan 1 warna dasar sebanyak sejumlah cc ke dalam embernya kemudian mencampurnya, selama total cc tidak melewati kapasitas ember. Pak Dengklek hanya dapat melakukan proses ini maksimal 100 kali. Lalu, bebek-bebek akan memberi tahu nilai kemiripan (F) antara warna favorit mereka dengan warna yang berada dalam ember Pak Dengklek saat ini setelah setiap proses penambahan dan pencampuran, yang dihitung dengan cara: • Isi ember Pak Dengklek saat ini adalah campuran X cc Merah, Y cc Kuning, Z cc Biru. • Jarak warna antara warna di ember dan warna favorit Bebek, yaitu W, adalah minimal dari (|kX - M| + |kY - K| + |kZ - B|) dengan k ϵ riil. • Setidaknya satu dari ketiga nilai |kX - M|, |kY - K|, atau |kZ - B| bernilai 0 untuk mendapat nilai W. • Formula Nilai kemiripan (F): max(0,100 - 4√W) Contoh: Nilai (M, K, B), (X, Y, Z) berturut-turut bernilai (200, 600, 200), (125, 200, 50), maka: Nilai W dihitung dengan meminimalkan (|kX - M| + |kY - K| + |kZ - B|), Kondisi |kX - M| = 0 |kY - K| = 0 |kZ - B| = 0
Nilai k 1.6 3 4
sehingga W = 225 dan Nilai F = 40.
Nilai (|kX - M| + |kY - K| + |kZ - B|) 400 225 500
Bantulah Pak Dengklek untuk mendapatkan nilai F sebesar mungkin sehingga cat Pak Dengklek semirip mungkin dengan warna favorit bebek-bebeknya! (Selama interaksi, program Anda harus mencetak TAMBAH [WARNA] [TAKARAN] atau SELESAI. Setelah mencetak perintah ini, program Anda akan menerima input sebuah bilangan riil F persen dengan 4 angka di belakang koma)
10
Contoh Interaksi Keluaran Program Peserta (Pak Dengklek) TAMBAH MERAH 100.0000 TAMBAH KUNING 123.4500 TAMBAH KUNING 76.5500 TAMBAH BIRU 50.0000 TAMBAH MERAH 25.0000 SELESAI
CONSTRAINT Kasus uji 1 Kasus uji 2 Kasus uji 3
Umpan Balik Grader (bebek)
Informasi Tambahan
0..3 0.0000
W = 800.0000
11.8159
W = 486.0267
30.7180
W = 300.0000
51.0102
W = 150.0000
40.0000
W = 225.0000
(interaksi sai)
sele-
: M = K, (M, K, B) ϵ bulat : B = 500, (M, K, B) ϵ riil : (M, K, B) ϵ riil
PEMBAHASAN Solusi : Pada dasarnya, kita diminta untuk mencari perbandingan dari ketiga warna. Pada contoh interaksi di mana nilai M, K, dan B berturut-turut adalah 200, 600, dan 200, perbandingan ketiga warna haruslah mendekati 1:3:1. Sehingga kita akan mendapatkan poin penuh apabila nilai X, Y, dan Z memiliki perbandingan 1:3:1. Dengan kata lain X = 10 cc, Y = 30 cc, dan Z = 10 cc atau X = 1.5 cc, Y = 4.5 cc, Z = 1.5 cc sama-sama bernilai 100. Berikut ini adalah ide solusi yang digunakan juri untuk mendapatkan poin berkisar 85-92.
Himpunan Kasus Uji 1 Perhatikan constrain, maka hanya terdapat 500 kemungkinan nilai M,K,B yakni (0,0,1000) , (1,1,998) , (2,2,996) , ... , (500,500,0). Apabila tidak ada batasan pemanggilan perintah TAMBAH, maka bisa dicoba semua 500 kemungkinan tersebut. Karena adanya batasan, kita tidak dapat mencoba semua kemungkinan perbandingan. Solusinya adalah TERNARY SEARCH karena nilai akan maksimal (100%) pada suatu titik dan mengecil apabila menjauh dari titik kemungkinan tersebut.
Bersambung ke halaman 13 ....
11
Bahas Soal :
Soal Essay no. 50 OSP 2015 Pembahasan oleh : Jessica Handojo
P
ak Dengklek memiliki sebuah array berisi N bilangan bulat non-negatif. Pak Dengklek pun menantang Anda untuk memilih angka-angka dari arraynya yang jika dijumlahkan habis dibagi N. Tentu saja angka di suatu index tidak boleh dipilih lebih dari sekali. Apabila hal ini mungkin, beritahu Pak Dengklek berapa banyak angka yang Anda ambil dan apa saja angka-angkanya. Apabila hal ini tidak mungkin, katakan “Tidak mungkin”. Format Input : Baris pertama berisi sebuah bilangan bulat N (2 <= N <= 100000) Baris kedua berisi N bilangan bulat non-negatif yang menyatakan isi array Pak Dengklek Format Output : Apabila mungkin, pada baris pertama keluarkan sebuah angka yang menyatakan banyaknya angka yang Anda ambil dari array Pak Dengklek, dan pada baris kedua keluarkan angka-angka yang Anda ambil dipisahkan oleh sebuah spasi. Apabila tidak mungkin, pada baris pertama keluarkan sebuah string “Tidak mungkin” tanpa tanda petik. Contoh Masukan
Contoh Keluaran
3 4 1 2
2 42
3 4 4 4
3 444
PEMBAHASAN
Dengan penjelasan Pidgeonhole Principle, soal ini akan SELALU memiliki jawaban. Tujuan solusi adalah mencari sebuah pasangan (a, b) sedemikian sehingga jumlah seluruh elemen array dari index a .. b jika dijumlahkan akan habis dibagi N. Contohnya dengan array masukan {2, 3, 8, 4, 1}, pasangan yang valid adalah (1, 2), (2, 4), (4, 5). Pertanyaannya, mengapa kita cukup mencari dari rangkaian elemen array terurut saja tanpa memperhatikan penjumlahan elemen array yang tidak berurutan (seperti pada contoh keluaran pertama)? Di sinilah Pidgeonhole Principle bekerja.
12
Mari mulai dari sebuah fungsi, yaitu fungsi prefixSum(x) dengan prefixSum(x) = (jumlah elemen array dari index 1 .. x) modulo N. Contohnya, pada contoh masukan pertama, prefixSum(1), prefixSum(2), prefixSum(3) berturut-turut adalah 1, 2, 1. Perhatikan bahwa prefixSum(0), artinya tidak mengambil elemen apapun, akan selalu bernilai 0. Pada fungsi prefixSum(x), x memiliki rentang dari 0 .. N sehingga ada (N + 1) nilai prefixSum(x). Sementara, prefixSum(x) selalu dihitung dalam modulo N, maka hanya akan terbentuk N nilai prefixSum(x) yang berbeda, yaitu dari 0 .. (N – 1). Terdapat (N + 1) buah hasil penghitungan dan hanya N buah nilai yang mungkin tercipta. Artinya, minimal ada 1 nilai dari 0 .. (N – 1) yang berulang. Asumsikan posisi dengan nilai yang berulang adalah index X dan Y. Maka, elemen-elemen array dari (X+1) .. Y jika dijumlahkan akan habis dibagi N (karena prefixSum(Y) – prefixSum(X) = 0). Inilah jawaban yang dicari, yaitu pasangan (X+1, Y). //-- Membaca input N dan array ke dalam ar – for (int i=1; i<=N; i++) prefixSum[i] = (prefixSum[i-1] + ar[i]) % N; memset(cek,-1,sizeof(cek)); for (int i=0; i<=N; i++) { if (cek[prefixSum[i]] != -1) { x = cek[prefixSum[i]] + 1; y = i; break; } else cek[prefixSum[i]] = i; }
... dari halaman 11
//-- Mencetak jawaban, yaitu ar[x], ar[x+1], .. , ar[y] --
Himpunan Kasus Uji 2 Nilai B adalah 500, sehingga kita hanya perlu mencari tahu nilai M dan K. Perbandingan yang mungkin terjadi berkisar antara 1:0:1 hingga 0:1:1, yaitu ketika nilai M,K,B adalah (500,0,500) dan (0,500,500). Solusinya adalah TERNARY SEARCH dengan domain range X berkurang dan range Y bertambah. Salah satu nilai tengah yang dapat diambil yakni dengan terlebih dahulu mendapatkan perbandingan X:Y:Z = 1:1:1, kemudian mencari tahu dominan di daerah merah atau daerah kuning.
Himpunan Kasus Uji 3 Tidak ada konstrain tambahan, perbandingan warna dapat dipatok secara random. Apabila satu warna telah dipatok perbandingannya, maka kasusnya menjadi mirip dengan Himpunan Kasus Uji 2. Misalnya kita patok perbandingan B = 1, sehingga perbandingan M:K:B adalah ?:?:1. Nilai tanda tanya bisa apa saja, tidak seperti Himpunan Kasus Uji 2 di mana nilai tanda tanya berkisar 0-1. Solusi yang digunakan tetap TERNARY SEARCH tetapi dengan range yang lebih luas.
13
BINCANG-BINCANG
ALUMNI TOKI
M
enjadi anggota Tim Olimpiade Komputer Indonesia bisa jadi merupakan impian ribuan pelajar SMA di seluruh Indonesia. Tak pelak lagi, meskipun perjuangan panjang harus dilalui, dan tidak mustahil banyak hal harus dikorbankan oleh peserta, namun setiap tahun semakin banyak saja para pelajar yang memperebutkan tempat menjadi anggota TOKI. Bertanding di ajang lomba nasional, bahkan internasional bukanlah tujuan akhir dari perjalananan ini, bisa jadi baru merupakan langkah awal atau batu pijakan untuk jalan masa depan para siswa. Jessica Handojo, tim redaksi TOKInews yang juga alumni TOKI, mewawancarai 3 orang alumni TOKI tentang bagaimana pengalaman sebagai anggota TOKI dalam pendidikannya. Berikut ini hasil wawancara tersebut, semoga kisah ini dapat menginspirasi para peserta OSN 2015 ini, berikut hasil wawancaranya :
NATHAN AZARIA
(National University of Singapore, TOKI 2012-2013, IOI 2012 – Perak, IOI 2013 – Perak) Dampak positif yang paling terasa adalah beasiswa pendidikan. Dari medali perak saya di IOI 2012, saya mendapatkan beasiswa studi dari Kementrian
14
Jessica Handojo
Pendidikan RI sampai tingkat S2. Selain itu, saya bertemu Dr. Steven Halim, salah satu dosen saya di NUS pada saat IOI 2012 di Italia. Dari situ, saya mendapatkan kemudahan masuk NUS (tidak perlu mengikuti tes masuk, diterima dari medali IOI). Selain itu, saya juga tidak perlu mengambil beberapa modul (mata kuliah) dasar di NUS seperti “CS1010 Programming Methodology” dan “CS1020 + CS2010 Data Structures and Algorithms I and II”. Tidak lupa, karena sudah biasa dengan algoritma di OSN, beberapa mata kuliah yang berhubungan dengan algoritma juga terasa lebih mudah untuk dijalani. Terutama karena beberapa algoritma yang dipelajari pada mata kuliah tersebut sudah diajarkan di Pelatnas TOKI.
ALFONSUS RADITYA ARSADJAJA
(Institut Teknologi Bandung, TOKI 20132014, IOI 2014 – Perunggu) Pengalaman OSN hingga IOI adalah hal baru dan berat untuk saya. Menyesuaikan ke dalam kehidupan OSN dan pelatnas membutuhkan perjuangan keras dan konsisten. Akan tetapi, saat sudah terbiasa, banyak sekali keuntungan yang didapatkan. Seperti, kemampuan untuk menganalisis meningkat drastis, logika juga terasah menjadi jauh lebih kuat dari sebelumnya. Kemampuan ini sangat ber-
guna saat sudah lulus SMA. Selain itu, saya mendapat banyak teman dengan ketertarikan yang sama dan mendapat pengalaman ke luar kota, menjelajahi kota yang belum pernah dikunjungi sebelumnya. Apalagi saat sampai tingkat internasional, bisa mengunjungi negara lain. Selain itu, pada studi tingkat universitas, saya menerima beasiswa karena meraih medali perunggu di IOI. Sebenarnya rangkaian OSN, pelatnas, sampai IOI itu berguna dan menyenangkan! Yang penting terus berusaha, jangan pernah menyerah, dan jangan pernah putus asa! Banyak orang mulai putus asa jika menemukan sesuatu yang sangat sulit untuk dicapai. Padahal sebenarnya itu adalah pengasah kita sehingga bisa mewakili Indonesia di IOI, serta mendapatkan pengalaman yang menarik dan tidak akan pernah dialami selanjutnya. Akhir kata, Go Get Golds!
ZAMIL MAJDY
(Universitas Indonesia, TOKI 2014, IOI 2014 – Perunggu) Banyak manfaat dan dampak positif yang saya dapatkan karena mengikuti TOKI. Pengalaman di TOKI dan IOI mempermudah saya dalam melanjutkan studi saya di perguruan tinggi (Universitas Indonesia) tanpa harus mengikuti tes/ujian lagi, yang mungkin saya sendiri belum tentu mampu masuk dengan mengikuti tes/ujian karena kekurangan saya pada beberapa pelajaran tertentu.. Dengan mengikuti IOI juga membuat saya bisa berkuliah tanpa menyulit-
NATHAN AZARIA
ALFONSUS RADITYA
ZAMIL MAJDY kan orang tua, saya bisa mendapat beasiswa selama kuliah, dari masuk sampai lulus nanti. Pengalaman tersebut juga membantu saya dalam kuliah selama ini, karena di rangkaian OSN hingga IOI saya belajar bagaimana cara memecahkan masalah, ketertarikan untuk belajar halhal baru, semangat untuk belajar, dan ketertarikan terutama pada bidang pemrograman. Pengalaman ini membuat saya mampu belajar dengan lebih mudah dan membuat belajar menjadi lebih menarik dan tidak membosankan. Saya juga mendapat banyak teman yang secara umum memiliki ketertarikan yang sama, sehingga saya bisa berdiskusi dan bertanya jika mengalami kesulitan.
15
Hall of Fame Muhammad Ayaz Dzulfikar, SMA YP Vidya Dahana Patra Bontang
Ayaz mulanya memperoleh medali perunggu pada OSN 2013. Sejak itu, Ayaz berkembang pesat dan mencapai Pelatnas 3 TOKI 2014. Meskipun tidak terpilih sebagai empat besar TOKI 2014, ia terus giat berlatih. Hasil latihannya berbuah pada OSN 2014 dengan perolehan medali emasnya. Pria asal Bontang ini merupakan pribadi yang ceria dan selalu memiliki ide-ide cemerlang dalam penyelesaian soal latihan.
Michael Wibawa, SMA Kanisius Jakarta
Pelatnas TOKI 2015 merupakan kesempatan kedua bagi peserta yang akrab dipanggil “MW” ini. Pada OSN 2013, MW memperoleh medali perak dan tembus hingga Pelatnas 3 TOKI 2014. Tahun berikutnya, MW memperoleh medali emas OSN 2014 dan terpilih sebagai anggota empat besar TOKI 2015. Ciri khas dari MW adalah sifatnya yang “cool” dan selalu tenang. Di kala peserta lainnya terlihat tegang saat mengerjakan soal latihan, ia terlihat santai dan duduk tenang. Ketika ia mulai coding, biasanya nilai 100 sudah terjamin di tangannya.
Agus Sentosa Hermawan, SMA Petra 2 Surabaya
Agus memperoleh medali pertamanya pada OSN 2013, yaitu medali perunggu. Setelah melalui perjalanan panjang, Agus sampai pada Pelatnas 3 TOKI 2014. Ia tidak terpilih sebagai empat besar TOKI 2014, tetapi ia tetap semangat untuk berlatih. Agus kembali berpartisipasi pada OSN, dan ia memperoleh medali emas peringkat pertama pada OSN 2014. Selama Pelatnas, Agus merupakan peserta yang sangat gigih dan giat berlatih. Ia memiliki pengetahuan yang luas seputar algoritma dan struktur data.
Stacia Edina Johanna, SMA Petra 3 Surabaya
Pada OSN 2013, Stacia tidak memperoleh medali. Meski tanpa mengikuti Pelatnas, kemampuannya bisa meningkat drastis hanya melalui latihan secara mandiri. Stacia memperoleh medali emas pada OSN 2014, dan memiliki prestasi yang konsisten selama rangkaian Pelatnas TOKI 2015. Ia pun memiliki kemampuan khusus pada materi yang biasanya kurang dikuasai peserta lain, sehingga seringkali Stacia menjadi peserta satu-satunya yang menyelesaikan soal latihan tersebut.
