Senin, 05 November 2018

Penyisihan Gemastik Pemrograman 2018

Beberapa minggu yang lalu aku ikut 2 cabang Gemastik, Pemrograman sama Keamanan Jaringan. CP sama CTF. Aku ikut karena biasanya fun dan lumayan objektif. Cuma tahun ini gak terlalu begitu rasanya. Aku bakal bahas yang pemrograman aja, secara aku ngerasa aku gak terlalu dalam di perkara CTF (tapi screencast 5 jam menurutku nggak jelas).

Oiya, aku gak lolos cabang apapun di Gemastik, jadinya nggak pergi ke Surabaya. Oke, fokus ke cabang pemrograman deh. I tried not to be angry, but I can't. Beberapa rant terkait penyisihan kemarin:

1. Server down

Server down 5 menit, 10 menit masih okelah. Ini sampai 2 jam down. Terus down-nya itu gak semuanya, kayak ada beberapa session yang bisa ngakses. Misal di timku, Anab bisa buka, sekalipun kacau banget. Aku sama Rakha selalu kena gateway time out. Jadinya ya nggak fair lah lombanya, gak semua bisa buka, dan sekalipun bisa buka juga lambat banget. Pemberitahuan dari panitia juga rada lambat, kalo menurutku. E-mail yang masuk (dan baru kubaca setelah lombanya selesai) kira-kira masuk 1 jam setelah kontes. Tidak membantu.

Masalah ginian emang jarang keprediksi sih. Aku juga masih gak tahu mitigasi yang baik itu kayak gimana. Ada baiknya kalo bikin semacam chat group atau apalah yang mempermudah komunikasi 2 arah panitia sama peserta, supaya kalo ada masalah ginian infonya bisa lebih cepat. Panitia juga ada baiknya "nutup" kontesnya dulu, biar lebih fair. Cuma kalo servernya down ya gabisa kan mau nutup. Tapi kalo misalnya bisa, kayaknya lebih baik.

Yaudah, solusi terbaiknya, semoga tahun depan udah ada server yang lebih bagus aja. Kayak gini udah kejadian di INC 2017, dan pada tahun ini udah gak down lagi, padahal kontestannya jauh lebih banyak. Intinya, jangan jatuh ke lubang yang sama.

2. Ganti aturan

IMHO, kalau servernya masalah dan sering kena internal error, paling bener itu nge-spam submission sampe keluar verdict non internal error. Gambling sih, soalnya bisa numpuk WA dan lain-lain. Cuma aku rasa setelah pro dan cons-nya, tetep mending spam aja.

Secara ajaib, habis penyisihan selesai, dapet e-mail dari panitia yang menyatakan aturannya diganti, penalty jadinya banyak attempt. Luar biasa. Aku gak tau itu sebenarnya diumumin atau nggak,  kalopun diumumin setelah servernya stabil juga rasanya udah rada telat.

Selain itu, jumlah finalis juga berubah. Sebelumnya 10, ini jadi 12. Habis ini tiap kali aku bikin lomba kutulis aja finalisnya 10, baru nanti ganti basisnya sesuai keperluan. Easy.

Anyway, kalo menurutku jangan ganti aturan secara mendadak gini atau pas lombanya sudah selesai. Nggak fair. Ngubah jumlah finalis itu juga sebenernya gak terlalu bijak. Mungkin sekarang jumlahnya tambah banyak bikin seneng, cuma itu berarti gak nutup kemungkinan kalo tahun depan jumlahnya bisa dikurangi (secara kita juga nggak tahu ini kenapa mendadak ditambah). Aku curiganya ini karena penalty-nya diganti, jadinya ada yang seri terus dilolosin, but who knows.

3. Soal

Wah, ada soal kombin keren. Kok susah ya. Coba generate solusi untuk N kecil, terus cari di google. Wih, ada di OEIS. Ada formulanya juga. Soalnya bagus banget buat penyisihan yang online dan bisa googling. Nyoba nurunin rumusnya itu nggak mudah lho buat soal itu.

Kalo mau ngambil top 5 scoreboard, menurutku set soal kemarin tidak terlalu membedakan. Kayak, 4 soal pertama itu untuk top 10-15 juga masih mudah. Sisanya tinggal ngerjain easy soal ke-5, atau solve hard-nya. Kalo gak solve hard-nya, jadinya cuma cepet-cepetan solve easy. In any case, penyisihan kemarin lebih banyak cepat-cepatannya. Karena aturannya diganti, jadinya sih bukan cepet-cepetan, ganti jadi akurat-akuratan.

Aku gak tau sih scoreboardnya setelah unfrozen gimana, mungkin aja top-5 itu emang AC semua soal. Cuma itu gak terlalu bikin problemset yang bagus juga. Lolos harus AC semua. Kalo bisa tahun depan ditingkatin juga kesulitannya, misal kayak Gemastik 2016-2017. Itu paling nggak masih keliatan bedanya antara yang lolos sama nggak.

Bikin soal yang sesuai emang nggak mudah. Mungkin C4T juga gak berhasil ngumpulin soal-soal yang sesuai. Mungkin bisa juga kontak langsung orang-orang yang biasa bikin soal. Tahun depan mungkin aku juga boleh dikontak. Cuma ingat, jangan sampai orang-orang yang berpotensi kontribusi soal marah.


Mungkin poin-poin pentingnya itu.

Anyway, aku gak pernah semarah ini dalam ikut kontes CP di tahun ini. Mungkin ini yang paling buruk di tahun ini, entahlah. Aku sampe bikin ginian:


Jangan sampai tahun depan masih kejadian kayak gini. Kasihan juga soalnya, secara ini bagian dari rangkaian Gemastik yang lumayan prestisius, tapi di penyelenggaraannya bikin peserta kecewa.

Semoga tahun depan bisa lebih baik lagi. Maaf apabila beberapa bagian terlalu kasar. Apabila ada yang ingin disampaikan, bisa lewat komentar di bawah.

Note: aku gak komentarin final karena aku gak punya hak melakukan itu (gak ngerasain masa ngomentarin :P), lagian aku juga gatau apa yang terjadi di final.

Kamis, 01 November 2018

Yang Seperti DP Matrix

idk why but i feel like writing tonight

Kali ini mau bahas trik yang kayak DP matrix, tapi bukan.


Kasusnya rada khusus, biasanya main di ngitung banyak sekuens (gak selalu sih). Tapi secara kompleksitas lebih kenceng, plus ngodingnya lebih gampang. Trik ini sendiri aku gak sengaja nemunya pas ngerjain soal SPOJ yang bakal kubahas di sini. Nggak banyak yang solve, cuma mungkin ini karena emang nyari soal di SPOJ repot.

Prerequisite

Secara konsep teknik ini harusnya nggak terlalu sulit asal ngerti DP sama fast modular exponentiation (perpangkatan dalam $O(\log N)$. Kalo ngerti DP matrix (matrix exponentiation) bagus, cuma akan tiba saatnya hal itu harus dilupakan terlebih dahulu.

Ide Utama - The Toy Store

Untuk ngejelasin idenya, aku rasa mending langsung liat soal yang bikin aku dapet trik ini. Tautan menuju soal: SPOJ DCEPC14F - The Toy Store

Abstrak soal: Dikasih array $A$ ukuran $N$, terus 3 bilangan $M, K, X$. Cari banyaknya sekuens $S$ berukuran $K$, yang mana $1 \leq S[i] \leq N$ dan $ \sum_{i=1}^{K} A[S[i]] \equiv X \pmod{M}$.

Coba dipikir dulu ya, sebelum lanjut ke bawah.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

Oke, jadi kalo ngeliat soal ini mungkin kebayang modelin jadi graf. Misal $cnt[i]$ menyatakan banyak elemen di $A$ yang hasilnya dimodulo $M$ adalah $i$. Maka, kita bisa membuat graf dengan nomor 0 sampai $M-1$, yang mana terdapat $cnt[i]$ edge dari $y$ ke $(y + i) \mod M$ untuk tiap $0 \leq y \lt M$. 

Selanjutnya, pertanyaan tadi bisa diubah menjadi "ada berapa banyak jalan berbeda dari 0 ke $X$?" Tentunya, hal ini bisa didapat dengan matrix exponentiation. Buat adjacency matrix, lalu pangkatkan sebanyak $K$. Tinggal ambil entri $[0][X]$-nya.

Nah, masalahnya sampai kita bisa membajak time limit-nya jadi segede gaban, kita pasti bakal dapet TLE. Ada $T$  kasus uji, dan untuk tiap kasus uji kita butuh $O(M^3 \log K)$ operasi. Pas masukin kalkulator, pasti angkanya lumayan gede. Aku sendiri udah coba optimasi beberapa kali, TLE semua.

Optimization is fun, sampe akhirnya banting setir

Nah, bisa dilihat juga kalo dulu aku ninggalin soal ini lama, dan baru dapet inspirasi pas nyoba ngerjain lagi.

Pada tahap ini, tolong lupakan DP matrix dulu.

Jadi intinya: ini kan sekuens, kita bisa kan anggep dia sebagai penggabungan 2 sekuens lainnya? Dengan kata lain, misal banyak cara membuat sekuens dengan panjang $L$, dan hasil jumlahannya $Z$ dalam modulo $M$ kita nyatakan sebagai $ways(L, Z)$. Maka, kita bisa cari nilai tersebut dengan cara sebagai berikut:

$$ways(L, Z) = \sum_{i=0}^{M-1} ways(L', i) \times ways(L-L', (Z-i) \mod{M})$$

Dengan $L'$ menyatakan panjang sekuens pertama dari 2 sekuens.

Kenapa bisa begitu? Ingat kaidah perkalian dari SMP atau SMA. Kalau kita potong jadi 2 sekuens, masing-masing panjangnya $L'$ dan $L-L'$, banyak cara di 2 sekuens itu saling independen. Untuk menggabungkannya, kita harus mengalikannya. Apabila sekuens pertama memiliki hasil jumlahan $i$, agar menjadi $Z$ ketika digabung dengan sekuens kedua, maka sekuens kedua harus memiliki jumlahan $(Z-i)\mod M$. Ya, kurang lebih gitu.

Oiya, harusnya cukup jelas ya kalau $ways(1, Z) = cnt[Z]$. Lalu, $ways(0, 0) = 1$.

Selanjutnya, kita bisa mencari $ways(L, *)$ (* artinya dari 0 sampai $M-1$) dalam $O(M^2)$ apabila kita punya $ways(L', *)$ dan $ways(L-L', *)$. Ini sebenarnya bisa kita bawa ke ranah fast exponentiation. 

Karena kita punya $ways(1, *)$, maka kita bisa mendapatkan $ways(2, *)$ dengan "mengalikan" $ways(1, *)$ dengan dirinya sendiri. Selanjutnya, dapat dilihat bahwa kita bisa mendapatkan semua $ways(2^i, *)$ dengan mudah. "Kalikan" dengan $ways(2^i, *)$, hingga jumlahan panjangnya $K$, dan hasilnya bisa didapat di entri $X$. Kita hanya perlu $O(\log K)$ "perkalian", yang mana tiap "perkalian" hanya butuh $O(M^2)$ operasi. Maka, untuk tiap kasus uji kita hanya butuh $O(M^2 \log K)$, dan cukup untuk mendapatkan AC.

Contoh solusi:
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int MOD = 1e9 + 7;

int A[N];
int n, m, k, x;

void read() {
  scanf("%d", &n);
  for (int i = 0 ; i < n ; i++) {
    scanf("%d", &A[i]);
  }
  scanf("%d %d %d", &m, &k, &x);
}

// "perkalian" untuk dapat ways(L, *)
vector<int> multiply(vector<int> a, vector<int> b) {
  vector<int> ret(m, 0);

  for (int Z = 0 ; Z < m ; Z++)
    for (int i = 0 ; i < m ; i++) {
      int j = (Z - i + m) % m;
      
      // jumlahan = i dari a, jumlahan = j dari b
      ret[Z] = (ret[Z] + 1ll * a[i] * b[j]) % MOD;
    }
  
  return ret;
}

vector<int> power(vector<int> base, int pwr) {
  // identitas; sekuens kosong jumlahannya 0
  vector<int> ret(m, 0);
  ret[0] = 1;

  while (pwr) {
    if (pwr & 1) ret = multiply(ret, base);
    base = multiply(base, base);
    pwr >>= 1;
  }

  return ret;
}

int work() {
  vector<int> cnt(m, 0);
  for (int i = 0 ; i < n ; i++) {
    cnt[A[i] % m]++;
  }

  cnt = power(cnt, k);
  return cnt[x];
}

int main() {
  int t; cin >> t;
  for (int tc = 1 ; tc <= t ; tc++) {
    read();
    printf("%d\n", work());
  }
  return 0;
}

Simple and clean. Tidak perlu nulis perkalian matriks dan lebih ngebut :P

Contoh Lain - Pasti Menang!

shamelessly using own problem for example again, lel

Tautan menuju soal: Final SCPC CompFest 9 - Pasti Menang!

Abstrak soal: Ada game, yang mana game-nya dimainkan di DAG, dengan tiap node-nya antara tidak ada bidak, atau mungkin ada >= 1 bidak. Total ada K bidak. Akan dilakukan permainan yang dilakukan oleh 2 orang, dengan gerakan tiap orang adalah memindahkan salah satu bidak ke node lain yang ada direct edge-nya. Pemain kalah kalau tidak bisa menggerakkan bidak. Kita mau bikin konfigurasi peletakan bidak sedemikian hingga kalau 2 orang ini mainnya optimal, pasti orang pertama yang menang. Tentuin banyak caranya.

Udah nyoba bikin abstrak tapi masih kurang ringkas kayaknya ;_; Maaf ya. Anyway, ini soal dulu pas lombanya nggak ada yang AC ;_; Harusnya dengan pengetahuan dari paragraf sebelumnya + sesuatu cukup sih untuk solve soal ini. Coba kerjain dulu ya, baru scroll ke bawah.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

Observasinya:

  • Kalau bidaknya udah diletakkan bakal jadi nim-game, yang berdasarkan Sprague-Grundy Theorem pemain pertama pasti menang jika dan hanya jika hasil xor dari nimber $K$ bidak itu bukan 0
  • Nimber maksimum dibatasi oleh $\sqrt M$, kasarannya maksimum ada sekitar 400. Artinya, hasil xor dari nimber $K$ bidak maksimum 511.
Kita bisa modelkan ini jadi permasalahan The Toy Store, tapi di sini kita pakainya xor. Contoh solusi yang kucomot dari githubku:

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 8;
const int N = 5e4 + 5;
const int MAX_GRUNDY = 512;

vector<int> multiply(vector<int> &a, vector<int> &b) {
    vector<int> ret(MAX_GRUNDY, 0);

    for(int i = 0 ; i < MAX_GRUNDY ; i++)
        for(int j = 0 ; j < MAX_GRUNDY ; j++)
            ret[i] = (ret[i] + 1ll * a[j] * b[i ^ j]) % MOD;

    return ret;
}

vector<int> power(vector<int> base, int po) {
    vector<int> ret(MAX_GRUNDY, 0);
    ret[0] = 1;

    while(po) {
        if(po & 1) {
            ret = multiply(ret, base);
        }

        base = multiply(base, base);
        po >>= 1;
    }

    return ret;
}

int grundy[N];
vector<int> adj[N];
int n, m, k;

void read() {
    scanf("%d %d %d", &n, &m, &k);

    for(int i = 0 ; i < m ; i++) {
        int u, v;
        scanf("%d %d", &u, &v);

        adj[u].push_back(v);
    }
}

void prepare() {
    for(int i = 1 ; i <= n ; i++) {
        set<int> s;

        for(int x : adj[i]) {
            s.insert(grundy[x]);
        }

        for(int j = 0 ; ; j++)
            if(!s.count(j)) {
                grundy[i] = j;
                break;
            }
    }
}

int solve() {
    vector<int> ret(MAX_GRUNDY, 0);

    for(int i = 1 ; i <= n ; i++) {
        ret[grundy[i]]++;
    }
    ret = power(ret, k);

    int ans = 0;
    for(int i = 1 ; i < MAX_GRUNDY ; i++) {
        ans = (ans + ret[i]) % MOD;
    }

    return ans;
}

void reset() {
    for(int i = 1 ; i <= n ; i++) {
        adj[i].clear();
    }
}

int main() {
    int t; 
    scanf("%d", &t);

    for(int tc = 1 ; tc <= t ; tc++) {
        read();
        prepare();
        printf("%d\n", solve());
        reset();
    }
    return 0;
}

Kompleksitas akhirnya per kasus uji adalah $O(M \log M + (\sqrt M)^2 \log K)$ = $O(M \log M + M \log K)$.

Soal Latihan

Aku gak terlalu tahu sih soal-soalnya, rasanya gak banyak yang emang harus banget pake ini. Beberapa yang bisa dipakai:



Penutup

Trik ini lumayan lucu sih, kalo menurutku. Terus ngodingnya juga nggak terlalu susah, nggak harus tau perkalian matriks (aku kadang rada pusing ngaliin matriks, tapi nggak akut kok). Mungkin rada spesifik kasusnya, tapi yaa lumayan berguna. Selain itu, walaupun dibahasnya tadi di ranah jumlah dan xor, aku sendiri yakin kalo bisa dengan operator lain juga, misal hasil kali. Oiya, untuk yang soal latihan terakhir, itu modelinnya rada beda, jadi itu bisa jadi latihan yang bagus :P

Akhir kata, semoga post ini bisa bermanfaat dalam menambah wawasan.

Minggu, 28 Oktober 2018

Maximum Average

Mencoba membuat hari terakhir di Bontang produktif sebelum besok balik ke Depok

Sebenarnya udah mau nulis ini dari lama, cuma meniatkannya gak pernah bisa. Anyway, di post kali ini aku bakal bahas tentang maximum average. Iya, bukan sum. Average.

Kalo mo cerita, soal yang pake trik ini aslinya pernah dikasih ke anak Pelatnas 2017 buat latihan. Cuma gak dibahas. Terus pas APIO beberapa hari setelah latihan itu, ada satu soal yang pake konsep ini. Such a coincidence.

Oiya, dulu aku baca trik ini dulu di e-maxx, pas dulu iseng-iseng baca e-maxx dengan modal translate yandex. Artikel e-maxx yang kubaca.

Ide Utama - PROSJEK

Yaudah deh, langsung aja liat contoh soalnya ya. Soal COCI 2014/2015, PROSJEK.

Soalnya pendek, intinya: Dikasih array ukuran $N$, cari rata-rata maksimum subarray yang ukurannya lebih dari atau sama dengan $K$.

Nah, kalo $K = 1$ kan gampang ya. Cuma jelas pembuat soal gak bakal sepintar itu ngasih $K = 1$. Jadi kita coba gali lagi dari soal ini.

Karena $N$ gede ($3 \times 10^5$), gak mungkin kita coba tiap subarray yang notabene $O(N^2)$. Kita harus cari properti yang mungkin bisa dipakai. Biasanya, kita lempar ide-ide liar:

  • Mungkin cari yang sum-nya maksimum?
    • Gagal, liat aja $K = 1$
  • Mungkin liat yang ukurannya tepat $K$?
    • Gagal, liat aja sample 2, dia ngambil yang ukurannya 3 (2 4 3 4)
Sebenarnya apa kesulitan utama kita? Ada 2 hal yang harus dipertimbangkan, yaitu jumlahan elemen dan panjang subarray. Ada 2 variabel yang saling berpengaruh, sehingga mencari optimalnya tidak mudah.

Mari lempar ide liar lagi: Mungkin gak jawabannya bisa di-binary search? Atau dengan kata lain, mungkin gak untuk suatu $x$, ada subarray yang ukurannya lebih dari atau sama dengan $K$ yang punya rata-rata >= $x$?

Biasanya, kalo binary search the answer kita harus bisa validasi suatu tembakan jawaban dengan cepat. Nah, ini gimana cara ngeceknya dengan cepat? Bukannya harus cek satu-satu lagi tiap subarray yang ukurannya seenggaknya $K$? Well, mari kita main-main formula matematika:

$$ \frac{\sum_{i=l}^{r} a_i}{r-l+1} \ge x$$ $$ \sum_{i=l}^{r} a_i \ge (r-l+1) \times x$$ $$ \sum_{i=l}^{r} a_i - (r-l+1) \times x \ge 0$$ $$ \sum_{i=l}^{r} (a_i - x) \ge 0$$

Wah, ada sesuatu yang berguna. Secara ajaib panjang subarray jadi tidak dipertimbangkan lagi.

Katakanlah kita ingin memeriksa apakah ada subarray yang punya rata-rata >= $x$. Kita bisa membuat array baru, $a'$, yang mana $a'_i = a_i - x$. Selanjutnya, cukup memeriksa apakah ada subarray pada $a'$ yang jumlahannya >= 0. Untuk memeriksa yang ukurannya >= $K$, kita bisa simpan nilai minimum prefix sum tiap indeks yang valid. Untuk mengeceknya bisa dalam $O(N)$, sehingga digabung binary search kompleksitasnya jadi $O(N \log a_i)$

Contoh solusi PROSJEK:
#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 5;
const int TRIAL = 50;
const double EPS = 1e-9;

int arr[N];
double psum[N];
int n, k;

void read() {
  scanf("%d %d", &n, &k);
  for (int i = 1 ; i <= n ; i++) {
    scanf("%d", &arr[i]);
  }
}

bool check(double x) {
  // prefix sum, karene a_l + ... + a_r = prefix_r - prefix_{l-1}
  for (int i = 1 ; i <= n ; i++) 
    psum[i] = psum[i-1] + arr[i] - x;
  
  double mins = 1e9;
  for (int i = k ; i <= n ; i++) {
    // prefix_{i-k} jadi valid saat iterasi ke-i
    mins = min(mins, psum[i - k]);

    if (psum[i] - mins > -EPS)
      return true;
  }

  return false;
}

double work() {
  double lo = 0, hi = 1e7;
  
  for (int i = 0 ; i < TRIAL ; i++) {
    double mid = (lo + hi) / 2;

    if (check(mid)) lo = mid;
    else hi = mid;
  }
  return lo;
}

int main() {
  read();
  printf("%.9lf\n", work());
  return 0;
}
Contoh Lain - Road to Hero

Ini soal yang dulu dipake di JCPC CompFest 8. Berkas-berkas terkait soal dapat diakses di sini. Oiya, hampir semua soal CompFest udah ada di TLX. Cuma CompFest 7 sama 8 belum masuk karena sesuatu. Sementara cek soal Road to Hero ini di github aja dulu ya.

Inti soalnya: Dikasih DAG, cari maximum average path dari persimpangan 1 ke persimpangan $N$.

.
.
.
.
.
.
.
.
.

Oke ini intinya kayak pertidaksamaan tadi ya. Cuma sekarang kita pakenya edge dari grafnya. Setelah bobot semua edge dikurangi $x$, maka kita cukup ngecek ada apa nggak path dengan cost >= 0. Berhubung ini DAG jadinya lebih mudah karena tidak ada cycle. Kita cukup mencari longest path dari 1 ke N, yang bisa dicari pakai DP. Sehingga, kompleksitasnya $O((N + M) \log P_i)$.

Contoh solusi dapat dilihat pada github soalnya.

Soal Latihan

Beberapa soal yang menggunakan konsep serupa:

Penutup

Trik mencari maximum average ini bisa dibilang kayak wrapper-nya aja, yang beda di tiap soal cuma buat cara cek validitasnya (kayak binary search the answer biasa). Sejujurnya aku nggak ngerti aku ngomong apa di kalimat sebelumnya, semoga kalian ngerti.

Akhir kata, semoga post ini bisa meningkatkan wawasan. Dan semoga aku bisa balik ke Depok dengan selamat, karena sayang amplang-nya kalau nggak dimakan.

Jumat, 12 Oktober 2018

Indonesia National Contest 2018

Nampaknya, niatan di semester lalu buat nulis seminggu sekali udah gagal, haha.

Oke, ini bakal sedikit melenceng dari judul. Minggu lalu, selain ikut INC, aku juga ikut penyisihan keamanan jaringan sama pemrograman dari Gemastik. Biasanya, aku ikut lomba-lomba kayak gitu karena:
  • Sifatnya objektif
  • Fun
Tapi kayaknya Gemastik kemarin benar-benar kebalikannya. Kalo aku harus deskripsikan, pengalamanku kurang lebih "not fun", "annoying", sama "disgusting". Tapi daripada blogpost ini isinya jadi rant, mari kita sudahi membahas Gemastik sampai sini saja.

Oke, buat INC sama ICPC regional nanti, aku bakal ada di tim Supir Tayo sama Degol + Inigo (kayaknya Inigo masih gak tau kenapa aku pengen kasih nama Tayo). Terus walaupun kemaren ada ngomong ke orang-orang kalo aku kemungkinan besar gak ikut regional ke luar, turns out tahun ini ada tetep ke luar setelah beberapa pertimbangan. Tapi akunya juga udah rada bego sih hehe, jadi jangan berekspektasi tinggi :P

Anyway, setelah Gemastik pemrograman yang web-nya down 2 jam (bikin kacau luar biasa), aku jadi nanya FJ perihal INC besoknya, karena tahun lalu INC juga sempat kacau sekitar 1 jam. Responnya lumayan pede, jadinya aku harap gak down bakalan haha. 

Oiya, terus malam sebelumnya kan ada IPSC, aku ikutan juga sama Prabowo + Agus. Walaupun jadinya tidur jam 3 pagi, gak sia-sia karena selama sejam ngedenger Agus jadi pelayan Mcd. Terus, ada pembicaraan, terkait pola selama aku ikut INC:
#2019PilihPrabayar


Iya, aku emang berekspektasi peringkat 4 atau 5 :P

Untungnya, walaupun baru bisa tidur sekitar jam 4-an, masih bisa bangun buat pergi ke kampus demi INC. Pas nyampe, masih ada waktu sekitar 45 menit, jadi bisa minta tolong buka lab dulu sama siap-siap. Untungnya, gak kayak tiap latihan, Inigo sama Degol bisa datang tepat waktu kali ini :P Sebelum kontes mulai, kesepakatannya Degol baca 1/3 pertama, Inigo 1/3 tengah, aku sisanya, mulai dari soal I.

Omong-omong, soal dapat diakses pada tautan berikut.

Kontes mulai! Pas baca:

I: aih expected value. Tapi kayaknya bisa
J: sort terus greedy harusnya, cuma nggak yakin yang ukuran grupnya gede taruh di depan atau belakang, sama gak yakin begitu optimal apa nggak
K: notasi matematis. skip dulu
L: terlihat panjang, skip
M: terlihat pendek, macem TSP tapi ada properti anehnya. Kayaknya greedy tapi ngerepotin

WTF ini soalnya aneh semua.

Degol bilang dia mulai ngoding A. Terus aku masih ngoret-ngoret I dulu dikit. Udah dapat sekilas, aku baru mulai ngerjain J. Pas liat di scoreboard udah ada yang AC J, jadi yakin kalo solusinya harusnya greedy yang gampang. Karena gak tahu yang optimal yang mana, yaudah.. aku cobain aja dua-duanya :P Submit, J - A Study on Groups AC. Beberapa menit sebelumnya, ternyata Degol udah AC A - Tour de BINUS sama D - Substring Permutation.

Inigo bilang dia ngerjain F. Terus, aku sama Degol ngeliat scoreboard. Yang lumayan rame E sama H. Degol terus ngerjain E, sementara aku ngerjain H. Yang H pas dibaca kayaknya bisa DP Digit -- state-nya [indeks][angka non zero terakhir][udah kurang dari boundnya belom]. Habis ngoding yang ngebug-ngebug, H - Plate Parity AC.

Inigo sama Degol masih ngoding, terus aku sekilas baca soal B. Kayaknya malesin, aku jadinya ngerjain I. Pas baca soalnya lagi, ternyata tadi aku salah ngerti soal. Kukira awalnya yang dihapus itu indeks-indeks yang A[i]-nya habis dibagi P[j], bukannya i habis dibagi P[j] :"( Habis itu aku ngoret-ngoret lagi. Intinya mau nyari fungsi f(K), yaitu berapa kali suatu bilangan muncul pada sekuens X, apabila ada K bilangan di [1, N] yang habis membagi indeks tempat bilangan itu. Dengan sedikit kombinatorik, nilai f(K) bisa dihitung dalam O(N). Selanjutnya, pembilang dari expected value-nya kan pasti jumlahan f(banyak_pembagi_i) * A[i]. Nah, tapi O(N2). Bisa dipercepat dengan memanfaatkan fakta banyaknya pembagi berbeda itu dikit, sekitar 100 lah kasarannya. Jadinya semacam O(N * sesuatu). Seperti biasa, ngebug-ngebug dulu. Habis bener, submit, I - Expected Value of a Permutation AC.

Habis itu, aku ngecek Degol sama Inigo. Degol E ngebug, Inigo F belum selesai. Aku jadinya minta Degol jelasin soal E ke aku, biar nantinya aku takeover sama dia bisa bantu Inigo. Setelah dijelasin soal dan dikasih beberapa observasi penting, aku ngoding E. Ngebug juga yey. Ada masalah dengan state untuk ngitung buat sekuens good. Habis bener-benerin lagi, E - The Good, the Great, and the Superb AC. Pas ngerjain, gak sengaja denger Degol ada ngomong Hopcroft-Karp ke Inigo, kayaknya soal F ada matching-nya.

Habis itu aku nanya ada yang bisa dikerjain apa nggak, terus Degol jelasin soal C. Intinya dikasih tree yang per verteks-nya ada nilai, katakanlah A[i]. Terus ada Q query, untuk suatu path, itung banyak verteks yang memenuhi L <= A[i] <= R. Oke, ini harusnya bisa dikerjain secara offline pake BIT sama LCA. Intinya, pisah query jadi 3 bagian, yaitu di kedua ujung path, sama di LCA-nya. Lakukan DFS, pelihara BIT yang isinya data dari root hingga ke node sekarang. Kalo di LCA, artinya kurangi dengan 2 kalinya, tapi kalo di ujung path artinya tambah. Terus ada main coordinate compression juga. Capek sih, tapi yaudahlah, coding aja.

Habis ngoding yang tentunya ngebug lagi, aku cek sample-nya. Lho, ini kok angkanya gede. Lho, ternyata diminta jumlahan A[i]-nya, bukan cuma banyaknya yang memenuhi. Untung modifikasinya gak susah. Tapi ya ngebug lagi. Benerin, submit, WA. Oh, query BIT-nya masih pake int, harusnya long long (aku nggak suka pakai long long kecuali emang perlu). Submit lagi, C - Hierarchical Architecture AC. Pas AC, beberapa saat sebelumnya juga ternyata F - KMP AC. Kalo gak salah ini ngelempar kami yang sebelumnya posisinya sekitaran 5~10an jadi top 5. Padahal pas di awal-awal masih 15~20an terus hehe.

Habis itu, seperti biasa:

Ayaz: "Ada lagi gak yang bisa gw kerjain?"
Degol: "Ini Yaz ada soal G. Tenang ini kayak geometri tapi bukan geometri."

Intinya dikasih beberapa titik, mau bikin mereka titik pusat lingkaran, dengan syarat untuk 2 lingkaran, yang satu berada di dalam yang lainnya.

Degol: "Gw bisa N faktorialnya"
Ayaz: "Nice info gan"

Tapi aku sendiri lupa sih approach-nya Degol gimana hehe :") Habis mikir sejenak, aku kepikiran kalau:

  • Kalau B tepat di dalam A, harusnya lingkaran A berimpit di B di beberapa bagiannya
  • Asumsikan C lingkaran terkecil dalam suatu himpunan (radius 0), terus mau masukin D ke dalam himpunan sebagai lingkaran terkecil. Pasti C radiusnya nambah sebanyak jaraknya ke D. Karena observasi sebelumnya, kalau B lingkaran terkecil yang lebih besar dari C, pasti B radiusnya nambah sebanyak ini juga demi menampung C. Dst, intinya semua dalam himpunan radiusnya nambah sesuai jarak C ke D.
Kalau benar, artinya solusinya bisa pakai DP Bitmask dengan state [lingkaran terkecil][bitmask]. Kompleksitasnya O(N22N). Yaudah aku coba coding aja. Entah kenapa rasanya awkward ngoding DP dengan nilai floating-point, terus aku jadinya pake variabel boolean buat nandain suatu state udah diitung apa nggak. Submit, yey G - Discs AC. Kalau gak salah ini ngelempar kami ke peringkat 1 pas itu.

Habis itu, aku bilang ke Degol sama Inigo kalo kayaknya mereka bisa ngerjain soal M. Habis aku jelasin soalnya, mereka ngerjain soal itu. Sementara itu, aku mikir soal B. Kayaknya bisa pake BBST, tapi gak suka, males ngodingnya. Terus kepikiran semacam Sqrt decomposition. Intinya bagi list-nya jadi blok-blok berukuran K (bloknya pake vector). Simpen tiap angka ada di blok mana. Untuk dapetin pergeserannya kan bisa didapat dari selisih indeksnya, jadi sekarang mikir cara dapet indeksnya. Untuk dapetin indeks, bisa aja loop O(N / K + K), iterasi tiap blok yang indeksnya kurang dari indeks bloknya, terus iterasi dalam bloknya itu sendiri. Untuk update, yaudah geser secara naif aja. Nah, kalo udah K kali update, bikin ulang blok-bloknya. Jadinya kompleksitasnya bakalan semacam O(Q(K + N / K)). Biasanya bagusnya K = sqrt(N), cuma aku malas, jadinya aku pasang K = 400. Terus aku nyoba-nyoba beberapa hal, ternyata percobaanku cacat, jadi buang waktu sekitar 10 menitan. Habis yakin, submit. Beberapa saat kemudian, B - Linked List AC.

Inigo sama Degol masih ngomongin kasus-kasus soal M. Aku dengerin sekilas entah kenapa rasanya serem. Karena sisa K, L, M aku jadinya harus baca sendiri, secara itu tanggung jawabku semua harusnya :"D Aku jadinya baca L, karena itu aja yang aku masih bener-bener buta. Habis baca, intinya gampang, cuma bikin turnamen rigged.

Awalnya kepikiran DP bitmask, cuma gak yakin muat apa nggak. Habis itung-itungan, kayaknya muat. Aku ngebikin semua transisinya dulu di awal, nyoba optimasi aja. Habis itu, ngoding DP-nya gak terlalu susah. Sample bener, submit, WA. Baru habis itu nyadar, oiya harus nyimpen di suatu subtree yang menang siapa. Jadinya state-nya dari [bitmask] jadi [siapa yang menang][bitmask]. Ngoding lagi, ngebug lagi, debug lagi. Submit, WA lagi. Sial, ternyata di prekomputasinya ada yang lupa dibalikin karena tadi lagi ngecek buat nilai N kecil :" Habis dibenerin, L - Fair Tournament AC. Yang bikin kaget, ternyata kami gak first solve soal L. Padahal di atas-atas belom ada yang AC. Habis scroll ke bawah, ternyata ada tim yang udah AC :/ Aneh, jadi keinget ICPC Nakhon Pathom tahun lalu.

Degol sama Inigo udah submit M, tapi kayaknya ada kasus yang kelewat. Degol mencoba debug, sementara aku sama Inigo mencoba memahami K. Setelah diskusi, konklusinya di soal ini mencoba cari cycle terkecil di suatu graf. Dari batasan, O(NM) kan nggak bisa. Terus pake properti DFS spanning tree juga gak bisa, bisa aja loncat-loncat back edge. Tapi karena nekat, aku coba submit dulu O(NM) pake BFS, dengan semua komponen tree di-skip. Cuma ya TLE.

Karena N, M <= 20000, aku pikir kayaknya ini bakal perlu bitset-bitset-an. Terus hasil oret-oret kayaknya bisa pake BFS, simpen semua ancestor di BFS tree. Sayangnya, setelah ngoding dan WA-WA, baru ketemu kasus yang gagal. Jadinya pusing. Terus Degol juga M terus berhasil menemukan kasus baru, tapi masih WA-WA. Sampai beberapa menit terakhir, kami masih belum nemu titik terang untuk soal manapun. Sampai beberapa menit terakhir, kami rank 1 dengan AC 11, terus rank 2 AC 11 juga.

Di 5 menit terakhir, aku buka minesweeper sambil berharap yang rank 2 gak nambah. Berapa detik kemudian aku tutup, karena dapetnya naas melulu minesweeper-nya (klik pertama bentuk kotak). Was-was, pas 300 menit lewat masih rank 1. Ternyata habis beberapa menit kemudian, ada submisi soal K dari Kth-D Hyperprism yang AC xD jadinya kami kegusur ke rank 2 di menit terakhir.

Tbh, I am not even mad. I was really amused xD

Jadi karena kurang nekat, kami kegusur ke rank 2. Seenggaknya nggak seperti perkiraanku bakal rank 4 atau 5 :P Scoreboard akhir, sampai rank 10:

Supir yang bisa ngoding

Masih banyak yang harus dibenahi sampai regional Jakarta nanti, tapi kurasa yang sekarang Supir Tayo gak buruk-buruk amat.

Yaudah deh, kurasa sampai ini saja dulu. Sampai bertemu di Binus bulan november nanti :D

Notes:
  • Solusi yang aku coding bisa dilihat di tautan berikut
  • Solusi M Degol udah 400 baris, masih WA :"")))
  • Kayaknya salah satu kontes terbaik yang aku ikuti tahun ini :D Problemset menarik dan lumayan seimbang. Terus nggak down sama soalnya juga jelas

Sabtu, 24 Maret 2018

Menutup Poligon

Phew, baru sempet nulis lagi...

Aslinya banyak yang terjadi, kayak kesalahan konyol di Kickstart Round A, kehidupan kuliah yang tambah broken, sama kegeblekan lainnya. Cuma kayaknya sekarang mau fokus nulis tentang salah satu soal yang kuurus di TOKI Open Contest Maret 2018, Menutup Poligon (Sulit & Mudah).

Jadi kalau mungkin belum sadar, di pengumuman TOC, ada namaku nongol di belakang. Yep, mulai bulan ini, aku juga ikut jadi panitia TOC. Bantu ngurus-ngurus gitu. Moga aja gak jadi beban T_T Btw, dari panitia TOC cuma aku yang sekarang domisilinya di Indonesia :")

Buat TOC kemaren, sebenernya aku ngurus testcase buat 3 soal, yakni Menutup Poligon (Sulit & Mudah), sama Lapangan Tembak (Sulit). Walaupun sebenernya jadi kayak ngurus 4 soal, karena runner Lapangan Tembak (Sulit) juga diedit jadi versi mudah-nya, sama Ammar tapi. Tapi well, mari fokus ke soal yang bikin testcase-nya itu kayak neraka.

Oiya, tulisan di bawah mungkin aja mengandung spoiler ya. Sudah saya tulis warning di sini :P

Btw, ini cara aku buat testcase. Kalau ada cara yang lebih elegan (dan aku sangat berharap ada), bisa komentar di bawah :D

Jadi, soal versi sulit kan intinya ngecek bisa tutup pake persegi 2 x 2. Nah, cuma gimana caranya bisa bikin testcase yang ukurannya besar, dan jawabannya "YA"?  Yang pertama kepikiran sih jelas, bikin persegi 2 x 2 yang nempel-nempel. Jadi pertama bikin grid, terus pasang-pasang persegi. Kalo udah,  transformasi grid-nya jadi format masukan yang diminta. Idenya sih gitu.

Cuma, pertama-tama, sebelum aku ngoding itu....
Aku harus bikin validator constraint-nya.
Terus aku gak tau caranya ngecek poligon gak ada motong diri sendiri selain dalam O(N^2).
Mantap gan.

Berhubung soal ini harusnya gak perlu bikin testcase yang banyak garis miringnya, aku jadinya bikin 4 pengecekan: motong horizontal-horizontal, vertikal-vertikal, horizontal-vertikal, sama garis miring-bebas. 3 Pertama bisa O(N log N), yang terakhir O(garis_miring * N). Jadi selama garis miringnya gak banyak, harusnya ngeceknya gak lama. Cuma ini ngodingnya neraka :"""

Oiya, kalo ada yang tau cara ngecek apakah poligon gak ada motong diri sendiri yang cepet, mungkin bisa komentar di bawah juga :"""

Nah, setelah bikin validator constraint, balik ke bikin jawaban "YA" yang gede.

Aku pertama bikin cara transformasi grid-nya jadi poligon, sesuai format masukan. Sebenernya gak terlalu susah, cuma nelusurin sisi-sisi poligon menurut arah jarum jam doang. Agak hardcode sih, nanganin jalan sama beloknya. Gak terlalu susah, cuma ngerasa ini bisa jadi 1 soal sendiri.

Habis meyakini transformasinya dah bener, aku bikin generator nempel-nempel persegi 2 x 2. Iseng, cek kalo perseginya 5, bisa. Langsung hajar gede, coba perseginya 50.000. Gagal, ada constraint yang dilanggar. Ada titik yang muncul 2 kali di input. Hmmm, harusnya gak mungkin gini. Coba perseginya 10. Gak gagal, tapi jawabannya "TIDAK".

wat. wat. wat. wat.

Aku coba cetak poligon sama petak-petak grid yang ditempeli persegi. Hasilnya kayak gini:


Yang disilangin itu petak yang ditempeli persegi. Pas sadar ada petak bolong, yakni petak yang dihitamkan itu, rasanya:


Jadi ya, intinya gak bisa main tempel sembarangan aja. Aku harus periksa juga apakah dengan masang itu, bakal bikin "lubang" di poligon akhirnya. Jadi yang begini ya gak boleh:


Cuma gimana coba ngeceknya? Berhubung "lubang"-nya bisa ukurannya apa aja, aku cuma kepikiran flood-fill awalnya, yang gak mungkin feasible kalo untuk bikin testcase. Pusing parah itu.

Cuma gak mungkin nyerah untuk bikin testcase-nya, berhubung TOC-nya udah dekat :"" Jadinya aku coba pikir lagi gimana cara ceknya. Aku curiga bisa dibikin pake properti planar graph. Rasanya dulu pas matdis 2 pernah dapet formula terkait vertex, edge, sama face di planar graph. Terus nemu laman di Wikipedia terkait itu.

Jadinya aku coba modelkan jadi  planar graph: anggap petak 1 x 1 itu 1 vertex. Lalu, buat edge di antara 2 vertex yang bersebalahan dan udah ditempeli. Aku bisa itung face yang berupa persegi 2 x 2. Kalau gak ada "lubang", harusnya total face yang bisa kuitung itu sama dengan v - e + f = 1, dikurangi satu karena ada face di luar grafnya. Misal untuk gambar di atas, graf-nya artinya begini:

Ada 12 vertex, 16 edge, sama 4 face persegi 2 x 2. Tapi, 12 - 16 + 4 = 0, artinya ada satu face yang gak kuitung, yakni yang di tengah. Maintain banyak vertex, edge, sama face gak terlalu susah. Artinya, secara ajaib aku bisa nanganin agar tidak ada "lubang".

Jadi ini rasanya mendapatkan pencerahan.

Habis aku tambahin pengencekan itu, code-ku udah berantakan banget. Aku coba generate testcase lagi.

Gagal. Ada titik yang muncul 2 kali di poligon.


Jadi ini rasanya frustrasi.

Aku coba cetak poligonnya lagi. Kurang lebih begini potongannya:

intinya gambar yang di tengah
Pas liat gambar kurang lebih ngeh sih. Jadi, ada 2 petak yang sharing sudut doang (yang ditandai titik di atas), bikin "lubang" lagi. Bingung sih ini harus diapain. Cuma firasatku, cukup cek apakah ada petak yang sharing sudut doang udah cukup, karena kalo nggak sudut doang, "lubang" pasti kena kasus planar sebelumnya. Pas dicoba, udah gak ada yang gagal lagi. Yey!

Setelah bikin untuk nempel-nempel 2 x 2, aku juga bikin untuk nempel 1 x 1, karena bakal berguna untuk bikin testcase invalid dan bikin testcase versi mudah soal ini. Setelah itu, aku juga bikin fungsi buat hapus sembarang titik, niatnya biar poligonnya jadi punya garis miring. Cuma ngebug-ngebug, hingga akhirnya jalan. Ini fungsi dibutuhin soalnya buat versi mudah dari soal ini.

Habis itu, nambahin testcase manual dari Ammar, sama pattern pemasangan persegi dari Jonmul. Udah beres, sisa di-review. Pas review, baru sadar kalo validator perpotongan vertikal-vertikal sama horizontal-horizontal ngebug T_T Jadinya beberapa testcase manual Ammar lolos. Habis benerin validator, testcase-nya Ammar jadi harus diubah dikit. Udah deh.

Btw, ini gak tau gimana rasanya yang nge-review. > 1000 baris. Sebenernya bisa aja di-refactor karena beberapa fungsi mirip, cuma otakku udah overheat. Parah. Btw, untuk versi mudah sih gak terlalu susah begitu yang versi sulit udah jadi. Tinggal comot validator, masang 1 x 1, sama hapus titik.

Habis entah gimana caranya ini runner bisa lolos review, soalnya dipasang. Di kontesnya, soal ini mayan berdarah-darah hasilnya.


Gak papa, yang bikin testcase-nya juga berdarah-darah kok. Seenggaknya ada 3 soal di pembuatan testcase-nya: solusi-nya, transformasi grid ke poligon, sama cek planar. Ini juga gak ngitungin soal ke-4, ngecek validitas testcase.

Sampai sekarang, kayaknya ini soal paling berdarah-darah yang pernah kuurus deh. Semoga gak ngurus soal beginian hingga beberapa waktu lagi :""

Mungkin sekian aja kali ya, sampai bertemu di post selanjutnya :D

Minggu, 04 Maret 2018

Daily Life #4

Wah minggu lalu skip :(

Jadi minggu lalu aku kelarin Mario Rabbids di Switch-ku. Mayan sih main strategi gitu, aku lumayan suka. Chapter 100%, Chest 100%, Challenge 88%. Gak kuat ngerjain Ultimate Challenge-nya, jadinya aku anggap sudah saja mainnya :)) Sekarang aku main Super Mario Odyssey, tapi harus nahan diri karena masih banyak kerjaan :"(

Minggu lalu, pas weekend juga ada setup environment buat PPL.  Semua baik-baik saja sampai pas harus nambahin badge di README buat pipeline sama coverage. Kayaknya regex-nya gitlab bermasalah, jadi harus diakal-akalin sampe bener. Habisin waktu parah. Jalan sih akhirnya, cuma ya.. capek.

Oiya, aku jadi inget soal yang kutulis buat Oprec CP Ristek. Menurutku lucu sih. Intinya gini: 

Dikasih complete graph dengan $N$ node, dan $N$ bilangan $A_i$. Jalan antara node $i$ dan node $j$ panjangnya $A_i + A_j$. Cari cost MST dari graf tersebut.

Aku set N-nya gak lebih dari $1.000$ biar bisa solusi MST klasik, cuma aslinya soal ini N-nya bisa sampai $10^5$. Terus ya, menurutku solusinya cukup lucu sih :))

Btw, tadi malam ada COCI Round #7, round terakhir sebelum olympiad-nya. Aku ikut cuma karena diajak Irvin sih. Baca soal, paham A, B, C, E (skip D karena males panjang, dan pas dicek lagi gak sesuai jalan ninjaku), terus mulai kerjain. Ngebug-ngebug :| terus baca F dan "oh max-flow", terus ngoding. Iseng, gak copas template max flow dan coba ngoding dari scratch lagi :)) Ternyata masih bisa yey. Terus aku cek E, baru kepikiran kalo DP-ku ada bug-nya, jadi harus nambah kondisi state lagi. Masih sisa 1.5 jam, tapi males ngerjain D :P Jadinya aku urus hal-hal lain.

Pas pagi-pagi cek, loh ternyata E-ku WA semua testcase :( Aku cek codingan, ternyata ada 1 baris menyedihkan.

yang disubmit:
dp[now][i + j + 1][2] = max(dp[now][i + j + 1][1], temp[i][0] + dp[nex][j][0]);

harusnya:
dp[now][i + j + 1][2] = max(dp[now][i + j + 1][2], temp[i][0] + dp[nex][j][0]);

Yaudah deh, mayan geli sih tapi haha.

Hmm sekian dulu deh, semoga minggu depan gak skip lagi buat nge-post :D

Sabtu, 17 Februari 2018

Daily Life #3

Minggu ini rasanya gak sibuk-sibuk banget (atau menipu diri sedang tidak sibuk). Kesibukan di luar kuliah, paling terkait Ristek sama Pelatnas. Untuk Pelatnas, aku udah harus nyicil ngerjain bagianku daripada ntar mati '_' Kalo Ristek, kemarin nyiapin soal untuk open recruitment CP SIG, yang sekarang lagi jalan. Kontesnya sih dari jum'at sampai minggu ini. Semangat deh buat para peserta :)

Hmm, rasanya ada yang lain. Oh iya. Kemaren ada 2 hal berfaedah yang (akhirnya) kulakuin:

  • Nambah partisi Ubuntu di laptopku. Ini wacana dari tahun lalu cuma baru sekarang dilakuin.
  • Bikin script untuk automasi bikin tc dari tcframe, ke format zip yang diminta HackerRank.
Dan 1 hal yang kurang berfaedah:

  • Tamatin nonton anime Love Live! Sunshine!! S2
Btw, itu nambah partisi tanpa bikin backup sama sekali. Bermodal keyakinan kalo semua data penting di Ubuntu sama Windows udah ada di cloud juga. Untung gak ada masalah :")

ketika berhasil modif partisi tanpa ngerusak apapun
Oiya, aku juga ngerjain soal open recruitment-nya NetSos cuma gak niat-niat banget :P Berhenti pas skornya udah di angka cantik :P Btw buat yang ikut, namaku emang gak ada di Scoreboard :))

Minggu ini gak nambah banyak Kattis dan SPOJ D: Untuk Kattis, akhirnya tembus rank 200an :O Habis ini pasti perkembangannya melambat deh haha.

Sekian dulu deh minggu ini, moga minggu depan bisa lebih berfaedah yang dikerjain. Bikin tutorial gitu misalnya :"