Behind the scene INC 2011

Tahun ini gua berpartisipasi dalam INC 2011, bukan sebagai peserta lagi, tapi sebagai judge/problem setter.

Karena ketua juri lagi di negeri seberang, mengaku menutut ilmu, gua kebagian in charge untuk babak penyisihan. Juri sedikit kewalahan untuk babak penyisihan dikarenakan banyaknya submission. Buat yang belom tau, cara judging saat penyisihan itu. Peserta submit lewat web, “submitter” download dari web, submit ke pc2, juri judge pake pc2 makanya lama, soalnya jumlah kliknya banyak banget sebelom ampe ke tempat juri, perlu disubmit oleh submitter. Submitter untuk babak penyisihan sendiri sekitar 10 orang, dan juri, cukup sekitar 4 orang karena judging dengan pc2 sangat cepat.

H-2 Menjelang Final

Hari senin sehabis penyisihan, gua memutuskan mudik ke kampung di pulau seberang karena tidak tahan dengan kerasnya kehidupan Ibukota Jakarta dan gua baru kembali ke Jakarta jumat malam. Ketika online di YM, bos juri yang rese minta gua ke binus buat test time limit, geez. Gua juga males kalo mesti sore ke binus, su beralasan ga bisa ke binus untuk ngetes karena lab software dipake pada saat siang hari, dan sore hari dia mo pergi.  Gua langsung kontak panitia di binus melalui email, kasih tau kalo besok mau ngecek time limit, dan langsung tidur karena masih cape.

H-1

Bangun pagi dan ga ada balesan atas email gua. Akhirnya berinisiatif menculik winardi untuk ngomong ke SiapapunDiLab agar diijinkan masuk. Ketika gua, winardi dan albet jalan ke Binus, tampak seseorang yang “Katanya Ga Bisa Ke Binus Karena Mau Pergi” sedang menyebrang jalan -.-  *hiaattttt keluarin tendangan tanpa bayangan

Final

Gua dateng pagi ke binus, sedikit terheran kenapa macet. Ternyata di binus sedang ada beberapa acara lain di samping INC. Parkiran motor yang biasanya gratis kalo hari minggu ga ad acara, hari ini mesti bayar sesuai tarif hari biasa. Untung saya masih punya kartu mahasiswa, jadi cukup 1000 / hari

Dateng ke ruang juri, gua mulai bagiin soal untuk practice session karena lom ada lagi yang bisa dilakukan saat ini. Sekalian foto foto sedikit, hari ini saya bertekad jadi tukang poto aja  :-) Kelar bagiin soal practice, terdengar kabar bahwa soal ketinggalan di ruang jurusan di syahdan dan lagi diambil ama Muhsin. Beberapa menit kemudian terdengar kabar, pintu jurusan ga bisa dibuka karena ga ada orang, dan building management (BM) syahdan lagi enggak ada *jeger*. Gua ikut Su yang udah mau ngeprint semua soal lagi, ampe basement Su coba ke BM anggrek dan ternyata lagi dikunci, orangnya keluar semua. Untungnya bisa ditelp dan katanya pintu jurusan udah berhasil dibuka *fiuh*

*terima kasih kepada saudara Muhsin atas perjuangannya, kontes ini tak akan berlangsung tanpa engkau..

Kembali ke lantai 8 dan mulai technical briefing, ngomongin macem macem tentang kontesnya dari sisi teknis. Disini gua sempet jadi pajangan di depan, enggak jelas buat apa -.- Kelar briefing langsung ke ruangan peserta untuk cek tim notebook. Cuma ada 1 tim yang notebooknya bermasalah, dan yang gua ga expect, itu tim binus >.<

Practice session dimulai, gua ga ikutan judging ama sekali. Gua mondar mandir di ruang peserta, liat liat ada yang bermasalah ato enggak, ngobrol ngobrol dikit sama tim yang kenal, jawabin pertanyaan peserta, dll. Ada yang tanya, kok applet javanya ga keluar? *bingung* karena ini mestinya bagian sistem, karena saya baik hati, saya coba jawab. tapi ternyata solusi gua ga membantu LOL **kabur**. Sampai ke salah satu ruangan, ga ada pertanyaan, ketika gua udah mau pindah ke ruang laen, SiBajuIjoAnehDanTidakGanteng angkat tangan mau tanya, sebelom dia keluarin pertanyaan, gua kacangin kabur ke ruang sebelah

Countdown final kontes mulai berjalan, gua masih mondar mandir di ruang peserta. Kira kira tinggal 5 menit, su masuk ruangan, kontes dipending ada masalah. Ternyata, server pc^2 crash **jeger** padahal lom dipake sama sekali, baru upload testcase dan login juri. Kesalahan ditimpakan kepada testcase problem setter yang sinting, total input output untuk semua soal mencapai 50mb (karena ukuran output file yang besar, *salah satunya soal gua, apa cuma soal gua ya?*, maka diputuskan pake pc^2 9.2 beta yang bisa atur output limit) dan juga ukuran RAM pada server yang hanya 2gb (desktop gua aja 4gb).

Setelah berhasil direstart dan tambah max memory untuk jvm,  semua peserta diminta login ke sistem, hasilnya memory jvm bengkak jadi 1.2 gb, padahal udah di set maximum 1.5gb. Juri yakin, akan matot lagi ini pc^2 kalo dipake. Surya cek memory dan server, gua mikir kenapa ini terjadi, dan suhendry ngomel ngomel. Akhirnya diputuskan, deploy 1 pc^2 lagi untuk judging soal yang input nya gede yaitu A,C,D,E. Ketika gua selesai deploy 1 pc^2 lagi (sebut server 2) dan suhendry udah beresin di server 1, kontes langsung start karena udah molor cukup lama dari jadwal. Jadi, untuk soal A,C,D,E yang disubmit peserta ke server 1, akan di re-submit ke server 2 baru di judge **ini termasuk distributed computing ga ya? :p* *

kanan : server 2 dengan task manager untuk memantau memory JVM| kiri : judge server 1 dan judge server 2

Akhirnya kontes bisa berjalan. Kontes kali ini berjalan cukup pelan, rasanya total submission ratenya ga sampe 2 / menit. Biasanya juri diserbu saat awal dengan submission untuk soal easy / bonus, tapi kali ini submission tetep lambat. Juri udah bosen, suhendry udah tidur, ada yang maen maen, ada yang browsing, ngobrol ngobrol. dan gua kembali ke ruang peserta moto – moto

Tim dongskar attack soal E di saat awal, padahal ini bukan soal yang mudah. Hal ini sepertinya membuat beberapa tim laen mengikuti jejaknya -.-

Pelajaran hari ini : ga semua tim perlu diikutin, terutama yang ga waras macam ini

Pertandingan cukup sadis ketika rank 1 udah solve 6, padahal rank 2 baru solve 3, 2x lipat. Gimana tim tuan rumah? Tim no 1 tuan rumah sempat terdepak ke posisi 4. Saat di posisi 4, bos lab computing udah stres, dia masuk ruangan juri dan bilang “mati dah, dicincang gua”. Untungnya mereka mengamuk di saat freeze, langsung accepted 3 soal awesome guys!!

tarian kemenangan dari artis jurusan

Ditengah pertandingan yang berjalan lambat, Su kembali tidur, di berbagai tempat dan dengan berbagai gaya.

submission ga di judge

pindah tempat dan ganti gaya

Gua berusaha motoin semua tim yang sedang bertanding. Tapi apa daya beberapa tim berada di tempat yang susah untuk difoto karena terlalu jauh dan gua ga mau ganggu peserta lain cuma karena untuk foto. Jadi yang fotonya ga ada di album, sori anda berada di posisi yang kurang baik.

Di akhir pertandingan, peserta mem-”bom” juri dengan submission. Beberapa submission sih tergolong spam. Ada tim yang ngespam dengan submit 1 source code ke semua soal. Beberapa submission pertama sih gua run, berikutnya cuma view source, langsung reply Wrong answer >:)

spammer!

Btw gua penasaran, butuh berapa menit untuk bikin pattern diatas?

Random Facts

• Balon bewarna biru tua cuma ada 1 buah, di assign ke soal paling susah, untung ga ada yang solve

Balon keramat yang cuma ada 1 

•  Solusi soal E awalnya dibuat 1/2 oleh Suhendry, dan 1/2 lagi oleh gua Tepatnya gua buat bagian suffix arraynya, sisanya Su yang beresin. Gua ga tau dia buat apa, dan dia ga tau gua buat apa. This is what we called teamwork *high five Su*
• Ada panitia yang komplain ke gua, katanya SiBajuIjoAnehDanTidakGanteng nyolot waktu dikasih tau. LOL

Anyway, congratz buat yang menang dan buat yang lom menang, selamat berlatih dan coba lagi taon depan.

Foto – Foto

Final Ranklist

Feedback Penyisihan INC 2011

belasan juri dan submitter,  ratusan submission, ribuan klik, diiringi oleh cucuran keringat para juri yang kepanasan, akhirnya kontes selesai….

Hari ini berlangsung penyisihan INC 2011. Ini pertandingan paling panas yang pernah saya liat, juri sampat berkeringat dikarenakan oleh AC yang enggak bener

Tulisan ini saya buat untuk menghilangkan kebingungan peserta (terutama yang baru ikut serta pada kontes pemrograman) terhadap hasil penilaian juri. Banyak peserta mendapatkan run time error dan compile error yang seharusnya bisa dihindari dengan mudah.

Dari banyak submission oleh peserta, banyak yang melakukan kesalahan kesalahan, bahkan beberapa melakukan kesalahan yang telah ditulis di halaman depan web competition (saat akan login), hayoo pada ga baca ya? :p  Biar enggak penasaran, saya akan bahas kesalahan kesalahan yang saya temukan saat pertandingan. Tentu saja saya enggak membaca submission semuanya, hanya kebetulan beberapa yang ketemu aja.

• C++: gunakan int main(), bukan void main(), perhatikan compiler yang digunakan.
  Compiler yang digunakan adalah mingw (g++) dan tidak menggunakan gcc bahkan untuk file dengan  berextension .c. Jika menggunakan extension file .c dan menggunakan void main akan mendapat compile error. Lucunya, jika keyword “void” dibuang sehingga fungsi utama hanya main() (tanpa tipe kembalian), tidak akan menyebabkan compile error
• Java: jangan menggunakan package, perhatikan command run di bawah.
  Program dicompile secara otomatis dari current directory dan langsung dieksekusi sesuai perintah yang telah disebutkan. jika menggunakan package akan menyebabkan error, karena file diharapkan berada dalam struktur folder
• (C/C++) Penggunaan getch()
  getch() yang digunakan di akhir program bisa menyebabkan program tidak berhenti (masih menunggu input dari keyboard), akibatnya program bisa mendapat Time Limit Exceed.
• (Java) Penggunaan GUI (JPanel, dsb)
  Program harus membaca input dari standard input (stdin) dan mengoutput ke standard output (stdout) yang keduanya ada di console (bukan GUI). Penggunaan GUI bisa menyebabkan program tersebut Time Limit Exceed (juri tidak memberikan input ke GUI yang ditampilkan sehingga program terus menunggu).
• Penggunaan format string %lld pada integer 64-bit
  Format string yang digunakan untuk tipe data long long atau __int64 (integer 64-bit) di DevC++ adalah %I64d, bukan %lld (DJGPP).

  int main()
   {
   __int64 x;
   scanf( "%I64d", &x );
   printf( "%I64d", x );
   return 0;
   }

  Kesalahan ini tidak menyebabkan program tidak bisa dikompile, namun output yang dicetak oleh program akan tidak sesuai dengan apa yang diinginkan (integer 64 bit).

• Runtime error pada beberapa program Java
  Hari ini gua nemu beberapa runtime error pada program java, ada yang sampai menelepon mempertanyakan hal ini, padahal di komputernya baik baik saja, kenapa mendapat hasil run time error. Setelah dilakukan penelitian asal asalan yang tidak komprehensif, ditemukan bahwa peserta melakukan beberapa kesalahan seperti :

• menggunakan fungsi dari class Scanner, yaitu nextInt() padahal dalam inputan disebutkan bahwa inputan dapat mencapai bilangan 64bit, ketika membaca angka yang sangat besar (misal 1000000000000), akan menyebabkan exception.
• membaca line yang tidak ada
  Salah satu source code peserta yang saya temukan, menggunakan perintah seperti ini

  if (scan.nextLine()!="")

  yang mungkin dimaksudkan untuk mengecek apakah inputan sudah habis, namun ini akan berakibat fatal, yaitu ketika sudah sampai line terakhir dan memanggil perintah diatas, akan menyebabkan runtime error. Solusi yang benar adalah menggunakan fungsi seperti hasNextLine, hasNext, hasNextInt, dsb untuk mengecek apakah masih ada inputan

• Konstanta terlalu besar untuk suatu tipe data
  Saya menemukan ada yang mengassign tipe data long long pada C++ seperti ini long long x=1000000000000;  Akan mengakibatkan error konstanta terlalu besar, solusinya adalah dengan menambahkan LL di akhir, 1000000000000LL. Jika tidak ditambahkan LL maka akan dianggap sebagai int, karena itu compiler akan mengembalikan pesan error
• Array index out of bound (c/c++,java)
  kesalahan klasik, mendeklarasikan 100 elemen pada array, namun mengakses elemen di luar indeks 0..99
• Memanggil fungsi tanpa meng-include header
  Menggunakan fungsi tanpa include header yang tepat, misalnya abs tanpa include stdlib.h. Mungkin peserta menggunakan IDE semacam dev-C++ yang terkadang agak “bego”. Sebagai contoh hanya menginclude iostream dan menggunakan fungsi abs tidak akan menyebabkan compile error jika compile dilakukan dari dalam IDE Dev-C++ namun jika dilakukan dari command line akan menyebabkan compilation error. Rule of thumb : jika bisa dicompile dari cmd, akan bisa dicompile di tempat juri, karena begitulah cara juri melakukan compilation
• Mengakses variable di luar scope
  Saya menemukan ada peserta yang melakukan hal semacam ini

  for(int j =0;j<n;j++) {
  .....
  }
  if (j .... ) {}
   

  pada code diatas, variable j hanya di deklarasikan dalam scope for, namun diakses di luar for. Compiler c/c++ yang benar akan memberikan compile error untuk kasus seperti ini. Namun sepengetahuan saya, pada compiler visual c++ 6.0 kode diatas adalah legal. Pada visual c++ 6.0 jika dibuat satu lagi block for dan deklarasi variable j di scope for, justru akan memberikan compile error. Dulu saya memakai visual c++ 6.0, ketika submit ke UVA online judge mendapat compile error terus menerus. Setelah mengetahui penyebabnya, saya langsung ganti compiler dan kurang tau lagi dengan visual c++ versi .net

Dari banyak kesalahan yang terjadi pada pengguna bahasa C/C++, kebanyakan disebabkan oleh compiler aneh yang digunakan yang bahasanya tidak standard, seperti borland C++ dengan void main, dan visual C++ 6.0 dengan scoping anehnya. Untuk kontes seperti ini saya sarankan menggunakan compiler mingw. IDE yang dapat digunakan misalnya Dev-C++ atau Code blocks. dev-C++ sudah lama terhenti developmentnya sehingga compiler yang disertakan sudah obsolete yaitu gcc versi 3. Namun bisa saja menggunakan dev-C++ dengan mingw versi terbaru.

Demikian kesalahan yang saya temukan pada kontes kali ini, kalo ada yang ga jelas, feel free to ask Semoga apa yang saya tulis diatas bisa menghilangkan rasa penasaran kenapa dapet compile error / run time error. Dan juga mencegah peserta maki maki juri karena juri dianggep ga jelas (cth makian : wah ditempat saya jalan, kok submit error, juri brengsek!).

Buat peserta yang baru pertama kali ikut dan belum berhasil, silahkan berlatih dan mencoba lagi tahun depan Goodluck buat yang ke final, sampai ketemu!.

Note : kalo ada yang mau complain soalnya susah susah, silahkan hubungin saudara Suhendry Effendy, selaku orang yang bertanggung jawab.

INC 2010

INC pertama sebagai pensiunan, kali ini gua cuma review soal, beberapa alternate solution, nonton dan tulis – tulis (maki maki) di status YM. Nonton ranklist kali ini mayan seru di awal – awal, tapi dah kira – kira 3 jam, hampir gua tinggal tidur, ranklist mulai statis papan atas tak bergerak! Status YM : “benar benar No Hope” gara – gara tim binus di rank 6.

Nyaris sepanjang kontes gua ngobrol ma Hendri, mulai dari chit chat soal, pasang – pasang status ga jelas. Pas Dongskar di rank 3 dan waktu udah mo abis, si Hendri sempet pasang “Binus UI bersatu” sebagai status YM nya tapi ternyata red coder mang sakti…

Gua tau ricky bisa soal F, karena gua pernah kasih ke dia soal yang mirip banget ma itu, tinggal dikasih preorder kelar dah, menjelang 40 menit terakhir, status YM gua (si Hendri juga ikut-ikutan) “HINT : PREORDER” saking frustasi nya sebagai supporter Binus dan UI wkwkwk… tapi ternyata tim binus ga ada yang liat status gua, malahan tim eleazar liat status si Hendri. Untungnya mereka ga bisa bagian setelah preordernya. Tim saklar lhompat (read : fushar) ternyata juga pernah buat soal yang mirip soal F, untung fushar ga online YM pas kontes dan nyadar tinggal dipreorder setelah kontes kelar [amin] >:) Pelajaran hari ini : kalo mau pasang HINT, appear offline dulu dari semua tim musuh yang bertanding.

Soal + pembahasan ada blog Suhendry http://www.suhendry.net/blog/?p=1135

Halaman-halaman: 1 2 3 4 5 6 7 8 9 10

Final Programming Contest Gemastik 2009

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″

Halaman-halaman: 1 2 3

Penyisihan programming contest gemastik 2009

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

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.

Halaman-halaman: 1 2 3 4 5

Penyisihan Arkavidia

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

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

Soal Trie lagi, kali ini diminta sequence katanya.Problem

UVA 11488 – Hyper Prefix Sets

Another trie soal pertama di OJ yg AC pake trie, ini ga pake pointer2an cuma pake array