Suhendry’s Blog

Lho!? koq bukan write-up tentang BNPC-HS 2007? hehehe, maap write-up BNPC-HS 2007 akan ditulis sehabis ini. Soalnya gw masih butuh beberapa resource (foto & data) untuk write-up nya

Di sini gw mau bahas sedikit tentang SRM 377 divisi-1 yang barusan gw ikutin di TopCoder Arena kemarin malam (mid-night 17-to-18 Nov 2007). SRM ini sialnya UNRATED (karena sempat ada database failure)!! arrghhh… sial banget! padahal udah lama gw ga SRM padahal lagi semangat-semangatnya padahal gw cuma butuh +1 buat balik ke kuning padahal gw udah perform bagus (444.40 points dan solve 2 problems). padahal felix udah kalah padahal udah rela-in gak tidur meskipun besoknya ada final BNPC-HS yah…. emang belum boleh kuning

Entah ada angin apa, cukup banyak coder yang mengikuti SRM 377. Kapasitas maksimum (1500 coder) juga tumben-tumbennya penuh, untungnya gw udah register duluan Coder indo di divisi-1 yang ikutan: ardiankp, felix_halim, simonsyd, ilham, wongiseng, suhendry (ugh.. biru), emka207, fir.

Jam 00:00AM teng! SRM mulai… tarik napas.. go!

Easy 250 - Squares Inside Lattice

Problem: SRM 377 - Squares Inside Lattice

Problem 250 mirip dengan problem BNPC-HS 2007 Qualification Problem B. Diberikan N titik (integer) di koordinat Cartesian, tentukan berapa banyak square yang bisa dibentuk. Bedanya, sekarang kita tidak diberikan N titik, melainkan suatu rectangle (width & height) dimana semua titik integer di dalam rectangle tersebut boleh digunakan. 1 <= width, height <= 10^5.

Corat-coret di kertas sebentar, dan ketemu solusinya Ternyata setiap square berukuran NxN memiliki N square unique dengan sisi sebesar N-Manhatan-Distance. Gambar di bawah ini menunjukan square yang memiliki Manhatan Distance sebesar 5 untuk setiap sisinya.

Kalau begitu, tinggal dibruteforce aja untuk semua N Manhatan Distance.

FOR(size,1,min(height,width)) {
    LL w = width - size + 1;
    LL h = height - size + 1;
    res += w * h * size;
}

Submit! 190.23 points.. hm, not bad

Medium 500 - Game on A Graph

Problem: SRM 377 - Game on A Graph

Untung minggu kemarin habis belajar tentang manfaatin matrix multiplication bareng si kurniady, jadi pas baca ini soal pikiran gw langsung connect dengan ide solusinya

Construct matrix W (n x n), sedemikian sehingga input vector P jika dimultiply dengan matrix W akan menghasilkan vector P’ yang merupakan hasil operasi pada graph saat node white diupdate. Construct juga matrix B (n x n) untuk operasi update node black.

Perhitungan solusinya menjadi (sekalian testing script LaTeX):

Operasi pangkat bisa diselesaikan dalam O(log(T)).

VVI W(n,n), B(n,n), I(n,n), P(1,n);
REP(j,n) REP(i,n) {
    W[i][j] = (colors[j] == 'W') ? (i==j) : adj[j][i] - '0';
    B[i][j] = (colors[j] == 'B') ? (i==j) : adj[j][i] - '0';
    I[i][j] = (i==j);    // matrix identitas
}
REP(i,n) P[0][i] = marks[i] - '0';
VVI M = (N/2 == 0) ? I : power(mul(W,B),N/2);
VVI ans = mul(P,M);
if ( N % 2 == 1 ) ans = mul(ans,W);

Dapat 254.17 points dari soal ini, lumayan

Hard 950 - Alien Language

Problem: SRM 377 - Alien Language

Ok, yang ini ribet dan gw belum kepikiran solusinya. Kalau ada yang udah bisa, jelasin ke gw yah

The Result

Hasilnya, gw berhasil dapat 444.40 points dan berada di rank 89. Untuk pertama kalinya (emang belum sering SRM sih) gw masuk top-100 di divisi-1 dalam SRM

Dan ini rank felix……

Yay!! gw menang dari felix

Dan setelah gw cek… ternyata gw rank-3 di room ^_^ (sayangnya unrated dan bukan SRM berhadiah)