Penyisihan Arkavidia Maret 17, 2009
Posted by marcadian in Event, Programming.trackback
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.
hehe, ga ada publish2an test case dan solusi ko, udah kesepatakan kami dari awal,
comparenya sama soal bonus ICPC sih…
klo comparenya sama soal bonus ICPC World Final, gmn?
coba gw ikutan wkwkkw, soal G pasti udah copas dari archive. Solusinya O(V+E) tapi yg di web felix masih O(VE) -> blom diblackmagic punya.
soal L sama kek IOI finland yg judulnya mobile (kayaknya
)
-Kurniady
Kontesnya lebih dari 1 hari kan ? 1 minggu yah kl gak salah ? wajar kl soalnya lebih susah daripada ICPC, ICPC kan dirancang untuk 5 jam
Moga2 loe lolos deh ko ^^
Kalo yg soal B, … tau ngga worst case berapa node yg bakal dihajar di bipartite-matching?
Kalo inputnya mirip kayak chessboard, bukannya bakal bisa ada banyak nodes tuh, 150×150 kira-kira?
Sekedar koreksi minor:
Hitung angka 5 pada X!
Angka 5 = floor(X! / 5) + floor(X! / 25) + floor(X! / 125) + ….
Itu harusnya floor(X / 5) + … (gak pake tanda faktorial lagi).
yg B itu emang parah…. worst node nya bisa ribuan
)
tapi wa hajar aja dah, ga kepikiran cara laen… entah ngebug ga =))
@turuthok : thx. iya yang soal B bisa banyak, 175×175 node
@kur : punya gua ud O(V) kok, toogle nodenya kan
Bah.., punya gw gimana ya nasibnya? wakakaka…
D – F gw hajar DP semua, yang G gw ga tau kalo itu DP Tree,
malah gw DFS doank, salah deee.. :p
Tinggal liat aja besok grading kaya gimana..
moga2 bisa lolos…
@eko
Yang D, meskipun lu dah klarifikasi, tapi coba liat kalimat ini
diikuti oleh M baris masing-masing berisi 3 angka P1, P2, S (0 ≤ P1, P2 ≤ N + 1, 1 ≤ S ≤ 10000) menandakan jarak jalan S dari SPBU P1 ke P2, tapi tidak sebaliknya
Nah loh…, tidak sebaliknya itu loh..
Lu koq tanya panitia bisa jawabannya beda dengan soal?
@wilbert : kenapa dengan itu ? itu cuma bilang edge nya directed, bukan berarti ga ad cycle
nice post, gan!
kapan ini pengumumannya?
@eko
Ups.., iya yah… baru nyadar.. wakakakaka..
Mestinya solusi panitia atau testcase dikasih donk,
kita kan juga pengen tau solusinya..,
dan juga kalo ada jawaban yang kita rasa bener tapi
salah kan bisa klarifikasi..
Yg G: Minimum Vertex Cover on a Tree …
@turuthok : eh? vertex cover tuh nge cover nya edge kan ? ini mirip dominating set, tapi cuma boleh ke cover tepat 1x.
Vertex Cover setau gue, untuk setiap edge, mesti ada minimum satu ujungnya tercover. Minimum Vertex Cover tentunya cari kombinasi yg seminimum mungkin.
Ini jadi kebalikannya Maximum Independent Set. Kalo dapet Maximum Independent Set, bisa dapetin MVC = n – MIS. Demikian sebaliknya.
8 Node
1 2
2 3
2 4
4 5
5 6
6 7
6 8
Kalo min vertex cover nya 3
tp jawaban untuk soal G cuma 2, karena edge 4 5 ga perlu di cover
Eh iya, bener juga ya … mestinya min vertex cover gagal untuk input ini. Jadi termasuk yg mana yg problem ini, … minimum dominating set?
@Eko
Testcase lu bener, MVC nya 3.. Tapi kenapa di OJ pada AC
semua? gw uda coba di Live Archive juga..
Apa soal G ini beda dengan yang di OJ? sama kan?
Mungkin testcase lu perlu ditambahin ke mereka? hahaha…
Karena gue jadi lebih penasaran, jadi mikir lagi, … ini dia algo greedy gue untuk G.
Pertama-tama, proses setiap edge di input. Untuk setiap edge a-b, kita tambahin 1 ke degreenya node a, dan 1 ke degreenya node b. Keep track juga neighbors masing-masing node (pake adj list).
Lalu, kita loop sampe gak ada vertex dengan degree >0.
Untuk tiap iterasi, pasti ada vertex dengan degree == 1 (karena ini tree). Vertex dengan degree == 1 tentunya adalah leaf. Dan akan aman kalo kita ngepilih tetangganya leaf ini untuk dimasukin ke dalam result set kita. Pas kita pilih tetangga leaf ini, maka sekalian kita delete node ini (hilangin semua edges yg terhubung ke node yg kita pilih) … tentunya degree dari tetangga-tetangga si node ini pasti berkurang 1. Selesai iterasi ini.
Jadi mestinya hasil problem G ini = jumlah iterasi yg kita kerjain.
Note: perlu dijelaskan kalo input case cuman ada 1 vertex, jawabannya 0 atau 1 ya?
Bingung yang soal G,……….
Hmmmmmmmmmm yang kemaren testcase lo kasi bener jawabnya 3 ko?
statement yang nyebabin tu pasti 3 yang mana?
wa masi bingung, algo wa ga jauh beda ama turuthok , tapi kalo pake algo itu ans dari testcase mu cuma 2 … ? ? ? ?
@turuthok : hmmm..mirip dominating set (gua jg bingung jd namanya apa), kalo dominating set kan cari set S sehingga semua elemen V-S itu terhubung setidaknya 1x dengan salah satu elemen S, kalo soal ini, cari S seminimal mungkin sehingga setiap elemen V-S terhubung tepat 1x dengan salah satu elemen S. Nah karena ada batasan bahwa ga boleh ada 1 orang yang ke cover 2x, maka akan ada case dimana leaf harus jadi orang yang mengcover.
iya itu greedy buat vertex cover di tree kan.
kalo cm ada 1 vertex jawabannya 1.
@wilbert : hah?? mksdnya apa? test case gua biasa aja kan?
@indra : gua ks test case bkn td pagi ya? yang tadi kan karena ada node yang ga boleh ke cover 2x. case ini kan?
8
1 2
2 3
2 4
2 7
4 5
5 6
5 8
nah jawabannya adalah 3, yaitu, {2,4,5}
kalo vertex cover kan jadi 2, yaitu {2,5} tapi ga boleh, karena untuk soal ini, node 4 akan ke cover 2x.
@Eko
Sepertinya soal yang di OJ dengan soal G ini
agak sedikit berbeda, jadi jawabannya juga beda..
Coz gw coding Maximum Independent Set untuk
dapetin Minimum Vertex Cover nya AC koq di Live Archive..
Okay, beralih ke algonya Ko Lego,
Greedy Degree Count yah itu?
Apa bedanya?sama ah.
“A set of servers in the network forms a perfect service if every client (non-server) is served by exactly one server. The problem is to find a minimum number of servers which forms a perfect service, and we call this number perfect service number.”
iya nih, pake vertex cover bisa AC di live archieve, ah test casenya butut kali nih >.<
Ini nih yang gw bingung.. Masa testcase Live Archive butut?
Kan itu sama persis sama soal regionalnya.., testcase
pasti ambil dari situ juga..
Hahaha.., ayo ayo, yang bener yang mana neh..
wakakakaka…
Supaya lebih meyakinkan, coba lu submit
di PKU juga.. hoahahahaha…
@wilbert : ya di PKU jg sama, mungkin pake test case pas regional nih. test case regional kan kadang2 ada yang butut
Wah, masa sih soal crucial kaya gini bisa testcasenya butut?
wakakakaka…
Btw, panitia ga ngurusin biaya apapun nih, kita pake
biaya sendiri? termasuk penginapan dsb?
[...] yang mirip di berbagai OJ, silahkan main2 ke postingan blog nya si marcadian AKA Eko Wibowo di sini Di blog dia juga ada pembahasan singkat beberapa [...]
Kalau mau lihat pembahasan beberapa soal ada di
http://evangozali.wordpress.com/2009/03/22/solusi-5-soal-penyisihan-arkavidia/
Thanks evan…