Pembahasan Soal Olimpiade Komputer UNISBANK 2013

Jadi ini editorial pembahasan lomba gw yang pertama. Kalo masih cacat harap dimaklumi ya. Lomba olimpiade Komputer UNISBANK adalah lomba programming untuk siswa/i SMA atau sederajat non-OSN (belum pernah dapat medali OSN) se-Jawa Tengah. Lomba ini bekerjasama dengan TOKI Biro UGM (soal dibuat TOKI Biro UGM). Oh ya, bahasa yang diperbolehkan di lomba ini hanya Pascal, karena emang target lomba ini bagi para newbie yang baru belajar Competitive Programming. Gw di sini cuma jadi pelatih dari tim SMA gw, karena sekarang sudah mahasiswa (berasa tua). Tapi lumayan lah, bisa nganterin sampai bisa bawa pulang juara 3. Anyway, kalao ada saran/ kritik/ sugesti algo yang lebih bagus atau algo gw salah silakan comment yak!

Soal bisa diunduh di sini

A. Segitiga

Sort arraynya, terus bruteforce (coba semua kemungkinan) 3 lapis buat nentuin apakah 3 pasangan itu bisa dibuat segitiga atau gak. Definisi bisa dibikin segitiga jika jumlah panjang 2 sisi terpendek < panjang sisi terpanjang. Karena sortingnya pake quicksort (paling cepat) yang kompleksitasnya O(n log n) dan bruteforce 3 lapis, kompleksitasnya O(n log n+n^3)=O(n^3). Untuk n=500 berarti 500^3=125 jt proses, mepet dikit sama waktu test case (1 detik=100 juta proses). Tapi kayaknya bruteforce bisa tembus. Sortnya pake quicksort, lebih cepat daripada bubble sort yang n^2 (kalo di cpp udah ada sort(v.begin(),v.end()) yang otomatis quick sort, pascal harus bikin sendiri)

Solusi: http://ideone.com/cyBP55

B. Truk Kontainer

Bruteforce dengan bitmask. Awalnya gw pikir ini soal dikerjakan dengan DP Knapsack, tapi setelah melihat batasan constraintnya 2 Milyar dan n=20, maka kalau kita buat tabel DP sebanyak 20×2 Milyar kena verdict Memory Limit Exceeded. Tapi, setelah melihat permasalahan ini, ternyata bisa diselesaikan dengan cara Brute Force (coba semua kemungkinan) dengan cara yang ‘sedikit elegan’. Kalau dilihat, barangnya hanya sampai 20. Berarti total kemungkinan cara pengambilannya adalah 2^20 sekitar 1 jutaan. Cara menyelesaikan permasalahan ini adalah dengan menggunakan teknik “Bitmask”. Apa itu “Bitmask” ? Silakan baca di buku Competitive Programming 2 halaman 23-24. Jadi, kita coba representasikan n barang tersebut dalam n digit biner. Bila digit ke-i bernilai 1, maka kita ambil barangnya. Bila bernilai 0 maka tidak diambil. Tinggal coba loop dari kemungkinan

00000000000000000000 sampai 11111111111111111111, itu untuk kasus n=20. Solusinya adalah sebagai berikut:

Solusi: http://ideone.com/seQWiK

C. Tugas Kelompok

Soal ini dapat diselesesaikan dengan Union Find Disjoint Set (Buku Competitive Programming 2 halaman 30-32). Apa itu Union Find Disjoint Set? Silakan baca sendiri di buku CP2 . Intinya UFDS digunakan untuk menentukan apakah suatu elemen satu dan yang lain terletak pada Himpunan yang sama atau tidak.

Solusi: http://ideone.com/IiM2m3

D. Kandang Kambing Empat

Ini satu-satunya soal yg gw nyerah. Gak ketemu formula DPnya. Akhirnya gw tanya temen gw. Awalnya gw pikir ini soal DP. Dan setelah gw tanya Gozali (temen gw, TOKI 2011), solusi dia jg DP dengan kompleksitas yang awalnya O(n^2) dan berhasil diminimalsisasi DP dengan kompleksitas O(n) dan solusi ini udah safe. Tapi dateng solusi dari Febry+Ashar(temen dan senior gw, TOKI 2011 dan TOKI 2010) yang datang dengan solusi kombinatorik dengan kompleksitas O(n). Terus diperbaikin Gozali jadi kompleksitasnya O(1) alias cepet parah!!! Nah, kalo gitu gw mulai penjelasannya dari solusi kombinatorik Febry+Ashar yang O(n) karena paling gampang dimengerti, baru masuk minimalisasi Gozali biar jadi O(1).
Nah, solusi Febry memisalkan kambing dengan angka 0 dan sekat kandang dengan angka 1. Misalkan ada 5 kambing (kandang pasti hanya ada 4). Maka representasi 5 kambing adalah 00000. Nah, representasi 5 kambing dalam 1 ruangan adalah 1000001 Maksudnya kelima kambing tersebut (direpresentasikan 0) diapit 2 sekat ruangan (direpresentasikan angka 1) atau bisa juga hanya 00000. Nah, jadi bila ada representasi 001000 berarti ada 2 ruangan, dengan ruang 1 ada 2 kambing dan ruang 2 ada 3 kambing. Nah, kita punya ada n kambing dan 4 ruangan, awalnya n kambing tersebut dimasukkan semua ke ruang 1, sedangkan ruang 2, 3 dan 4 kosong. Representasinya:
000000…(sebanyak n)…000  111
Nah, berarti sekarang kita punya n+3 digit. Salah satu representasi lain misalnya:
00000…(sebanyak n-6)…000 1 00 1 0 1 000, kenapa (n-6)? karena ada 6 kambing yang sudah masuk di ruang 2 (ada 2),3 (ada 1) dan 4 (ada 3). Berapa banyak cara kita menempatkan 3 digit angka 1 di (n+3) digit angka? Jawabnya tinggal menghitung (n+3)C3 kan? Tapi ingat, itu baru cara menempatkan n kambing. Padahal pak blangkon bisa saja memberikan dari 0 kambing, 1 kambing, 2 kambing  …. n kambing. Sehingga kita harus looping dan menjumlahkan dari i=0 sampai n untuk jumlahan dari (i+3)C3 . Sehingga kompleksitasnya menjadi O(n).
Ternyata ini masih bisa dioptimisasi lagi sama Gozali. Bagaimana caranya? Awalnya kita hanya punya 4 ruang. Formula di atas hanya bisa digunakan untuk menghitung n kambing dalam 1 waktu. Sehingga untuk menghitung konfigurasi ruang dari kambing=0 sampai n diperlukan loop n kali. Bagaimana menghitung konfigurasi semuanya dalam 1 waktu? Ide dari Gozali dengan menambah 1 ruangan lagi yang disebut “Ruang Buangan” (sedih amat namanya) . Tapi emang sesuai namanya, kambing yang masuk “Ruang Buangan” sama aja kayak nggak dihitung. Artinya misalkan ada x kambing yang masuk “ruang buangan”, berarti sama aja kayak kita menghitung konfigurasi (n-x) kambing dalam 4 ruangan kan? Jadi misalkan awalnya representasinya:
00000…(sebanyak n)…000 1 1 1 1 1 //Ingat ada 1 tambahan “Ruang Buangan” yang terletak di paling kanan.
bila kita ingin menghitung konfiguras (n-1) kambing representasinya:
00000…(sebanyak n-1)…000 1 1 1 1 0
Nah, sehingga banyak konfigurasinya tinggal menghitung berapa banyak menempatkan 4 buah angka 1 dalam (n+4) digit. Jawabannya adalah:
  (n+4)C4 = (n+4)(n+3)(n+2)(n+1)n!   /    ( n! * 4!)
  (n+4)C4=(n+4)(n+3)(n+2)(n+1)/24
E. Petani dan Kambing

Utak-atik Trigonometri, geometri sederhana.

Jadi, misalkan kita punya segitiga seperti ini :

segitiga_2

Si petani berada di titik merah dan kambing di titik hijau. Sekarang pertanyaannya berapa panjang x yang menghubungkan titik merah dan hijau? Langkah pertama tarik dari titik hijau ke sisi b sehingga kita dapat garis yang melewati titik hijau dan tegak lurus sisi b, misalkan kita beri nama t. Dan misalkan sudut antara sisi c dan b adalah alfa

segitiga_3

Bagaimana cara mencari nilai alfa? Pertama, kita cari Luas segitiga secara keseluruhan. Bagaimana? Kita sudah punya data sisi a, b dan c. Nilai Luasnya jika diketahui ketiga sisinya adalah :

Luas:= sqrt(s * (s-a) * (s-b) * (s-c) ); dimana s adalah (a+b+c)/2.

Nah, kita sudah punya luasnya bagaimana mencari alfa? Alfa diapit oleh sisi b dan c. Luas segitiga bila diketahui 2 sisi dan sudut diantara kedua sisi tersebut adala:

L = (b *c * sin(alfa)) /2; berarti:

sin(alfa):= (2*L)/(b*c);

Bila kita lihat pada gambar, sin(alpha) juga berarti t/(c/2) hal ini karena titik hijau membagi sisi c menjadi 2 bagian yang sama panjang. Jadi nilai t adalah:

t:= sin(alpha)*(c/2);

segitiga_4

Kemudian misalkan sisi b dibagi menjadi 2 berdasarkan perpotongan dengan t: yaitu y dan (b-y). Dimana sisi y terletak di kanan t dan (b-y) di kiri t. Maka cos(alpha) akan sama dengan y/(c/2). Bagaimana mendapatkan cos(alpha) bila diketahui sin(alpha)? Gunakan identitas trigonometri, dimana

(sin_alpa)^2 + (cos_alpha)^2 = 1

berarti cos_alpha := sqrt(1-(sin_alpha)^2);

Berarti nilai y adalah cos_alpa*(c/2);

Nah, kita sudah dapat nilai (b-y) dan t. Berarti nilai x tinggal didapat dari Rumus Pythagoras biasa. Voila! Ketemu juga nilai X.

Solusi: http://ideone.com/bsDxhJ

==========================================================

Yup, sekian untuk pembahasan kali ini, kalau ada yang perlu dikoreksi feel free to comment. Btw ini lomba buat newbie, tapi soalnya udah mulai DP, bitmask, UFDS, dll. Gila, standarnya newbie sekarang udah harus nguasain ini. Jaman gw masih SMA, boro-boro tau DP itu apaan, modal cuma belajar logika+dasar pascal kayak searching+sorting aja (di tengah kesibukan gw di kelas akselerasi) gw masih bisa sampe propinsi. Dulu belajar DP aja jaminan lolos OSN. Sekarang semuanya udah jadi standar kali ya. Well, dulu gw cuma dapet 1 kali kesempatan OSN dan itu gw sia-siain. Pesan gw buat para coder muda yang baca postingan ini: “Jangan pernah sia-siakan kesempatan yang kalian punya!  Karena kesempatan gak dateng 2 kali.” <==Standar baget yak pesannya? Anyway, thanks udah berkunjung ke blog gw. Ciao!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s