OSN 2010

Akhirnya, Olimpiade Sains Nasional 2010 dimulai besok! Kalau tiga tahun lalu saya datang sebagai peserta, tahun ini saya ikut di kontingen OSN sebagai fasilitator / pelatih tim Informatika DKI Jakarta. Kalau koneksi internet memungkinkan, saya akan blogging daily di post ini tentang day-to-day OSN tahun ini, khususnya tentang OSN Informatika, dan mungkin akan livetweet (follow @angelinavj) juga.

Downloads :
Daftar Gold Medalist + Nilai
Daftar Silver Medalist + Nilai
Daftar Bronze Medalist + Nilai
Daftar Perolehan Medali per provinsi

===watch this space for updates===

Pelatihan Pra-OSN (DKI)

08/01 > Arrival

08/02 > Opening Ceremony, Practice Contest

08/03 > Contest Day 1

08/04 > Contest Day 2

08/05 > Excursion

08/06 > Medal Awarding

Afterthought

Advertisements

Google Code Jam Round 1B

Tadi pagi, gw berpartisipasi di Round 1B Google Code Jam, kompetisi algoritma internasional tahunan dari Google. Kualifikasi pertama sudah dilakukan dua minggu yang lalu, diikuti oleh 106 coder dari Indonesia (menurut website ini). Dari 22 coder Indonesia di Round 1B, 7 orang menyelesaikan round ini dengan full score, termasuk gw. Meski begitu, agak kecewa juga sih dgn bug-bug yg mewarnai kode gw sepanjang contest ini. waktunya jadi rada2 lama hiks.

Soal-soal GCJ menurut gw menarik, bahkan juga bagi yang masih relatif pemula dalam programming, jadi berikut gw coba bahas step-to-stepnya. mudah2an berguna 😉

tolong feedback ya kalau ada salah-salah atau ada solusi lain yang lebih baik 🙂

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

Problemset

Problem A : File Fix-It

Soal ‘implementasi’, karena cukup straight-forward dari soalnya. Soal ini bisa diselesaikan dengan penggunaan struktur data tree. Untuk setiap baris query, lakukan parsing, atau pisah-pisahkan nama direktori yang dibatasi oleh tanda slash. Parsing bisa dilakukan seperti ini :

nAr = 0;
for (int j = 0; j < s.length(); j++){
            if (s[j] == '/'){
               nAr++; ar[nAr] = "";
            } else{
              ar[nAr] += s[j];
            }
}
Keterangan : nAr adalah jumlah direktori dalam baris itu.

Setelah itu, untuk setiap baris query yang sudah di-parse, lakukan proses penelusuran tree dari root.

/*
Keterangan:
1) setiap direktori di-mapping-kan ke sebuah angka 'pengenal'.
2) anak-anak dari node di mappingkan di vector child[node].
3) dire[node] berisi nama direktori dari angka pengenal = node.
*/
void visit (int node, int now){
     if (now > nAr){
        return; //proses selesai
     } else{
       bool tr = false; //ar[now] belum menjadi ‘anak’ dari node.
       for (int i = 0; i < child[node].size(); i++){
           if ((dire[child[node][i]]) == ar[now]){
              visit(child[node][i],now+1); //telusuri kedalaman berikutnya.
              tr = true;
           }
       }
       if (!tr){ //bila direktori belum tersedia, maka harus dibuat
          num++;  //operasi 1, s[now] di-assign ke node nomer num.
          child[node].push_back(num); //operasi 2
          dire[num] = ar[now]; //operasi 3
          visit(num,now+1);
       }
     }
}

jadi, setiap selesai parsing kita memanggil procedure visit dengan visit(0,1), karena root dari tree ini bernomor 0.

ingat bahwa variabel num berisi jumlah node baru yang dibuat. Bila x = num saat n query pertama dibaca, dan y = num saat m query kedua dibaca, maka hasil akhir yang diminta adalah y-x.

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

cara kedua (oleh Brian Marshal)

dengan menggunakan string-matching sederhana juga bisa, mengecek sampai / ke berapa query bisa disamakan dengan data yang sudah ada sebelumnya.

misalnya, yang sudah ada : /a/b/c, yang mau ditambahkan : /a/b/d, maka dengan string-matching kita dapat menyamakan /a/b/, dari sini kita tahu bahwa tinggal satu direktori d yang tidak bisa disamakan. Maka jumlah mkdir yang dibutuhkan : 1.

Problem B : Picking Up Chicks

soal dengan karakteristik Greedy. Beberapa analisa yang bisa membantu :

  • waktu tercepat sebuah bebek i dapat mencapai barn adalah (barn-x[i]) / v[i]. bila nilai ini kurang dari T, maka bebek ini dapat mencapai barn sebelum waktu T sesuai deskripsi soal.
  • maka, K bebek bisa mencapai barn dalam waktu T bila jumlah bebek yang memenuhi poin 1) lebih dari atau sama dengan K.
  • Supaya bisa bergerak secepat di poin 1), si bebek harus melewati / di-swap dengan bebek-bebek di kanannya yang tidak dapat untuk mencapai barn (seperti ditentukan di poin 1). Perhatikan bahwa ini dapat diartikan : untuk membuat bebek i mencapai barn dalam waktu tercepat, swap harus dilakukan untuk bebek j di mana x[j] > x[i] dan v[j] < v[i] dan used[j] = false (bebek j tidak dapat mencapai barn)
  • untuk meminimalkan swap, maka bebek yang dipilih untuk mencapai barn harus yang paling kanan yang mungkin.
/* nmin = k. r = jumlah bebek yang memenuhi.res = jumlah swap*/
     int r = 0;
     int res =  0;
     for (int i = nducks; i >= 1; i--){
         if ((barn-x[i]) <= v[i]*ntime){
            r++;
            for (int j = i+1; j <= nducks; j++){
                if (used[j]) continue;
                if (v[j] < v[i]) {
                       res++;
               }
            }
            used[i] = true;
          }
          if (r >= nmin) break;
     }
     if (r >= nmin)printf("Case #%d: %d\n",ti,res);
     else printf("Case #%d: IMPOSSIBLE\n",ti);

constraint yang kecil memungkinkan O(n^2) straight forward seperti di atas, namun dengan perubahan yang minim bisa menjadi O(n).

Problem C : Your Rank is Pure

Problem yang diselesaikan dengan rekursif dan kombinatorik dasar. dynamic programming diperlukan untuk menyelesaikan testcase yang large.

Persoalan ini dapat dimodelkan dengan rekursif berikut:

f (pos,bil) = sum of { f(j,pos) * kombinasi }

di mana

  • 1 <= j < pos, dan kombinasi = nCk (bil-pos-1,pos-j-1).
  • pos : posisi bilangan bil.

hasil bisa diperoleh dari sum of { f (i,n) } di mana 1 <= i < n.

dasar pemikirannya kira-kira adalah kita menelusuri proses dari angka pivot n ke bilangan berikutnya yang direfer oleh posisi angka n tersebut, dan seterusnya. bila ada ‘tempat kosong’ yang tidak dikunjungi (yaitu bila pos dan j tidak bersebelahan), kita dapat ‘mengacak’ bilangan-bilangan yang tersedia (yaitu bilangan di antara pos dan bil) untuk menempati tempat kosong ini. kemungkinan pengacakan ini = nCk (bil-pos-1,pos-j-1).

untuk menyelesaikan large testcasenya, tambahkan memo untuk dynamic programming.

LL  process (int pos, int bil){
 if (pos == 1) {
    return 1;
 }
 if (dp[pos][bil] != -1) return dp[pos][bil];
 dp[pos][bil] = 0;
 for (int j = 1; j < pos; j++){
     if (pos-j > bil-pos) continue;
     int tempat = pos-j-1;
     int bilangan = bil-pos-1;
     if (bilangan >= tempat){
       dp[pos][bil] += (comb[bilangan][tempat] * process(j, pos))%MOD;
     }
     dp[pos][bil] %= MOD;
 }
 return dp[pos][bil];
}

Katalog Programming Page

Programming page ini ditulis sejak bulan Januari, terinspirasi dari page teman saya dari Olimpiade bidang Kebumian. Di page tersebut, termuat tutorial, soal-soal teori dan praktek, serta solusi dari beberapa problemset yang ada. Mudah2an bisa membantu teman2 yang mau belajar, karena selama ini ‘kan soal-soal lomba komputer SMA di Indonesia masih terpencar-pencar dan sulit dicari 🙂

Kenapa pake buat katalog ginian segala? kata temen SEO buat keywords di page kurang oke 😛

Bila ada yang ingin menyumbangkan soal-soal dari pelatihan pra-OSN di SMA, kotamadya atau provinsinya, bisa email saya di lennie_2nd@yahoo.com.

Soal Teori

Olimpiade Sains:

  • Nasional (OSN) Komputer 2006,2007,2008, 2009
  • Provinsi (OSP) Komputer 2006, 2007, 2008, 2009
  • Kotamadya / Kabupaten (OSK) Komputer 2006, 2007, 2008, 2009, 2010

Lomba Swasta:

  • Jogja Informatics Technology Session (JOINTS) UGM 2007, 2008, 2009, 2010
  • Informatics Logical Programming Competition (ILPC) Ubaya 2009, 2010
  • Compfest UI 2010
  • Bina Nusantara Programming Competition for High School 2007

Pelatihan Pra-OSN:

  • Riau
  • DKI Jakarta.

Kunci / Solusi / Penyelesaian :

  • OSK 2006
  • OSK 2008
  • OSK 2010
  • OSP 2007
  • JOINTS 2010

Soal Praktek / Programming

Olimpiade Sains Nasional (OSN) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009

Lomba Swasta:

  • Computer Competition @ Gonzaga 2007
  • Lomba Komputer Nasional Computerkid/Computer Star SMP 2007.
  • Lomba Komputer SMA Kanisius 2007 (penyisihan dan final)
  • IPEKA Computer Competition 2007, 2009
  • IBII Code Challenge 2007
  • Kompetisi Pemrograman (KP) Unpar 2007, 2008, 2009, 2010
  • Jogja Informatics Technology Session (JOINTS) UGM 2008, 2009, 2010
  • Bina Nusantara Programming Contest for High School (BNPCHS) 2006, 2007, 2008, 2009
  • COMPFEST UI 2010
  • PROLOG UPH

Pelatihan Pra-OSN :

  • Riau
  • DKI Jakarta
  • SMAK 1 Jakarta
  • SMAK Gading Serpong Banten

* Katalog tanggal 30/4/2010, bila ada file baru yang diupdate, page ini tidak diupdate. silakan langsung lihat programming page-nya.

* Ini page untuk pemula pra-OSN, jadi tidak ada soal level Internasional atau Pelatnas.

Terima kasih kepada donator2 soal :

Ellensi Rey Chandra, Muhammad Adinata, Janson Hendryli, Brian Lie, Daniel Julius, Harta Wijaya, Felik Junvianto, Daniel Rolandi, Suhendry Effendy, Agung Utama.

Final JOINTS 2010

Jogja Information Technology Session (JOINTS) – Programming Competition Session (PCS), Universitas Gajah Mada, 11 April 2010

problemset dan solusi sudah diupload.

detailed scoreboard [thanks Vilberto]

EDIT : Pembahasan Soal D.

Soal E, Bilangan

ada dua kemungkinan :

  • bila angka terurut menurun, maka angka 0 harus ditambahkan (tambah digit). urutkan menaik, lalu sisipkan angka 0 di posisi kedua paling depan.
  • bila angka tidak terurut menurun, cari pasangan i, j paling kanan di mana i <= j dan digit[j] < digit[i]. tukarkan. //setelah contest nyadar, mestinya bisa di next_permutation aja sih di C++.

ini soal termudah di contest kali ini – setelah submit sekali, ngga nemu perubahan yang perlu sampe akhir contest. tapi ironisnya nilai saya 0, compile error katanya 😛 nilai saya : 0 (CE)

Soal C, Kayu

lihat Huffman Coding. ga pake mikir langsung koding :p pas debug beberapa jam kemudian, nyadar kalo ada bug kecil yang bs ngancurin seluruh kode. nilai saya : 100

Soal A, Lemari

menggunakan dynamic programming tiga dimensi yang cukup straight-forward, dengan state [depth – tinggi laci yang mau diselesaikan, dari atas] [ jumlah laci yang yang terkunci ] [ boolean, apakah laci tepat di atas yang sekarang terkunci atau tidak ]

fungsi rekursinya :

bila (last = true) atau (depth = teratas), dp[depth][safe][last] = dp[depth+1][safe+1][true]+dp[depth+1][safe][false];

else, dp[depth][safe][last] = dp[depth+1][safe][true]+dp[depth+1][safe][false];

ada tiga versi kode ini yang gw submit. versi pertama pure rekursif dan DP, versi kedua pruning / optimasi rekursif, versi ketiga ganti printf jadi cout, karena output long long di printf rada bahaya kalo ga tau jelas compiler jurinya.

nilai saya : 100

Soal B : Pesan

pikiran naluriah yang pertama adalah bikin algo Longest Common Subsequence diulang berkali2. tapi cepet ketemu counter casenya.  solusinya sih… hajar rekursif, kasih tabel DP =)) kalo kata Riza, namanya multiple dimension LCS. baru tau juga.

intinya, tabel DPnya punya empat dimensi [posisi string 0][posisi string 1][posisi string 2][posisi string 3], dengan nilai string hasil. untuk setiap state, ada 2 kemungkinan:

  • s[0][pos0] termasuk di dalam string hasil. maka kita harus mencari dp[pos0+1][p1+1][p2+1][p3+1]. p1, p2, p3 adalah indeks occurence pertama yang <= posisi string 1/2/3 di mana karakternya sama dengan s[0][pos0]. hasil : s[0][pos0]+dp[pos0+1][p1+1][p2+1][p3+1].
  • s[0][pos0] tidak ada dalam string hasil, maka kita harus pencari dp[pos0+1][pos1][pos2][pos3].

bandingkan kedua hasil, yang mana yang lebih baik, masukkan ke dalam dp[pos0][pos1][pos2][pos3]. hasil ada di dp[0][0][0][0].

ada 4 versi yang gw buat:

  1. rekursif dengan inner rekursif berdepth 3.
  2. coba pruning dikit.
  3. nyadar kalo ngga perlu ada inner rekursif, rewrite.
  4. ada kurang inisialisasi di rekursif, bisa membuat salah untuk hasil panjang pesan < 2.

nilai saya : 100.

Soal D : Pesta

soal yang gw nggak solve, ga bs ketemu kompleksitas yang lebih bagus. cuma bisa ngurangin dari n^3 jadi n^2 log n (kayaknya sih, ga gt bisa ngitung kompleksitas priority queue). bingung juga jelasinnya, silakan liat kodenya di halaman Solusi 😛 gw sempet nyoba worst casenya di contest time dan ud keliatan bgt ga bkl lewat.

nilai saya : 40 (ternyata masih paling tinggi di soal ini :P)

EDIT : ini soal Google Code Jam 2008. Pembahasan bisa dilihat di sini. thanks Ashar for the input!

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

total 340 dari 500. agak kecewa dengan soal Enya sih.rank 2 dari SMAK 1 Penabur Bandung, 270, rank 3 dari Ipeka International, 220 kalo ga salah.

personal background:

tadinya bener2 ga berencana buat ikut JOINTS, tapi ternyata tanggalnya persis banget sama kondangan sodara sehari sebelumnya. lol emg harus ke Jogja, jadi ya sekalian 😛

general comments gw buat problemset JOINTS:

  • buat gw problemsetnya menarik dan cukup menantang, significantly lebih sulit dari soal JOINTS 2 tahun lalu, tapi juga nggak sulit-dan-tidak-menarik kayak UnPar.
  • sayangnya, soal termudah di contest ini (soal E) nggak cukup gratisan, akibatnya hampir setengah peserta dapet nilai 0 (dengan bodohnya saya compile error di soal ini lol).
  • secara persebaran juga perlu dibenahi, karena tadi ada 2 soal DP, 1 greedy, 1 ad hoc, dan 1 yang gw ngga perfectly solve. graph nggak ada :(( *gw rada bias sih :P*
  • ngga make algo yang aneh2, yang nearly mustahil untuk dipikir sendiri, kayak Strongly Connected Component di Unpar.
  • semua soal terbuka untuk mengemis nilai parsial.
  • menarik, tiga national contests yang besar (JOINTS, BNPCHS-Binus, Unpar) tingkat kesulitan soalnya naik cukup jauh dari tahun 2008. ini kerasa banget terutama untuk JOINTS dan UnPar, karena gw skip ngga ikut tahun 2009nya.

all in all, ini last contest gw sebagai siswi SMAK 1 Jakarta, akhir dari perjalanan competitive programming gw selama beberapa tahun ke belakang. gw senang dan bangga karena bisa menutup bagian hidup gw yang ini dengan catatan yang patut gw banggakan 🙂

A March Weekend

20-21 March:

I’m totally screwed at TCHS* Championship Round. I misconverted time (late by one hour) because I  stupidly didn’t pay attention to the change in conversion caused by Daylight Saving Time. so as soon as I got home that night, I registered at the Arena and left my PC to watch three episodes of The Mentalist. I finished watching at about 11:20 pm and turned on my PC to chat…

offline message from ptrrsn_1: “lu ketiduran?” (“did you oversleep?“)

lennie_2nd : “masi ada stengah jem mulainya, kali =D” (“there’s more than 30 mins left!”)

then I opened Arena, quite lazily….. GOOSSSHH it has started!!! More than half competitors had submitted their 250 pt. Paniccccc!!! blahhh and I don’t know what was I thinking when I wrote that sloppy, long-winded code. I tested the code against the worst testcase and realized that it was over time limit, yet amidst the adrenaline rush I submitted it anyway (I know, that’s super stupid).  I missed submitting 600 pt by a minute, although I’m not 100% sure it’ll pass systest as I didn’t have enough time testing. The challenge phase was disastrous (I am really bad at challenging, duh) and I ended up with my first minus score in TopCoder so far. and this happened in the annual championship. gaaahh.

that night I submitted the 250pt in practice room, chatted w/ some US-based pals, and watched Mentalist again – then slept at 5 am. Woke up at ten with headache and stomachache. I did JOINTS** Preliminary (theoretical test) at 2pm, wondering throughout why this supposedly-programming test turned out to be more than 80% math. As I finished, I didnt have the strength to think abt anything.

lesson : seriously need to learn to handle my nerves. I sure can do better than a minus…. and dont challenge if i’m not quite sure. lose 50 pts in TCHS and 25 pts in the last SRM =(

Other news :

  • coming back to yellow rating at TopCoder! when will I be red?
  • got a very surprising acceptance from a university in a state I have difficulty to spell correctly. I’ll write more abt that (and other university-related things)  early next month, I hope.
  • super busy these days with self-learning APs and preparing for A Level, but on the other side facebook activity somehow escalates, too =)
  • invited to another Hermawan Kartajaya‘s event, Indonesia Youth Marketing Subculture Forum, as a continuation from my participation in the Time Cube a month ago. very excited!
  • decided not to compete for a place, hence not participate in, the IOI team this year. prolly I will to APIO, but let’s see later…
  • so many decisions to make! I hope I made the right ones 🙂

* TCHS stands for TopCoder High School, an international online tournament for High School students. 3 selection rounds before qualifying 100 finalists for Championship Round.

* JOINTS stands for Jogja Information Technology Session, annual and national programming contest held by Universitas Gajah Mada.

Final KP UnPar 2010

Update : Soal Final [RAR]

Practice Contest

2 soal :

  1. keluarin bilangan fibonacci di antara a dan b
  2. dikasi 2 sequence bilangan, temukan letak pertama sequence A ada dalam sequence B

pas lg ngerjain soal 2, bengong jg liat constraintnya. bisa ada sejuta testcase, tiap sequence bisa ada sejuta bilangan. lah, ini kan baca input doang ud ga muat time limitnya? yaud gw jd koding versi ngasal brute forcenya (total sejuta ^ 3 kalo ada sejuta testcase), ternyata AC (constraintnya ngaco berarti). sisa waktu pake buat iseng2 ngoding Knuth-Morris Pratt, pake array sejuta. eh, ga bisa :)) aneh, padahal itu kan masih jauh < 16 MB? setelah ditanya, kata panitianya, “memory limitnya 1 MB“. gw bengong =))

setelah practice contest selese, gw menyimpulkan ‘ga usa peduliin constraintnya, hajar aja, wong sejuta ^3 aja muat’ =))’

click more untuk write-up soal final…

Read more of this post

Semifinal KP UnPar 2010

Overall idem dengan Penyisihan – tapi kali ini gw nunggu perbaikan beberapa soal sebelum kirim, dan sialnya ada 2 ato 3 soal gitu yang ga sengaja kekirim solusi yg sama 2 kali. >< anyway, akhirnya solve semua sih. kali ini soalnya lebih mending daripada penyisihan, uda mulai ada algo graph walau cuma BFS-DFS, dan ada soal data struktur sederhana.

Problemset bisa diunduh di page programming, solusi saya di page solusi. write-up untuk masing2 problem, click more.
Read more of this post