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.
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.
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.
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;
}
IOI 95 – Word Chains Januari 4, 2009
Posted by marcadian in Algo & Math.Tags: Trie
1 comment so far
UVA 11488 – Hyper Prefix Sets Januari 4, 2009
Posted by marcadian in Algo & Math.Tags: Trie
add a comment
Another trie
soal pertama di OJ yg AC pake trie, ini ga pake pointer2an cuma pake array
UVA 11539 – Another Word Game Januari 4, 2009
Posted by marcadian in Algo & Math.Tags: Dynamic Programming, Trie
add a comment
Ok mari mulai ngepost source code kyk orang China, tp gua cm post yg menarik aja, ga bakal ada source code hello world sini
Karena baca di forum pada kena TLE untuk soal ini, jadi kali ini trienya pake pointer
Convert Class November 6, 2007
Posted by marcadian in Development.add a comment
Bedanya adalah, kalo pake typecasting biasa seperti (int) a, maka akan dilakukan checking pada saat compile time, kalo dengan Convert, konversi dilakukan saat runtime, Tapi untuk berbagai kebutuhan kita memerlukan konversi saat runtime, misalnya untuk mengubah string “123″ menjadi angka (integer) 123, cukup dengan Convert.ToInt32(namaString)
akan ada 3 kondisi yg terjadi jika menggunakan Convert class.
1. Tipe data yang akan di convert dan tipe data tujuan adalah sama, tidak ada konversi yang terjadi
2. Tipe data berbeda, tapi tidak memungkinkan terjadi konversi misal string “abc” tidak bisa di convert ke int32 maka akan terjadi exception(System.FormatException, overflowexception,dll tergantung method convert yang dipakai) untuk menghindari runtime error, sebaiknya gunakan convert di dalam try statement kecuali sudah yakin bahwa konversi pasti berhasil
3. tipe data berbeda dan bisa di konversi, maka akan di konversi.
Data Connection November 2, 2007
Posted by marcadian in Development.add a comment
pembahasan menggunakan c# dan sqlserver. Untuk akses database di .net ada 1 metode, pertama yaitu dengan DataAdapter dan DataSet untuk connectionless oriented, maksudnya yaitu kita “menyalin” dulu database yang kita gunakan ke dalam dataset, sehingga koneksi ke database tidak berlangsung terus menerus, keuntungannya jelas mengurangi traffic network. Model kedua yaitu connection oriented, dimana koneksi dilakukan terus menerus, dengan menggunakan sqldatareader(jika menggunakan sql server) ato oledatareader(utk database lain mis access).
Untuk akses dengan DataAdapter yg penting adalah kita udah set insert command, update command, select command, delete command, masing2 utk insert,update, select dan delete ke database, kalo cm mau buat liat datanya, cukup set insertnya aja, trus jg perlu manggil method fill, nah method ini bakal jalanin otomatis select command kita lalu ngisi ke dataset kita (Dataset anggep aja mirror database di local kita, bs mengandung table, relationship, constraint,dll)
cthnya gni ( ga di compile, jd mungkin error2 dikit ky masalah huruf besar/kecil, tp kalo pk intellisense ga masalah seh)
private string constring = .... ;//isi connection string
private dataset ds;
public void akses()
{
DataAdapter da = new DataAdapter();
using (sqlconnection con = new sqlconnection(constring) )
{
private sqlcommand cmd= new sqlcommand();
cmd.commandtext = "" // query sql ato nama storedprocedure jika menggunakan storedprocedure
cmd.commandtype = sqlcommandtype."..."
/*defaultnya adl query sql langsung, bs diubah jd stored procedure(recomended) */
cmd.connection = con; //sql connection yang dipake
/*
kalo storedprocedurenya ada parameters, cmd.parameters.add("paramName","paramtype");
cmd.parameters["paramName"].value = MyValue;
paramName nya persis sama ky di storedProcedure yg dibuat,mis "@id"
commandtext ma connection bs langsung diisi pas buat objek private sqlcommand cmd= new sqlcommand("commandText",connection);
*/
da.selectcommand = cmd;
da.fill(ds,"MyTable"); //MyTable adl nama table di dalam dataset kita, kalo ga diisi bakal jd table0,table1,dst
}
}
nah dengan gtu aja kita ud bs akses database kita, utk akses MyTable dari dataset, kita pake
da.Tables["MyTable"] << ini bertipe DataTable bs di return ato dimanipulasi lebih lanjut
nah kalo untuk pake datareader
public void akses()
{
using (sqlconnection con = new sqlconnection(constring) )
{
sqlcommand cmd= new sqlcommand();
sqldatareader reader = new sqldatareader();
cmd.commandtext = "" /* query sql ato nama storedprocedure jika menggunakan storedprocedure */
cmd.commandtype = sqlcommandtype."..." // defaultnya adl query sql langsung, bs diubah jd stored procedure(recomended)
cmd.connection = con; /*sql connection yang dipake */
/*
kalo storedprocedurenya ada parameters, cmd.parameters.add("paramName","paramtype");
cmd.parameters["paramName"].value = MyValue;
paramName nya persis sama ky di storedProcedure yg dibuat,mis "@id"
commandtext dan connection bs langsung diisi pas buat objek private
sqlcommand cmd= new sqlcommand("commandText",connection);
*/
con.open();
reader = cmd.executereader();
while (reader.read())
{
/*
utk akses colom pertama bs dengan
reader[0] ato reader["FirstKolom"], yg pake angka langsung lbh cepet, bs jg cara laen (nanti aj)
"FirstKolom" itu nama kolom / field yg lo buat, jangan lupa datanya harus di convert ke tipe data yang bener
misalnya utk ke int32: int x = Convert.toint32(reader[0]) tapi kalo cm mau ditampilin langsung aja pake .ToString()
*/
}
reader.close();
con.close();
}
}
nah kalo kita buka koneksi dengan con.open() jangan lupa ditutup, kalo males buka tutup, langsung aja executereader, tar otomatis dibuka dan ditutup koneksinya, tp inget kalo udah kita buka, panggil executereader trus ga ditutup, koneksinya ga otomatis ditutup
sebenernya sqlcommand ada 3 macem eksekusi
yaitu executereader << return datareader
executescalar << return 1 nilai di baris 1 kolom 1
executenonquery << yg ini untuk query yang ga ad returnnya, spt untuk insert update,delete, nah method ini return brp banyak data yg terkena efek query. nah tapi kalo pake select hasilnya PASTI -1,
trus mending pake datareader ato dataadapter ?? dari buku yang gua baca mending kalo bs datareader pakelah datareader, knp?lupa tar kalo inget baru gua cari
kayaknya seh gara2 kalo dataset itu makan memory, jd kalo ga butuh ya jangan