Final Programming Contest Gemastik 2009 Oktober 10, 2009
Posted by marcadian in Event, Programming.Tags: gemastik
18 comments
Day 1
Terjadi perubahan rencana mendadak pagi2, yang tadinya kumpul di kampus syahdan tiba2 pindah ke kijang, gara2 bus cipaganti diusir protecom >.< langsung menghubungi semuanya buat langsung ke kijang, yang udah dateng langsung berangkat naek angkot.
Perjalanan lancar, ampe sana ternyata wismanya better lah dari yang taon lalu punya. sekamar gua 4 orang dengan tempat yg lebih gede daripada taon lalu. Abis urusan regis2, langsung kabur bentar cari buku trus pas balik pas ud akhir briefing, ambil nomor urut buat komputer, yes i got lucky 7 
dan tim solitude dapet no 13, lucky 7 vs number 13 >:)
Gua buka penampungan cw di kamar gua mpe malem
Kali ini bajunya mirip ma pegawai hotel, dan yang paling kacau adalah pendek banget, padahal gua ud ambil ukuran L yang paling gede, udah pendek, ada belahannya lagi, mantap. Si Jep mesum dah berencana “kipas2″
Penyisihan programming contest gemastik 2009 Agustus 27, 2009
Posted by marcadian in Event, Programming, Story.4 comments
Hmm… baru saja kelar beberapa jam lalu. Tambah ancur aj nih kontes, penyisihan ke-2 taon lalu masih jauh lebih bagus daripada ini.
memasuki tahun terakhir Agustus 25, 2009
Posted by marcadian in Uncategorized.add a comment
Udah lama enggak update blog. Bentar lagi masuk semester 7, yang semoga menjadi semester terakhir kuliah (tp mpe sekarang lom dpt topik skripsi nih). Tahun ke-3 (smst 5 dan 6) adalah semester plg jahanam menurut gua, terutama semester 6 
banyak kerjaan, beberapa gj dan makan waktu.
(lagi…)
Malaikat di Bros (101 Cara Menggunakan Barometer) Mei 2, 2009
Posted by marcadian in Nice Stuff.4 comments
Cerita bagus yang gua baca waktu ke Sweden dari Chicken Soup.
(lagi…)
World Final ACM ICPC 2009, Stockholm April 30, 2009
Posted by marcadian in Event, Programming, Story.17 comments
Day 0-1
Perjalanan Jakarta – Bangkok cukup lancar dan berasa cepet, ampe bangkok, waktunya bengong 9 jam, mantap. Setelah muter2 bandaranya, yang arsitekturnya cukup keren, tapi ga gtu banyak tempat makanan akhirnya nongkrong di starbucks bentar, trus menemukan tempat yang nyaman, bisa tidur bentar disini. Abis itu cari tempat makan di bandara, isinya makanan macem2, cita rasa thailand dah gua sendiri makan tom yam. Pas masuk ruang tunggu, ketemu tim NUS ma NTU, tim NTU cm transit disini sekitar 2 jam, wew kenapa gua 9 jam ==”
Pas lagi nunggu, ketemu beberapa orang asia bermuka geek, wah kayaknya tim ICPC juga nih, dan ternyata mereka dari NTU Taiwan.
Penerbangan dari bangkok – stockholm makan waktu 12 jam, sepertinya cukup membosankan. Di samping gua duduk seorang cw (hmm… cw bener bkn ya? serem kl shemale, cuekin aj ah) pas naek langsung pk selimut, molor, malah sempet selimut ampe nutup muka, cw stres ==”. Abis makan, langsung tdr, bangun2 dah pagi, ga lama makan lagi. Bis itu nanya2 cw sebelah dari mana, oh dr filipina, kemungkinan besar beneran cw berarti.
Turun dari pesawat, wow tambah dingin, ah tenang masih kuat. Abis urus imigrasi, ketemu orang dari panitianya, eh ternyata maksudnya mereka ingin ada di bandara saat tim nyampe itu, ya benar2 gtu, bukan berarti mereka jemput 
Keluar bandara buat naek taksi, woo mantap suhunya, bisa bikin merinding disko. Dari bandara Arlanda, naek taksi ke stockholm, taksinya fixed rate, 495 kr (1kr sekitar 1200 rupiah), ok mantap taksinya (selaen mahalnya) volvo! dan melaju dengan kecepatan > 100km / jam pernah ampe 150an konstan, mantap ini baru namanya taksi. Sekitar 1/2 jam nyampe grand hotel, check in. Abis itu mau makan, dan muter2 jalan2 cari makanan, wew kotanya bagus, banyak airnya, stockholm terpecah ma perariran. Baru jalan sekitar 10 menit, menyerah dengan suhu udaranya, dan kembali ke kamar buat tambah armor. Jalan ga lama, gunawan berasa ketombenya rontok lol ternyata bukan, salju jatuh dikit, untung ga banyak. Abis jalan susah juga nemu tempat makan, karena banyak gedung2 tanpa nama, akhirnya ketemu 7 eleven dan makan disana, gua menghabiskan 59 kr.Mirhard ma pak fredy membeli sebotol air mineral, seharga 33kr, ternyata itu air soda, met menikmati. Abis itu pulang, nunggu bentar trus urus registrasi dll lalu makan malam, abis itu ketemu pak sablin bentar, trus keluar hotel dengan tanpa persiapan hanya untuk foto, suhunya lbh mantap dr tadi siang ==” abis itu balik ke kamar, tidur. Kata pak sablin, lewat jam 12 malam, ada channel2 “nakal” >:) tapi sialnya gua selalu terkapar sebelum jam 12.
Arkavidia April 6, 2009
Posted by marcadian in Event, Story.9 comments
Arkavidia
Day 0 Decision…
Ok, dikarenakan terjadi suatu kesalahan teknis oleh panitia yang tidak memberitahu jadwal acara, padahal dari hari rabu sebelumnya dah gua email, dan sodara flashit bilang kalo software disuruh ikut expo tanggal 2, maka semuanya berangkat bareng tanggal 1. Setelah milih hotel, booking, 15 menit kemudian ad email dari panitianya, software mulai tanggal 3, nice cengo dulu ampe tanggal 4 gua.
what a wonderful day! Maret 26, 2009
Posted by marcadian in Story.3 comments
Yak hari ini bagus sekali, semalam berusaha tidur 2.30 pagi, dan dibangunkan 4.30, meski sadar2 ya jam 4.45. Ngapain bangun pagi disaat libur? padahal ga libur aja bangunnya siang Hari ini pergi ke kuburan kakek gua, kenapa? (karena ini hari nyepi!) karena hari ini mulai maa cheng beng (gmana nulisnya ya?).
Nah abis dari sana, pada mau ke kebun durian http://www.warsofarm.com/ ya akhirnya gua terculik ikut karena ga bisa pulang, pada kesana semua. Sialnya karena gua ga suka duren, ini cuma bikin capee. Berangkat dari kuburan gunung sindur ke sana butuh waktu sekitar 4 jam, udah +makan di jalan. Jalan2 yang dilewatin banyak yang macet, jalanannya kecil pula. Ampe disana, ngeliat2 bentar kebunnya, ok mayan banyak abis itu pada makan duren, karena gua ga suka, ya ga makan. Bicara tentang duren, gua jadi inget waktu ujian bahasa indonesia, kalo ga salah pas SD ato SMP d. Ada keluar soal tentang perumpamaan, kalo ga salah pertanyaannya adalah, manakah yang bukan berarti mendapat keuntungan or something like that lah. tinggal 2 option yang bikin bingung, salah satunya adalah “Bagai mendapat durian runtuh”. Ok, gua orangnya logis, perumpamaan itu dibuat pasti dengan metafora tertentu, jadi cukup dibayangkan kejadiannya. Nah, ini dia sumber masalahnya,inferensi gua mengatakan
Fakta 1 : durian itu tajam
Fakta 2 : saya tidak suka durian
Hasil : Mendapat durian runtuh adalah mendapat sesuatu yang ga baik!!
Yak saya pilih dengan yakin!! dan ternyata salah..>.< ternyata mendapat durian runtuh adalah mendapat keberuntungan, loh gimana bisa?? coba d, “ada orang yang mau keruntuhan durian?” gua sih jelas ga mau, soalnya tajem2, kalo kena dijamin lecet2 kalo “ada ga orang yang mau beruntung?”, semua orang pasti mau!!bodoh nih, sapa sih yang buat nih perumpamaan??
Ok lanjut, abis dari situ, pas jalan keluar macet panjang aj, jalanan sempit, dan 2 arah, good… Abis itu lewat kota bogor, pada mau beli asinan, macet aja, jalanan 3 jalur, 1 arah, damn! Pas sampe udah mendung banget mau hujan, yak pas disini ketemu anak binus yang gua kenal (gila dunia sempit aje). ga lama abis kelar belanja disitu, hujan deras banget, di tengah jalan tol baru reda dikit. Akhirnya gua sempet tertidur sebentar, pas sampe ud keluar tol di jakarta, kyknya paling lama tuh cm 1 jam. Pas sampe tempat sodara hujan mayan deras, pas turun mobil gua basah dikit. Nah disana bentar trus pulang ke rumah, sampe sekitar jam 7 malam!! Bener2 nih, cape doank, mending gua ga ikut >.<
Penyisihan Arkavidia Maret 17, 2009
Posted by marcadian in Event, Programming.30 comments
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.
Akademis busuk… Januari 20, 2009
Posted by marcadian in Story.23 comments
Ok, hari ini sangat busuk.
Hari jumat lalu, dosen grafkom ga masuk karena sakit, di tempelan tertulis, kuliah pengganti hari selasa tgl 20 januari jam 3 sore ampe 7 malem.
Hari senin kuliah sistem operasi, sang dosen katanya disuruh akademis untuk mengadakan kuliah pengganti hari selasa tgl 20 januari, dari shift 3 ampe 6, begitu dibilang ada grafkom, tuh dosen bilang, akademis kasihnya jam segtu.
Hari ini, pas mulai KP sisop, si dosen bilang, dia dikasih akademis shift 3 – 6, dan yang grafkom itu dikasih shift 6 – 7.
Pas ke akademis tanya,
Mr x : wah mestinya mahasiswanya bilang ke dosennya, mestinya ga bisa itu
mhs : loh pak, ud bilang, katanya dikasih dari akademis itu jadwalnya
Mr x : wah ya mestinya ga bisa, yang booking duluan dapet duluan
mhs (tepatnya gua) : loh ini kok bisa pak? jadi kuliahnya gmana ?
Mr x : ya yang booking duluan sapa bla bla bla
OK, dasar tolol cape berdebat, tinggalin aja, jelas2 mereka yang atur jadwalnya. >.<
Yang menyetujui booking mereka, masa bisa dalam 1 shift, kuliah di 2 tempat? Kalo ud ada jadwal laen ya bookingnya ditolak donk, pindahin ke hari laen. Akhirnya td shift 6 dosen sisop ngalah dan mayoritas kelasnya kuliah grafkom.
Akhirnya hari ini kuliah dari jam 11 siang ampe jam 9 malem!! *jam 1/2 9 ud pulang karena kuliah shift 6 – 7 ga ad istirahat*
Setau gua (dari informasi waktu POM), mahasiswa reguler itu jadwal kuliahnya dari jam 7 pagi ampe 7 malam, dan mahasiswa malam kuliahnya dari jam 3 ampe jam 9.
Note buat yg ga tau:
Shift 1 : 7.00 – 9.00
Shift 2 : 9.20 – 11.00
Shift 3 : 11.20 – 13.00
Shift 4 : 13.20 – 15.00
Shift 5 : 15.20 – 17.00
Shift 6 : 17.20 – 19.00
Shift 7 : 19.20 – 21.00
Semalam hanya tdr 5 jam, dari jam 5 pagi ampe jam 10an (maklum jam tdr eropa, waktu GMT , tinggalnya di daerah GMT +7) dan hari ini kuliah 10jam, mantap.
ZJU 3077 – Move to baggage office Januari 9, 2009
Posted by marcadian in Algo & Math.Tags: Dynamic Programming
add a comment
Problem. This is a modified knapsack problem. One thing should remember that in real knapsack problem, the order of items doesn’t matter, but in this problem it does.
Here is sample case:
S = 10
v1 10 9
v2 3 1
If the order like this then you can take both item, but if the order is the reverse you just can take one item. 10 – 3 + 1 < 10. So, what is the best order so that if we take item in that order, we are not lose other items ?
Lemma : Order by B value (input is v a b) descending is optimal ordering.
For example we have 2 items.
v1 a b1
v2 c b2
Where b1 > b2
Proof : Assume that this order is not optimal, then there is strength value, X where
X – a + b1 < c and X – c + b2 >= a
X + b1 < a+c and X + b2 >= a + c, combine both equation, we have
X + b1 < a + c <= X + b2 , Substract with X
b1 < a + c – X <= b2
b1 < … <= b2, we conclude that b1 < b2 which contradict our assumption, therefore the order by decreasing of B value, is optimal. Here is the code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef struct
{
int v,a,b;
}item;
bool operator<(item a,item b) { return a.b > b.b; }
int main()
{
int s,t,n,b,v,a;
item items[101];
int best[1001];
scanf("%d",&t);
while (t--)
{
scanf("%d %d",&s,&n);
for(int i=1;i<=n;i++)
scanf("%d %d %d",&items[i].v,&items[i].a,&items[i].b);
memset(best,-1,sizeof(best));
sort(items+1,items+1+n);
best[s] = 0;
for(int i=1;i<=n;i++)
{
a = items[i].a;
v = items[i].v;
b = items[i].b;
for(int j=0;j<=s+b-a;j++)
{
int temp = j + a - b;
if (temp >= a && best[temp]!=-1)
best[j] = max(best[temp] + v, best[j]);
}
}
printf("%d\n",*max_element(best,best+1+s));
}
return 0;
}
