Marcadian’s Blog

Ya penyisihan arkavidia udah ditutup. Ini sedikit write up dari gua. Soalnya ada 12. yang menurut gua distribusi tingkat kesulitannya adalah jelek (sorry, no offense buat panitia) karena menurut gua soalnya mayan susah, bahkan dari 3x ICPC yang gua ikuti, soal bonus di ICPC lebih gampang dari semua soal penyisihan kali ini. Ga kebayang d soal finalnya, kalo penyisihannya aja udah kayak gini. Untung parsial scoring kalo enggak, gua ga yakin nih ada 30 yg minimal solve 1. Soal2nya pun banyak yang udah pernah liat ato comot dari Online Judge.

Soal A -> coba cek http://spoj.pl/problems/ARCTAN  
Untuk soal ini, coba buang dulu arctan nya, kalo udah, utak atiknya rada tricky nih. Tar akhirnya tinggal
(B-A) * (C-A) = A*A + 1
Nah soalnya sekarang jadi tinggal faktorin A^2+1, bisa selesai dalam O(A) . Bisa googling nih soal waktu itu gua nemu hehehe

Soal B -> mirip sama http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1002
Bipartite macthing? mirhard yang buat, tidak terlalu tahu menahu

Soal C -> Pernah liat dimana gtu, dan pernah ada yang nanya. Salah satunya ada di topcoder

Catalan number!! Pertama gua coba pake rasio catalan, dapetin C[i] dari C[i-1] entah salah code ato emang pas itung overflow, ya ud ganti, keluarin yang udah pernah dibuat pake BigInteger java, dan hard code

Soal D -> baru liat!! ga tau mau diapain. beneran ada solusinya nih? yang bikin susah adalah, bisa ada cycle, dan boleh visit SPBU yang sama lebih dari sekali (gua ud klarifikasi nih)

Soal E -> DP, dah pernah nemu yg mirip2 tp ntah dimana
Mirhard yang buat, intinya sih simpen, kalo dari titik ini, maksimal ada berapa lagi yang nilainya < dan dalam batas

Soal F-> Klasik, diameter graph

Soal G -> Soal ICPC Kaoshiung 2006 http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3685
DP tree, sebenernya bisa cheating nih, buka aja web felix halim dan submit source codenya. Solusi O(V).

Soal H-> Dah pernah ngerjain soal yg minta trailing zero disini dan soal yang minta itung jumlah digit di UVA, lupa yang mana
Untuk itung digit suatu angka X
Digit = floor(log10(x))+1

Hitung angka 5 pada X! [EDITED : Thx to Turothok ]
Angka 5 = floor(X / 5) + floor(X / 25) + floor(X / 125) +  ….  

Soal I -> Ga pernah liat, susah. Ga tau solusi liniernya

Soal J -> Convex hull, klasik, tp g tau jadi pa kg

Soal K -> 2 soal TOKI digabung jadi 1, soal lipat OSN 2004 dan soal pelatnas 3 jaman dulu.

Soal L -> comot dari http://spoj.pl/problems/MATSUM
Pertama mencoba buat quadtree, bribet yah pas motong2nya, akhirnya beralih ke Binary Indexed Tree, baca dari sini, lom gitu ngerti motong2nya, rada aneh, tapi kalo nge mimic codenya sih bisa hehehe..

Well sekarang tinggal tunggu d grading semuanya.

Oh iya karena kontesnya lama gini, ada thread di kaskus yang nanyain soal J dan soal H tuh.

Dari semua soal, yang gua temuin di OJ udah gua coba dulu di OJ dan AC meskipun untuk soal A dan L di arkavidia gua ragu kalo solusi juri pun bisa di bawah 1 time limit (1 detik)  karena servernya setau gua enggak cepet2 banget (ayo yang punya server, klarifikasi spec nya ) , solusi gua di SPOJ sekitar 4 detik untuk soal A dan 5.5 detik untuk soal L.

Nah ini  (file zip nih, ubah dulu extensionnya, maklum wordpress gratisan )   sebagian solusi tim gua. Ga semuanya ada disini karena masih ada ma mirhard. waktu mo ambil dari server arkavidia pun udah ga bisa. Beberapa yang pake int 64 bit masih pake %I64, waktu mau submit udah diganti, ya silahkan disesuaikan dengan compiler masing-masing.

Well semoga panitia ngebuat pembahasan ato setidaknya mempublish test case dan solusi mereka.