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];
}
Advertisements

6 Responses to Google Code Jam Round 1B

  1. Timotius Sakti says:

    Yang problem C, bisa diselesaikan dengan cara curang juga :D.
    Bruteforce testcase easy (2^25), setelah itu buka situs integer sequence :D.
    Masukkan 5-6 deret bilangan pertama, kita bisa dapatkan hasil berikut:
    http://www.research.att.com/~njas/sequences/?q=5%2C8%2C14%2C24%2C43&sort=0&fmt=0&language=english&go=Search

    :p

  2. Risan says:

    @Timo: Oo… Ternyata ini cara brute force yang tadi pagi lu bilang =)) *Two thumb* =))
    @pemilik blog: Nice write-up 😀 *Four thumb* =))

  3. Felix J says:

    yang soal A, untuk smua direktori yang ada, bisa dimasukin ke set dengan terlebih dahulu nambahin “/” di plg belakang tiap direktori. misal “/a/b/c” maka jadiin “/a/b/c/”, terus masukin ke set setiap ketemu ‘/’, Jadi buat “/a/b/c/” yang dimasukin ke set “/”, “/a/”, “/a/b/”, “/a/b/c/”. terus pas terima query, lakuin hal yang sama… tinggal cek di set ada / gak, kalo gak ada berarti kita harus create tuh directory + masukin tuh directory ke set kita :p

  4. Aku dah coba kerjain yang A caranya mirip kayak bikin trie, tapi keynya string. Jadi proses insert untuk yang udah ada awalnya dan yang baru sama persis, tapi untuk yang baru tiap kali ada anak yang baru hasilnya +1 =p

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: