TOKI Open Contest July 2014

Halo semua :)

Pada sabtu, 26 Juli 2014 kemarin, merupakan pertama kali saya handle contest di Toki Learning bersama dengan 2 teman saya, Jennifer Santoso dan Jessica Handojo. Mereka berdua merupakan alumni TOKI sedangkan saya alumni SMA saya saja =))

Saya mau terima kasih kepada :

1. Ashar Fuadi
2. Felik Junvianto
3. Pusaka Kaleb Setyabudi
4. Anthony

Atas kepercayaannya ke kita dalam handle contest, bantuan dalam mempersiapkan soal, dan dalam pelaksanaan kontesnya :)

Terdapat beberapa masalah dari sebelum mulai, bahkan ketika kontes dimulai. Kontes dimulai 15 lebih lama karena terdapat beberapa masalah teknis, dan pada saat kontes berlangsung, ternyata server sempat down, dan beberapa deskripsi soal yang kurang sehingga harus di ralat. Namun kita puas dalam pelaksanaannya dan pembagian soalnya. Karena TOKI Open Contest kali ini menggunakan format ACM ICPC, dan ada peraturan yang (mungkin) tertulis bahwa "Semua soal harus bisa di solve oleh minimal 1 team dan tidak ada team yang solve semua soal", dan di kontes ini, kondisi tersebut terpenuhi :) [YAY].

Soal 'The Legend Of Calory Runner' dari Jennifer Santoso menjadi soal penentu dan soal tersebut hanya bisa di solve oleh 1 orang yaitu Kevin Luvian :).

Para pembuat soal dalam kontes ini adalah :

1. DotA - Vincentius Madya [http://tokilearning.org/problem/1678]
2. Quick Count - Jessica Handojo [http://tokilearning.org/problem/1679]
3. The Legend Of Calory Runner - Jennifer Santoso [http://tokilearning.org/problem/1680]
4. O2Jam - Vincentius Madya [http://tokilearning.org/problem/1681]
5. Res-Dimension - Jennifer Santoso [http://tokilearning.org/problem/1682]

*Mungkin kalian harus login untuk melihat soal tersebut.

Dan top 10 dari contest kemarin adalah :

No.	User	Total	P5	P4	P3	P2	P1
1	> (emwe)	4 7:49	3 3:13	3 1:14	6 4:44	1 1:50	2 1:31
2	miris gan (miris_gan)	4 8:52	5 3:21	2 0:35	0 0:00	1 2:25	5 2:29
3	T.T (TryhardDoto)	4 11:39	10 5:46	1 0:39	0 0:00	3 2:21	7 2:51
4	Tjandra Satria Gunawan (tjandra)	3 4:30	0 0:00	1 1:30	0 0:00	2 1:02	1 1:58
5	Wynne Wijaya (wynnewijaya)	3 9:36	0 0:00	2 3:20	4 2:40	1 2:14	5 4:01
6	Kevin Luvian (senaidert)	3 10:10	0 0:00	2 1:04	10 5:35	0 0:00	4 3:30
7	PlayFap (PlayFap)	2 1:09	3 2:12	1 0:25	0 0:00	0 0:00	1 0:44
8	Jonathan Christopher (nathanchrs)	2 3:38	0 0:00	3 2:33	0 0:00	1 2:42	2 1:04
9	Andre (Rebirth)	2 3:59	0 0:00	2 1:25	0 0:00	1 2:34	1 2:58
10	Wira Abdillah (wirabdillah)	2 4:15	0 0:00	2 1:20	0 0:00	0 0:00	5 2:54

Kali ini saya akan membahas 2 soal yang saya siapkan :)

DotA [Dynamic Programming]

Kalian diberikan uang sebanyak G gold, dan kalian diberikan N list item dengan harga yang bervariasi. G kalian akan bertambah 1 gold setiap detik. Kalian bisa membeli barang apapun selama gold kalian mencukupi dan waktu untuk membeli dapat diabaikan. Tugas kalian adalah menghabiskan uang kalian (gold kalian menjadi tepat 0) dengan waktu menunggu seminimal mungkin. Konstrain :

• 1 <= N <= 1.000.000
• 1 <= G <= 5.000
• 1 <= Hi <= 1.000.000.000

Contohnya adalah, gold kalian 5 sedangkan ada 3 barang dengan harga masing masing {3 4 10}. Kalian bisa menghabiskannya dengan cara berikut :

1. Membeli barang 3 gold (gold sisa 2)
2. Menunggu 1 detik (gold bertambah 1 sehingga menjadi 3)
3. Membeli barang 3 gold (gold sisa 0)

Dengan demikian, gold kalian akan habis dan total waktu menunggu adalah 1 detik dan ini optimal.

Solusinya adalah menggunakan Dynamic Programming dengan digabungkan beberapa trick. Trick pertama adalah, kalian pasti akan hanya membeli barang yang lebih besar dari G hanya sekali. Trick ini akan menghasilkan jawaban awal dimana kita hanya membeli barang yang lebih besar dari G. Kita mencari untuk setiap i dimana Hi lebih besar dari G, maka jawaban = min(jawaban, Hi - G).

Dari trik pertama kita sudah mendapatkan jawaban secara Greedy, lalu kita masuk ke trick ke-2. akan ada maksimal G jenis barang yang akan kita pakai. Contohnya adalah misalkan N = 1.000.000, lalu G = 10, dan harga barang masing masing adalah {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, ..., 8, 9, 10} (ada 1.000.000 barang). Dari hal tersebut, kita hanya akan melihat harga {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Dengan kata lain, kalian dapat menghilangkan redundan.

Setelah mendapatkan barang yang dapat digunakan untuk penghitungan, maka disinilah fungsi Dynamic Programming. Relasi recurensnya kurang lebih seperti berikut :

DP(gold) = gold - G | Untuk gold >= G

DP(gold) = min(DP(gold + Bi)) | Untuk gold < G

Bi adalah list harga barang yang lebih kecil atau sama dengan G dan sudah dihilangkan redundannya.

Untuk mencegah computasi ulang oleh state yang sudah pernah dihitung, kalian bisa menggunakan teknik Memoization.

Untuk kontes kemarin, banyak kontestan yang lupa trick pertama, dimana mereka hanya menghitung harga barang yang lebih kecil atau sama dengan G, tanpa mengecek bagaimana jika kita membeli harga barang yang lebih besar dari G sekali.

O2Jam [Simulasi]

Pembahasan disini menggunakan asumsi bahwa kalian sudah pernah bermain O2Jam :)

Kalian diberikan note note yang akan jatuh pada detik detik tertentu, dan kalian akan diberikan simulasi penekanan yang dilakukan oleh pemain secara berurutan. (Untuk lebih jelas dalam pemahaman soal, kalian bisa baca deskripsi soal).

Disini, kalian hanya mensimulasikan penekanan. Pertama kalian bisa menyimpan note note tersebut dalam sebuah array 2 dimensi NOTE[X][Y], dimana X adalah nomor lajur, dan Y adalah detik. Dengan demikian adalah NOTE[X][Y] menandakan bahwa ada note yang harus ditekan di tombol ke-X dan di detik ke-Y.

Lalu untuk setiap penekanan yang dilakukan pemain, kalian tinggal mengecek mulai dari note paling awal muncul. Misalkan pemain menekan di tombol ke-A dan di detik ke-B, maka kita akan melakukan pengecekan terhadap :

1. NOTE[A][B-2] -> jika ada, maka akan menghasilkan Bad (25 point)
2. NOTE[A][B-1] -> jika ada, maka akan menghasilkan Good (50 point)
3. NOTE[A][B-0] -> jika ada, maka akan menghasilkan Cool (100 point)
4. NOTE[A][B+1] -> jika ada, maka akan menghasilkan Good (50 point)
5. NOTE[A][B+2] -> jika ada, maka akan menghasilkan Bad (25 point)

Untuk miss, kalian bisa menggunakan formula MISS = N - (BAD + GOOD + COOL).

Beberapa contestan menyadari dengan cepat bahwa soal ini merupakan soal mudah, meskipun menggunakan deskripsi yang sangat panjang. Tapi disitulah letak keasikannya :).

Akhir kata, terima kasih sudah mengikuti contest ini, semoga saya bisa berkontribusi lagi dalam TOKI Open Contest berikutnya :). Dan selamat juga buat pemenang :). Mohon maaf problem setter tidak menyediakan hadiah. Mudah mudahan ucapan selamat cukup untuk saat ini hahahaha. Doakan next kita bisa provide hadiah :). SEMANGAT DAN GO GET GOLD :)

Beberapa pemikiran pribadi saya yang sangat random :

1. Contestan lebih tertarik ke soal DotA dan soal O2Jam karena judul soal merupakan nama game yang populer pada masanya. Coba DotA diganti judulnya menjadi "Problem ngabisin duit" dan O2Jam menjadi "Pencet Pencet Tombol" sepertinya tidak ada yang tertarik.
2. Honorable Mention saya pribadi kepada Chalvin (chalvin96) dalam usahanya mencoba soal DotA sebanyak 27 Submission dan berakhir dengan Accepted :)

   15

   chalvin (chalvin96)

   2 13:02

   0 0:00

   1 1:30

   0 0:00

   0 0:00

   27 11:31

3. Waktu Tjandra WA dalam soal Quick Count, apakah solusi juri salah ? Ternyata benar :)
4. Bagaimana jika soal DotA merupakan kejadian nyata. Harga barang 1.000.000.000 Gold, mungkin effectnya adalah whosyourdaddy + thereisnospoon + iseedeadpeople. Terus bagaimana jika beneran ada yang menunggu 2700 detik dibandingkan creeping untuk membeli mystic staff ?
5. Saya membuat soal O2Jam untuk mempromosikan bahwa game O2Jam merupakan game yang menarik :). Kalian bisa memainkan game tersebut secara online di http://live.o2jam.asia/
6. Untuk pembahasan lainnya, tanya ke problem setter yang bersangkutan hwehwhewhewhehwehwehwe