A little about Google Code Jam... this is a world competition of making computer programs, firstly it's online, but later the 100 people on the top will compete in Google's place in the US with accomodation and flight ticket bought by Google. Wow, how nice! Firstly is the qualification round, it was joined by about 3000 competitors (anyone can join), and 500 from them will pass. And the 3000 competitors is divided into 5 groups that will do different problems. So each group will have top 100 that will proceed to the next round (that is Round 1). And that time I passed the qualification round, on which I got the which position, can you guess? The answer is... last! In other words I got the 100th position of 100.

Sekilas tentang Google Code Jam... ini lomba bikin program untuk seluruh dunia, pertama2 secara online, tapi nanti 100 orang teratas akan bertanding di markas Google di Amerika dengan hotel dan tiket pesawat gratis! Betapa enaknya. Pertama2 babak penyisihan dulu, diikuti sekitar 3000 lebih peserta (siapapun boleh ikut), 500 di antaranya lolos. Dan 3000 lebih peserta itu dibagi 5 kelompok dengan soal yang berbeda. Jadi tiap kelompok 100 orang teratas lolos ke babak berikutnya (yaitu babak 1). Dan waktu itu ku uda lolos babak penyisihan... dengan peringkat, hayo berapa, teman2? Jawabannya terakhir! Alias peringkat 100 dari 100 hehehe.

Today, I woke up at 4.20 am, even though I had just slept for one hour, because I felt something terrifying. Then.. I slept again. After that I felt that the air is very hot, and I felt that it was already afternoon, so I needed to wake up. But when I woke up, actually it was just 7.50 am, even though I set the yelling alarm at 8.00am. I slept again, even though only 10 minutes left. But eventually at 815 I really woke up, and this is the terrifying thing that I will face. It's the Round 1 of the Google Code Jam 2005 by TopCoder.

Sekilas tentang Google Code Jam... ini lomba bikin program untuk seluruh dunia, pertama2 secara online, tapi nanti 100 orang teratas akan bertanding di markas Google di Amerika dengan hotel dan tiket pesawat gratis! Betapa enaknya. Pertama2 babak penyisihan dulu, diikuti sekitar 3000 lebih peserta (siapapun boleh ikut), 500 di antaranya lolos. Dan 3000 lebih peserta itu dibagi 5 kelompok dengan soal yang berbeda. Jadi tiap kelompok 100 orang teratas lolos ke babak berikutnya (yaitu babak 1). Dan waktu itu ku uda lolos babak penyisihan... dengan peringkat, hayo berapa, teman2? Jawabannya terakhir! Alias peringkat 100 dari 100 hehehe.

A little about Google Code Jam... this is a world competition of making computer programs, firstly it's online, but later the 100 people on the top will compete in Google's place in the US with accomodation and flight ticket bought by Google. Wow, how nice! Firstly is the qualification round, it was joined by about 3000 competitors (anyone can join), and 500 from them will pass. And the 3000 competitors is divided into 5 groups that will do different problems. So each group will have top 100 that will proceed to the next round (that is Round 1). And that time I passed the qualification round, on which I got the which position, can you guess? The answer is... last! In other words I got the 100th position of 100.

Jadi kontes hari ini yaitu seleksi lagi, akan diambil 250 dari 500 peserta, semua peserta waktunya sama dan soalnya sama. Mulai jam 9 pagi, harus daftar ulang sebelum jam 855. Ada 3 soal, dengan nilai maksimum 250, 500, dan 1000, sesuai tingkat kesulitan soal.

So the contest today is a selection. 250 out of 500 contestant will move to the next round. All contestants compete at the same time with same problems. Starting at 9 am, need to re-register at 8.55 am. There are 3 problems, with maximum points of 250, 500 and 1000, according to the difficulty of the problem.

Soal pertama dengan nilai maksimum 250: Seperti biasanya, soal pertama gampang, jadi lebih ke adu cepat ngetik. Cuma suru tempatin titik2 dan buang bagian pinggir yang gada titiknya (kalo ga ngerti lewat). Semua lancar.. tapi pas klik tombol Test ada array out of bound?! Kodenya:

The first problem with maximum mark 250: As usual, the first problem is easy, so it's just like typing competition. I was only asked to place some dots and discard the borders that have no dots (if you don't understand, never mind). All seems ok, but when I clicked the Test button, array out of bound error happens?! The code:

for (int i=minr; i<=maxr; i++) {
    hs[i-minr] = "";
    for (int j=minc; j<=maxc; i++) {
        hs[i-minr] += jadi[i][j]==1?'X':'.';
    }
}

Apa salahnya kira2? Untunglah salahnya udah ketauan sebelom pencet tombol Submit, jadi ga rugi. (Kalo salahnya ketauan setelah pencet Submit, untuk submit ulang ada penalti). Tentu saja salahnya ada di... for yang ke 2, seharusnya j++, bukan i++. Salah ketik yang menyedihkan.

Guess where is the mistake? Fortunately the mistake was found before I pressed the Submit button, so I didn't lose. (If the mistake was found after pressing Submit, to re-submit it gets a penalty). Of course the mistake is on the... second for, that should be j++, not i++. A sad typo.

Soal pertama beres, soal kedua bernilai 500 dibuka. Baca soalnya... walau kalimatnya agak membingungkan, tapi keliatannya ko gampang sekali? Apa ga salah? Ada jebakankah?

After the first problem is done, I opened the second problem worth 500. I read the problem... but even the sentences a bit confusing, it looks very easy? Maybe something wrong? Is there any trap?

Character j in element i (both 0-based) of friendships says whether person j and person i know each other ('Y' for yes, 'N' for no). This relationship is symmetric. You want to start a club where every member knows at least k other people in the club. Needless to say, you want the club to contain as many people as possible. Return a int[], in strictly ascending order, containing the numbers of all people in your club.

Sepertinya gada jebakan, dan kulihat2 di contohnya keliatannya normal2 aja, jadi kubuat dengan cepat dan langsung submit (dapet 463.76). Tiba2 seseorang mengingatkan ku, bahwa ternyata memang ada jebakan di sana, yaitu kalau seseorang tak punya teman cukup di sana maka ia tak akan masuk klub itu dan orang lain yang akan masuk klub itu dan berteman dengannya tidak akan dianggap mempunyai teman dia jadi bisa saja orang lain itu tidak akan masuk klub itu. (Pusing ga? Kalo iya, lewat). Jadi terpaksa diedit.. dan submit lagi dengan penalti 10% dan waktu yang telah cukup lama berjalan, jadi cuma dapet 279.74 dari 500 poin.

Looks there was no traps, and when I looked at the examples it seemed normal, so I did the problem quickly and submitted it (463.76 points). Suddenly somebody warned me, saying that there was indeed a trap, which is if somebody don't have enough friends there he will not enter that club and other person that will enter the club and is a friend with him will not be considered to have he as a friend so it's possible that that other person will not enter the club. (Are you with me? If not, just ignore). So there was no way but to edit... and submit it again with penalty 10% and the time has passed quite a long time, so I got only 279.74 of 500 points.

Soal ke 3 terlalu susah bagiku, setelah pikir2 pun ga ketemu ide, jadi kubiarkan kosong saja. Akhirnya waktu lomba habis, kulihat peringkat keseluruhan, aku berada di posisi 264 dari 500. Sekarang tinggal nunggu System Test, maksudnya semua program yang disubmit semua orang akan dites pake macem2 input, dan kalo ada salah satu saja yang salah, nilai untuk soal itu langsung 0. Walau belum masuk 250 besar, tapi aku uda seneng, pasti di atasku banyak yang gagal System Test (seperti biasa), jadi satu-satunya kemungkinan ku ga lolos kalo ku sendiri ga lulus System Test. Nah, saat ini semua kode orang lain uda bisa dibuka, jadi bisa ngintip kode orang2, dan orang2 juga kerjain soal ke 2 dengan cara yang sama dengan ku.

The third problem was too hard for me, after some thinking I got no idea, so I left it blank. Finally the competition time was over, I saw the overall ranking, I was on 264th position out of 500. Now is the time to wait the System Test, it means that all programs that is submitted by all competitors will be tested using variety of inputs, and if only one of them produces wrong result, the mark for that particular problem will become 0. Even though I had not become top 250, I felt happy, I think there must be a lot of people above me fail the System Test (as usual), so the only possibility I didn't pass was only if I myself didn't pass the System Test. BTW, now all other contestant's code can be viewed, so I could peek into it, and people also did the second problem using the same strategy as me.

System Test mulai juga setelah nunggu sejam katanya ada gangguan sih. Sesuai dugaan, banyak orang gugur di atas ku, dan peringkatku menaik jadi 239.. lalu 236, gembiraaa... tiba2 jadi 306?!?! Ternyata aku gagal System Test di soal ke 2 yang berarti nilai soal ke 2 ku jadi 0 :( Mengapa demikian??? Coba liat kode di bawah ini dan kira2 sendiri mengapa bisa begitu (pasti Anda tau)... Hik, betapa sedihnya...

After waiting for an hour because it was said there was some technical problem, finally the System Test began. As expected, a lot of competitors failed the System Test and moved to positions below me. And my rank was increasing, to 239.. then 236.. Oh I was so happy... suddenly my rank became 306?!?! I failed the System Test of the second problem which means that my points for the second problem became 0 :( How could it be like that??? Try to see the code below and guess by yourself how could it happen (you can!)... How sad was I...

public int[] getMax(String[] friendships, int k) {
    int n = ...
    int ff[][] = ...
    ...    
    
    for (int ulang=0; ulang<50; ulang++) {
        for (int i=0; i<friendships.length; i++) {
            int cnt = 0;
            for (int j=0; j<n; j++) {
                if (ff[i][j] == 1) {
                    cnt++;
                }
            }
            if(cnt < k) {
                 for (int ii=0; i<n; i++) {
                    ff[ii][i] = 0;
                    ff[i][ii] = 0;
                 }
            }
        }
    }
    ...    
}

Tau?

Can?