Felix Halim .NET  
Google 
Name:  Message:

Indonesia National Contest 2008 - Summary

Programming Contest semakin populer dari tahun ke tahun. Indonesia National Contest (INC) merupakan salah satu ajang untuk memperlihatkan kebolehan masing-masing Universitas di Indonesia dalam hal analisis/design algoritma dan data structure maupun keterampilan membuat program. Tahun lalu INC 2007 juga diadakan di bulan yang sama. INC 2008 tahun ini sebenarnya hampir tidak jadi diselenggarakan karena kekurangan pengurus (para pengurus di-fokuskan untuk lomba ACM ICPC Regional Jakarta nanti). Berkat HIMTI, acara ini bisa terselenggarakan juga :).

Tingkatan ACM ICPC dari yang kecil ke besar adalah

  1. National / Local Contest. Lomba ini adalah optional, biasanya digunakan untuk menyaring murid-murid lokal di universitas masing-masing.
  2. Regional Contest. Tim-tim yang terpilih di masing-masing universitas bisa mendaftar ke contest tingkat Regional ini untuk bertanding antar universitas di regional yang sama. Dalam hal ini, kita berada di Regional Asia. Jadi anda bisa memilih untuk bertanding misalnya di Regional Singapore, Kanpur, Nanjing, Seoul, Tokyo, Beijing, Taipei, Tehran, Dhaka, dan lain lain... Jika anda ingin tahu seperti apa Regional Contest di Kaohsiung 2006 bisa dilihat disini.
  3. World Final Contest. Para pemenang (Juara 1) dari tingkat regional contests akan di undang untuk bertanding di tingkat World Final. Ini adalah impian semua peserta untuk bisa bertanding di tingkat ini. Untuk mengangkat nama universitas sekaligus mempercerah masa depan anda sendiri. Jika anda tertarik melihat seperti apa contest di World Final, bisa lihat di blog saya tentang ACM ICPC World Final Tokyo 2007.
Jadi sebenarnya semua universitas bisa langsung masuk Regional Contest. Kelima pemenang INC 2008 ini cuma mendapat "biaya pendaftaran" (*free pass*) gratis untuk ACM ICPC Regional Contest - Jakarta nanti tanggal 20-21 Oktober 2008. Binus University mendapatkan kehormatan untuk dapat menjadi salah satu penyelenggara (host) dari ACM ICPC tingkat Regional di Asia. Ini sangat bagus karena anda tidak perlu jauh-jauh ke luar negri untuk mengikuti Regional Contest :D. Sangat diharapkan untuk semua universitas yang ikut INC 2008 ini untuk mendaftar ke ACM ICPC Regional Contest Asia - Jakarta (pendaftarannya sudah dibuka lho.. click disini). Tentu saja untuk Regional nanti para pesertanya akan ada yang berasal dari luar negri dan jauh lebih ketat persaingannya :D. Para tim Juri pun terpaksa membuat soal yang lebih menantang :P. Akan seru nich Regional Contest nanti :D.

Dalam INC 2008 ini, saya masih melihat kesenjangan yang cukup besar. Di scoreboard babak penyisihan terlihat masih banyak sekali tim yang belum dapat menyelesaikan setidaknya satu soal. Masih diperlukan banyak latihan untuk tim-tim tersebut. Diharapkan blog yang saya buat ini bisa membantu mereka atau siapapun untuk mengembangkan diri :).

Juara di babak final INC 2008 kali ini masih tetap dipegang oleh juara bertahan INC 2007 tahun lalu, yaitu tim Kurniady. Tim NoMoreAC yang berganti nama menjadi TSP (dan juga berganti satu anggotanya kecuali Timotius Sakti dan Stephen Kohar) meraih posisi kedua seperti tahun lalu. Juara ke-3 diraih oleh tim BINUS "generasi muda" dengan nama tim pinkpanda. Tim ini diharapkan untuk bisa meneruskan prestasi BINUS untuk kedepannya (karena Andrian Kurniady sudah pensiun dini dan Timotius Sakti sebentar lagi lulus). Juara ke-4 juga diraih tim BINUS dengan nama tim acmon yang tahun lalu menggunakan nama Tweety dan anggotanya berganti 1 orang, sedangkan juara ke-5 diraih oleh tim dari Universitas Kristen Satya Wacana dengan nama tim EMI. Hasil selengkapnya bisa dilihat di scoreboard babak final.


Babak Penyisihan, 1 Juni 2008

Suhendry Effendy, kepala bagian pembuat soal, sudah menulis pembahasan/analisa soal-soal penyisihan dengan sangat baik (dengan memperhatikan kesalahan-kesalahan umum yang dilakukan oleh para peserta) oleh karena itu saya tidak lagi membahas soal-soal penyisihan disini. Pembahasan lengkap soal penyisihan oleh Suhendry bisa dilihat di websitenya.

Secara pribadi saya merasa prihatin akan hasil dari babak penyisihan INC 2008 ini karena menurut statistics yang dikumpulkan, terdapat 103 tim yang tidak bisa menyelesaikan soal satupun. Entah apa kendala yang mereka hadapi? Bagi yang ingin mendiskusikan masalahnya, bisa ketik di chatbox sebelah kanan atas dari halaman ini. Saya berharap di ACM ICPC Regional Contest Jakarta nanti (bulan Oktober 2008) tim-tim ini bisa mencapai hasil yang lebih baik. Untuk sekedar informasi, hasil dari ACM ICPC Regional Contest akan dipajang langsung di website ACM ICPC!. Jadi berusahalah semaksimal mungkin untuk mengangkat nama baik universitas dan anda sendiri di mata dunia :).

Berikut adalah soal-soal di babak penyisihan. Untuk pembahasan soal-soal bisa click langsung di kolom "Kategori" dibawah dimana anda akan di-redirect ke websitenya Suhendry.

Nama Soal Pembuat Soal Kategori Level
A Who Got the Medals? Bong Win Ce Ad Hoc 4
B Converting Numbers Bong Win Ce Mathematics 3
C Panda Land 3: Text Wrapper Evan Leonardi Simulation 5 (hardest)
D Maze Walker Suhendry Effendy Flood Fill 2
E Lemonade One Danny Gunawan Greedy or DP 1 (easiest)

Tingkat kesulitan yang ada di kolom "Level" adalah angka yang subjective. Setiap orang mempunyai kelebihan dan kekurangan masing-masing dan akan berpendapat beda tentang tingkat kesulitan tersebut.


Babak Final, 15 Juni 2008

Juara-juara Indonesia National Contest 2008 (INC 2008) adalah:

  1. Juara 1 - Binus University - kurniady (Andrian Kurniady, Fiona Liausvia, Purnama) Solved 5 problems.
  2. Juara 2 - Binus University - TSP (Timotius Sakti, Stephen Kohar, Pascal Gerardus Angriawan) Solved 4 problems.
  3. Juara 3 - Binus University - pinkpanda (Winardi Kurniawan, Eko Mirhard, Panji Kharisma) Solved 3 problems.
  4. Runner Up 1 - Binus University - acmon (Eko Wibowo, Lie Gunawan, Cun Cun Lim) Solved 3 problems.
  5. Runner Up 2 - Universitas Kristen Satya Wacana - EMI (Erisman Kriswandhani Lim / Michael Ade Soewondo / Indra Suryatama) Solved 3 problems.
Untuk lengkapnya, hasil akhir lomba INC 2008 dan detail para peserta dapat dilihat di scoreboard dan team rosters untuk babak final.

Untuk babak final, saya menulis pembahasan dari sudut pandang saya. Para peserta lain atau Juri atau para problem-setters (permbuat soal) juga dianjurkan membuat pembahasan masing-masing. Semakin banyak pembahasan, semakin banyak pilihan untuk belajar. Misalnya kalau tidak mengerti pembahasan saya ada pilihan untuk melihat pembahasan Suhendry atau yang lain. Kalau ada yang sudah buat pembahasan atau blog atau semacamnya, tolong beri tahu saya. Sebab saya ingin baca :D (begitu pula para peserta lain bukan?). Kita saling sharing aja (terbukti bagus untuk meningkatkan kemampuan dengan cepat). Saya akan masukkan link pembahasan yang saya temukan nanti ke Links/Blogs. Pembahasan saya untuk masing-masing soal di babak final dapat dilihat di menu sebelah kiri.

Sewaktu penutupan acara, Suhendry Effendy telah menjelaskan secara garis besar algoritma yang dipakai untuk solve ke delapan problems dan kembali menjelaskannya pembahasannya dalam bentuk tulisan di websitenya (pembahasan Suhendry untuk soal-soal tertentu lebih detail dari saya, sehingga pembahasannya saling melengkapi). Berikut adalah daftar soal INC 2008 di babak final.

Nama Soal Pembuat Soal Kategori Level
A Superstitious Skylab Tower Ryan Leonel Dynamic Programming 6
B Panda Land 5 Evan Leonardi Dynamic Programming 7
C Almost Clear Andoko Chandra Geometry 5
D Eat or Be Eaten Suhendry Effendy Sorting 2
E Indomie Felix Halim Combinatorics 3
F In Queries Surya Sujarwo Counting Sort 4
G Hotel Bong Wince Selection 1 (easiest)
H Walaweh Felix Halim Math + Recursion 8 (hardest)
Download semua soal/input/output/solusi


Cerita Sampingan

Sewaktu briefing maupun practice session, jika anda memperhatikan para peserta ada 2 orang memakai baju hijau dengan logo "ACM ICPC World Final, Banff Canada". Kedua orang tersebut adalah Andrian Kurniady dan Timotius Sakti. Yup, mereka belum lama ini baru saja bertanding di ACM ICPC tingkat dunia: ACM ICPC World Final (Banff, Canada 2008). Kurniady dan Timotius yang dulunya adalah satu tim waktu bertanding di World Final dengan nama tim YoiMon, ternyata tidak berada dalam satu tim di INC 2008 ini! Seperti tahun lalu, Kurniady membuat tim sendiri dengan nama Kurniady. Timotius pun membuat tim sendiri dengan nama TSP. Tampaknya meskipun mereka memecah kekuatan, tetap berhasil mencapai dua posisi teratas di babak penyisihan maupun final! Tidak bisa dibayangkan kalau mereka tetap satu tim! Timotius mengutarakan alasannya kenapa pisah tim dengan Kurniady di blognya. Berikut adalah foto kedua orang berbaju hijau yang dimaksud:

 

Tim Kurniady (kiri), dan Tim TSP (kanan) (click untuk lihat lebih besar).
Kok gaya di-foto nya bisa sama yah? bener-bener kompak :D



Baju hijau tampak dari belakang, terlihat tulisan 2008 World Final, Banff.

Untuk sekedar info, sebentar lagi ada lomba Google Code Jam 2008. Kesempatan menang untuk regionalnya lebih tinggi :) Buruan daftar + cobain practice nya disini. Saya juga mao latihan keras nich buat event ini, gak mao kalah ama yang lain :P.

Daftar Tim Peserta Babak Penyisihan INC 2008

No Team Name Team Member
Universitas Multimedia Nusantara
1UMN AAmbrosius Alvin Gunawan/Yunky Hower/Harry Indra Koswanto
2UMN BMarcel Bonar Kristanda/FX. William Riyanto/Dicky Hartono
3UMN CMarco Hudaya/Dimaz Mahendra Budi/Antony
Universitas Pelita Harapan
1kulikodingDwika Putra/Christoforus Yoga Haryanto/William
Binus University
1PhoenixDavid Pratama Lumban Tobing/Johanes/Lie Albert Januar Linarco
2TSPTimotius Sakti/Stephen Kohar/Pascal Gerardus Angriawan
3acmonEko Wibowo/Lie Gunawan/Cun Cun Lim
4kurniadyAndrian Kurniady/Fiona Liausvia/Purnama
5hiddenStef/Cuncuna smile/Eko Ari Wibowo
6Spirit4acIndra/James Natan Wiguna/Denise Harland
7Denny_DjSuryadi Chandra/Denny Djuarto/Poyuandy
8color_ijoAlfian Arief Phanoto/Davin Pradipta/Jastian Ganaputra
9illuminatiAndreas Sanjaya Paiman/Erwin Permata/Garry Bernardy
10JGTROng Randy Pratama Joeandy/RIko Nagatama/Ronny Setiawan
11pinkpandaWinardi Kurniawan/Eko Mirhard/Panji Kharisma
12wishSofia Setjahusada/Indra Gunawan/Willyanto
13bluemanLay Ivan Sulaiman/Heru Prasetia/Novianto Halim
14IntMainWilliam/Ferry Yuwono/Budi Prasetyo
15Jimmyadrianus/jimmy/adryn
16adrynarif/pratama/zulkarnain
17adrianuseric/irvan/ivan
18KaaNNelson Widjaya/Aloysius Theo Prima/Kristoforus Kevin
19lionheartzSuwandy/Jonathan Sukandi/Kurniawan Suyono
20DarcAnthony Ciputra/Christin/Devina Purwito
Institut Teknologi Sepuluh Nopember
1SolidSnakeAswin Rachmat Pramono/Adhilaras Putro Pamungkas/Achmad Sonif
2fortressBarkhah Pudya Permana/Andre Parvian A/Nela Oktivani
3mkningRidho Rahman Hariadi/M Abidir Rokhman/Arya Nugraha Nawing
4bangkitituWimbi Perdana Putra/Eka Gibran Hasany/Kurniawan Haikal
5peyipayiRindra Parama S.H./Eky Pratama Halim/Rizky Septiandy Wicaksono
6eternalThariq Nugrohotomo/Decky Kurniawan/Tommy Adhyasa Sumardhana
7dreamingTovan Setiono/Deneng Eka Putra/Mahardhika Aji S.
8senyumdonkPurnama Anaking/M.Rohmatulloh S/Aditya Saputra
9ganbamonRatri Dwi Kayungyun/M. Fitrah Muttaqin/Mirza Aulia Rahman
10festivalsWijanarko Sukma Pamungkas/M. Rizky Ramadhan/Andi M. Fahrur Hidayat
11coder_cupuYohanes Indra Riskajaya/Anang Dista Satria/Dommy Asfiandy
12WAR TeamDavid Agustinus/Ony Octavianto/Anugrah Pratama E
13kkgj_tc07Jeffrey Hermanto Halimsetiawan/Kemas Dimas R./Gita Ventyana
14ECKS-RAYFerbianto/Tristanto Khosiawan/Yohanes Khosiawan
15deadlineSatriawansyah Urbaya/Mieky Sofyan Yudinata/Charisma Reandrianto
16tuwekMuchamad Agus Romansyah/M. Khairul Habib/Arimas Artadi
17buaya_airLanang Aditya Nugraha/Ahmad Rifai/Teguh Prasetya
18madArdi Imawan/Doni Setio Pambudi/Mario Wahyu Prabowo
19aeosBilly Montolalu/Koharudin/Supriadi
20hydrantFitra Raditya S./Rizki Akbar M./Ahmad Fuadi
21blink182Priya Bagus Sasikirono Ramadhan/Vega Prima Sagitara/Firman Rosdiansyah
22noname.cppCintaniati Putri/Rahma Mustika Ningrum/Fitri Indra Indikawati
Institut Teknologi Harapan Bangsa
1GembelJayaAngga Muhammad Rahadian/Imanuel Sudiono/Zavero Krishna Wibowo
Institut Teknologi Bandung
1GukGukSamuel Simon/Dominikus Damas Putranto/Jansen
2ASDFAris Feryanto/Fanny Limassa/Bernardino Madaharsa Dito A.
3GamerEka Permadi Susanto/Firdi Mulia/Praba Iman Prasaja
4arihilArief Pratama/Muhammad Ihsan/Ilden Abi Neri
5K.E.F.SKevin Tanadi/Evan/Ferry Mulia
Universitas Kristen Satya Wacana
1EMIErisman Kriswandhani Lim/Michael Ade Soewondo/Indra Suryatama
2fti-ukswANDI TARU NUGROHO NW/OMEGA PALGUNO PURNOMO/AGHATA DHIWI ASHITA
3xrvelDicky Kurniawan/Nelfrit Christopher/Jolly Lengkono
4fti-uksw06Yongkie Purnomo BudiSaputra/Christina Victoria/Marcel Willem Aipasa
Parahyangan Catholic University
1cobahura2Felix Chandra S/Andrianto Dwi L/Aditya Nugraha
2Gun A DieChandra Diharja/William Budianto Sutisno/Hendra Gunadi
3HuraHura07Christian Indrayana/Suarlin Husni/Elisa
4¼skill ¾hqIdham Yuandi/Yulius Chandra/Felix Samuel Lando
5hanekiHadi Saloko/Nelson Kurniawan/Kikita Yoshehana
6ParadoksEdric Marthanegara/Eldwin Viriya/Dicky Wira Senjaya
7unpar12029Adrian Darmawan/Michael Yohanes/Jason Ipinsaputra Kurniawan
UIN Syarif Hidayatullah Jakarta
1TIC_ExtMuhamad Qadhavi/Setiajid/Anton Budiwan
2bpc_uin1Bima Aji Saputro/Muhammad Tri Wibowo/Retno Ayu Widiyaningrum
3bpc_uin2Heri Nurmanto/Deni Zakya/Yunita
4bpc_uin3Heru Arya Pratama/Agunahwan A./Putra Angga Anolisa
5bpc_uin4Afrialdi Syahputra Butar Butar/Annisa Primasari/Morteza Muthahhari
6bpc_uin5Reza Andy Pradana/Edwin Adhiputra/Ardiansyah
Universitas Nasional PASIM
1amatAmat Miftakhudin/Akhmad Fakhrurrozi/Irman Sulaeman
2cyberwitchAde Saprudin/Akhmad Yani/Nunuh Nurjaman
Universitas Sumatera Utara
1BonggowIzhari Ishak Aksa/Ronny P. Silitonga/Jefri Umar
2k1r4Rizky Zulkarnaen/Fachrurozi Nasution/yuyanto
Universitas Brawijaya
1brawijayaYanuar Risah Prayogi/Mirza Galih K/Mohammad Azis Fatoni
2UB_TeamRatna Mufidah/Pipit Tunjungsari/Rini Alifah
Universitas Sanata Dharma
1code-manAngela Ami Asmarani/Teresia Esti Seliastuti/Henricus Wahyudi
2trnkanBBMBayuSanjaya/Anna Setiawan/Hertartik Clarasita Devy
3USD01Fransiskus Anggit/Hendra Christian/Wiliams Andrian
4USD02Florensius Phangestu/Dony Setiyawan Nugroho/Benidiktus
5USD03Sari Indah Anatta S./Albertus Dio/Taufik
6USD04RobinSteven/Kartono Pinaryanto/Alexander Rosyanto
Sekolah Tinggi Sandi Negara
1cryptocodeArief Karfianto/Zaenal Suhardono/Tetra Widianto
Universitas Pendidikan Indonesia
1uteukYaya Wihardi/Irvan Riswanto/Winprins
2ilkomupi06Avionic/Husni Firmansyah/Yopi
Universitas Indonesia
1mcntouchMoehammad Ichsan/Rizki Mardian/Danu Widatama
2RTCRicky Suryadharma/Teddy/Charles Christian
3UI_4Ade Saputra/Deni Lukmanul Hakim/Erik Dominikus
4jajakajawaAgung Firmansyah/Bayu Distiawan/Ikhlas Purwanto
Universitas Atma Jaya Yogyakarta
1lumineNg Elyi Junaidi/Yohanes Novendriono/Erlangga Pradipta Suryanto
2ardiansaBernadus Ari Nugraha/Christina Dian Hayu Kurniawati/Elisabeth Kurnia Wijayanti
3VeRMeLBafo Ade Hutiva/Anastasius Triseptian/Bagus Ade Saputra
4burjoNengsih Fitria/Vidi Valianto Shaweddy/Ridwan Yusuf
5cuxedHendri/YB Bagus Adityatama/Daphne Eka Jayanti Wesling
Universitas Surabaya
1ubaya1EDWIN MOCHSIN/RESAN TANAGO/REDEN TANAGO
2ubaya2PRASETIA GUNAWAN/HARMAN WIJAYA/YOHANES WILLIAM SAMBUDJO
3ubaya3ANDY SURYA PRANATA/WEE CIANG/BENNY KURNIAWAN SOENARJO
4ubaya4FX. BAMBANG EKO SANTOSO/ASWIN NIOGROHO/TOMMY ADITYA LAWANTO
5ubaya5ARIIS PRATAMA SETIABUDI/IVAN WIDJAJA/YULIANTO
6ubaya6SUSANTO BENNY/HARDI LIMIYANTO/JOHAN KRISTIANTO
7L-ACCendra Yamin/Dewi Maria/Aris Untung
Petra Christian University
1Oct++Andy Basuki/Albertus Wonges/Eko Adi Prasetyo Gunawan
2EAStElizabeth Kwan/Anton Indrawan/Stephanus Surya Jaya
3vistaKiswono Prayogo/Wendy Gunawan/Robin Chandra
4"A"Albert Halim/Adrian Hartanto/Alvin Nathaniel T.
UNIKA Soegijapranata
1ikom_06Iwan Setiawan/Doni Cahyanto Y./Marcellina Ervina S.
2proxieRhesa Varian/Hendarta Aditya S/De Rosal Ignatius Moses S
3ikom1Adi Nugroho/Ong Milo Caturangga Hariyanto/Benny Santoso
STMIK Mikroskil
1NEW_BIESUWANDI/HENDRA GUNTUR/HENDRIK TANDIONO
2WONGDESODARWIN KOSASIH/ANDREW JAUHARI/HARTONO
3CRYSTALDARWIN/SUNARIO MEGAWAN/RICHIE SETIAWAN
4SWINGARWIN HALIM/JHON KEVIN/FENDY
5ICE_BOY3EIGER YAP/KASIM/ANDY PUTRA
6DEBUSHABRI LOY/HENDRA SUWANDA/ULNI AHMAD PERDANA
Widyatama University
1RoyalFlushIndra Pranatha/Ardhi Beniyanto/Lerry Manggara Putra
2frogrootTeguh akbar/Rizki kalgasi kasim/Andreas Riadi
3iteamMathofany Boer/Asep Rukmana/Redi Widyawan
Institut Bisnis dan Informatika Indonesia
1BISILinda Chandra/Shita Novelia/Daniel Stefie
2LOW FATJosephine/Yogi/Sucipto
STMIK MDP
1stmik-mdpMohammad Iqbal/Didy Yedidyah Listyarwan/Jonni
Mercu Buana University
1fasilkom2Dian Wirawan/Fronita/Adi Wahab
2fasilkomHendra Triyatmaka/Agung Wiseso/Denny Satriyatno
Universitas Budi Luhur
1blue01Muhamad Haveis Yulindo/Hendro Purnama Sardjono/Febri Wicaksono
2blue02Shintya Yulianti/Tiharsih/Hairunnisa
3blue03Abdul Aziz Nur/Rawuh Harsongko/Christine
4blue04Alfonsius S/Pujianto/Restu Maulunida
Institut Pertanian Bogor
1ilkomipbWildan Rachman/Indra Juniawan/Ciramudya Adha Gafawidj
Institut Teknologi Telkom
1STT01Fauzi Aulia Rahman/Karina Fitriani Fatimah/Oscar T. Ardianto
2dna_softDody Qori Utama/Alfian Akbar Gozali/Naufal Mikhdzam Ar Rozi
3ARTisRizky Ario Nugroho/Rindang Septyan/Septian Rani
4scratchzAli Murtado Fauzarrohman/Sugihartono/Saputra Aries Pratama
Dian Nuswantoro University
1vectorcodeIswahyudi/Agusta Wicaksono/Ahmad Saiful Muhajjir
Universitas Sriwijaya
1cyborgBinahar Agus P/Vebby Madyasari/Yuli Astuti
2FADEDede Kurniawan/Fikri Heriyanto/Adril Tabrani
3CYBERM. Ali Buchari/Edvin Ramadhan/Aldefvi Roci
4DINDAMYusrizal Erwansyah/M.Nur Hasyim/Yovi Pratama
Sekolah Tinggi Informatika & Komputer Indonesia
1ELANGSonny Setiawan/Go Frendi Gunawan/Varin Dwi Saputra
Universitas Kristen Duta Wacana
1DUTADaniel Susanto/Wilbert/Yoshua Aditya Santoso
2WALKAgustinus Patrisius Suku/Willy Budiman/Kharis Handoko
Universitas Gadjah Mada
1usernameWahyono/Riza Oktavian NS/Saifuddin Noor Afifi
2aaaAgung Nugroho/Ardian/Aaron Baratha
Universitas Islam Indonesia
1pit-uiiDAYU BAGUS PERMATA/DWIRA MAULANA/BRIMA ARIBOWO
Universitas Kristen Maranatha
1TREUKMErick Costanio/Tri Chandra/Depenses
2Maranatha1Melingga Waty/Ade Rusmana/Samuel Christianto
3Maranatha2Louwy Ayasin/Christian Suhindar/Yulianti
Institut Teknologi Indonesia
1HMIF_ITIA.A.Ayu Mirah Handayani/Rangga Effendi/Mochamad Setiady
Sekolah Tinggi Ilmu Statistik
1youYou Ari Faeni/I Gde Agus Arya/Abdurrahman Assel
2ArieArie Wahyu/Feby Dwi/Aris Prawisudatama
3takdirTakdir/Cahya Al Kahfi/Miswar
4anasAnas/Habi/Sawung
Institut Teknologi Adhi Tama Surabaya
1ITATSMITA ISTINARATI/WAHYUDI KARUNIA TJUATJA/ALEXANDER ADITYA N.
Universitas Pakuan
1UNPAK2Rudi Yudhistira/Yuly Wati/Adhi Rohmat
2UNPAK1Syamsuri/Zaenal Abidin/Arizal Coto
Universitas Komputer Indonesia
1unikomIF2Rully Isma Hidayat/Friko Simanjuntak/Eko Kurniawan Khannedy
2unikomIF1Yudi Yogaswara/Eko Budi Setiawan/Adam Mukharil Bachtiar
3unikomIF3Herman Herwansyah/Herdi A/Warman Suganda

Scoreboard - Hasil Akhir Babak Penyisihan INC 2008

Rank Team(s) A B C D E Solved Total Time
1TSP
Binus University
2/1043/593/-1/121/594294
2kurniady
Binus University
6/963/834/-1/181/534390
3Gun A Die
Parahyangan Catholic University
2/743/1016/-3/1051/224402
4pinkpanda
Binus University
3/753/1291/-1/412/684413
5haneki
Parahyangan Catholic University
1/685/131-/-3/1593/634581
6K.E.F.S
Institut Teknologi Bandung
3/981/79-/-7/1442/1124613
7acmon
Binus University
3/935/--/-2/482/403261
8kulikoding
Universitas Pelita Harapan
2/913/149-/-1/-1/333333
9RTC
Universitas Indonesia
1/1281/80-/-3/-2/1773405
10username
Universitas Gadjah Mada
2/1022/--/-1/1771/1103409
11Oct++
Petra Christian University
1/115-/--/-1/1684/1443487
12EMI
Universitas Kristen Satya Wacana
5/-6/1801/-2/921/1223514
13vista
Petra Christian University
6/1503/143-/-5/-12/1663819
14Spirit4ac
Binus University
1/611/--/--/-1/1032164
15lumine
Universitas Atma Jaya Yogyakarta
1/691/--/--/-2/1242213
16GukGuk
Institut Teknologi Bandung
2/-5/--/-2/1181/792217
17UI_4
Universitas Indonesia
1/1233/--/-1/-1/972220
18eternal
Institut Teknologi Sepuluh Nopember
2/77-/--/--/-1/1242221
19SWING
STMIK Mikroskil
1/76-/--/-1/176-/-2252
20Phoenix
Binus University
2/-10/--/-2/1381/1232281
21¼skill ¾hq
Parahyangan Catholic University
5/-6/-7/-1/1291/1732302
22Bonggow
Universitas Sumatera Utara
3/--/--/-2/1433/1162319
23mkning
Institut Teknologi Sepuluh Nopember
5/1693/--/-2/-1/742323
24Paradoks
Parahyangan Catholic University
3/-4/--/-3/1511/1682359
25illuminati
Binus University
2/1123/--/-4/-5/1502362
26cobahura2
Parahyangan Catholic University
6/-1/--/-1/1784/1382376
27EASt
Petra Christian University
8/177-/-1/-1/-2/1142451
28SolidSnake
Institut Teknologi Sepuluh Nopember
7/-2/--/--/-1/50150
29bangkititu
Institut Teknologi Sepuluh Nopember
4/-3/--/-2/-1/53153
30senyumdonk
Institut Teknologi Sepuluh Nopember
-/--/--/--/-1/86186
31fortress
Institut Teknologi Sepuluh Nopember
-/--/--/--/-1/89189
32unpar12029
Parahyangan Catholic University
1/--/--/-3/-1/94194
33WONGDESO
STMIK Mikroskil
-/-1/-1/--/-1/1131113
34ubaya2
Universitas Surabaya
3/762/--/-5/--/-1116
35ubaya4
Universitas Surabaya
-/-2/--/-4/-2/961116
36bpc_uin1
UIN Syarif Hidayatullah Jakarta
-/-1/--/--/-1/1241124
37bpc_uin4
UIN Syarif Hidayatullah Jakarta
-/--/--/--/-1/1271127
38ASDF
Institut Teknologi Bandung
3/-4/--/-2/-1/1291129
39ubaya1
Universitas Surabaya
2/1151/--/--/--/-1135
40kkgj_tc07
Institut Teknologi Sepuluh Nopember
1/--/--/-3/-2/1171137
41LOW FAT
Institut Bisnis dan Informatika Indonesia
1/1483/--/-2/--/-1148
42BISI
Institut Bisnis dan Informatika Indonesia
1/153-/--/--/--/-1153
43aaa
Universitas Gadjah Mada
-/--/--/--/-1/1531153
44ilkomipb
Institut Pertanian Bogor
-/--/--/-1/-1/1541154
45UMN A
Universitas Multimedia Nusantara
3/-1/--/-2/-1/1551155
46mad
Institut Teknologi Sepuluh Nopember
4/-7/--/--/-2/1631183
47peyipayi
Institut Teknologi Sepuluh Nopember
4/--/--/--/-4/1461206
48Gamer
Institut Teknologi Bandung
1/--/--/--/-3/1781218
49wish
Binus University
-/-7/--/-5/1394/-1219
50STT01
Institut Teknologi Telkom
-/--/--/--/-4/1791239
51HuraHura07
Parahyangan Catholic University
-/-7/--/--/-8/1411281
52lionheartz
Binus University
6/-10/174-/-9/--/-1354
53UMN C
Universitas Multimedia Nusantara
-/--/-1/-2/--/-00
54vectorcode
Dian Nuswantoro University
-/-1/--/--/--/-00
55xrvel
Universitas Kristen Satya Wacana
-/-1/--/-1/--/-00
56VeRMeL
Universitas Atma Jaya Yogyakarta
-/--/-6/--/-5/-00
57WALK
Universitas Kristen Duta Wacana
-/-2/--/--/-1/-00
58unikomIF2
Universitas Komputer Indonesia
1/--/--/--/--/-00
59noname.cpp
Institut Teknologi Sepuluh Nopember
-/--/--/--/--/-00
60unikomIF3
Universitas Komputer Indonesia
-/--/--/--/--/-00
61NEW_BIE
STMIK Mikroskil
1/--/--/-4/-16/-00
62WAR Team
Institut Teknologi Sepuluh Nopember
3/-1/--/--/--/-00
63uteuk
Universitas Pendidikan Indonesia
2/--/--/-1/--/-00
64Maranatha2
Universitas Kristen Maranatha
-/--/--/--/--/-00
65Maranatha1
Universitas Kristen Maranatha
-/--/--/--/-3/-00
66UB_Team
Universitas Brawijaya
1/-1/--/--/--/-00
67unikomIF1
Universitas Komputer Indonesia
-/-1/--/--/--/-00
68mcntouch
Universitas Indonesia
-/--/--/--/-1/-00
69UMN B
Universitas Multimedia Nusantara
2/-4/--/-2/-1/-00
70you
Sekolah Tinggi Ilmu Statistik
1/--/-1/--/-2/-00
71hidden
Binus University
-/--/--/--/--/-00
72USD01
Universitas Sanata Dharma
2/-1/-1/-1/-1/-00
73tuwek
Institut Teknologi Sepuluh Nopember
5/-3/--/--/-9/-00
74stmik-mdp
STMIK MDP
-/--/--/--/-3/-00
75UNPAK1
Universitas Pakuan
-/--/--/--/--/-00
76takdir
Sekolah Tinggi Ilmu Statistik
-/--/-1/--/--/-00
77TIC_Ext
UIN Syarif Hidayatullah Jakarta
-/-1/--/--/--/-00
78UNPAK2
Universitas Pakuan
-/--/--/--/--/-00
79USD02
Universitas Sanata Dharma
-/-1/--/-1/--/-00
80TREUKM
Universitas Kristen Maranatha
3/--/--/--/-3/-00
81ubaya3
Universitas Surabaya
4/-2/--/-1/--/-00
82scratchz
Institut Teknologi Telkom
-/--/--/-2/-2/-00
83USD04
Universitas Sanata Dharma
1/--/--/-4/--/-00
84pit-uii
Universitas Islam Indonesia
-/--/--/--/--/-00
85proxie
UNIKA Soegijapranata
1/--/--/-1/-3/-00
86RoyalFlush
Widyatama University
-/-1/--/--/--/-00
87USD03
Universitas Sanata Dharma
3/-1/-1/-1/-1/-00
88ubaya6
Universitas Surabaya
-/-3/--/-3/-5/-00
89ubaya5
Universitas Surabaya
-/-1/--/-4/-2/-00
90trnkanBBM
Universitas Sanata Dharma
1/--/--/-7/--/-00
91L-AC
Universitas Surabaya
4/--/--/--/-1/-00
92"A"
Petra Christian University
2/-3/--/-1/--/-00
93bpc_uin3
UIN Syarif Hidayatullah Jakarta
3/-1/--/--/--/-00
94bpc_uin5
UIN Syarif Hidayatullah Jakarta
-/--/--/--/--/-00
95brawijaya
Universitas Brawijaya
1/-4/--/--/--/-00
96buaya_air
Institut Teknologi Sepuluh Nopember
1/--/--/--/--/-00
97burjo
Universitas Atma Jaya Yogyakarta
4/-1/--/--/-7/-00
98code-man
Universitas Sanata Dharma
8/--/--/--/-2/-00
99coder_cupu
Institut Teknologi Sepuluh Nopember
1/-2/--/--/-4/-00
100color_ijo
Binus University
2/--/--/-1/-1/-00
101cryptocode
Sekolah Tinggi Sandi Negara
-/--/--/--/-1/-00
102CRYSTAL
STMIK Mikroskil
-/--/--/-1/-1/-00
103cuxed
Universitas Atma Jaya Yogyakarta
2/-6/--/--/--/-00
104CYBER
Universitas Sriwijaya
-/--/--/-4/--/-00
105cyberwitch
Universitas Nasional PASIM
1/--/--/-3/--/-00
106cyborg
Universitas Sriwijaya
1/--/--/-3/-2/-00
107bpc_uin2
UIN Syarif Hidayatullah Jakarta
-/--/--/--/--/-00
108blueman
Binus University
4/--/-2/-3/--/-00
109adrianus
Binus University
-/--/--/--/--/-00
110adryn
Binus University
-/--/--/--/--/-00
111aeos
Institut Teknologi Sepuluh Nopember
4/-5/--/--/-7/-00
112amat
Universitas Nasional PASIM
1/--/--/--/-5/-00
113anas
Sekolah Tinggi Ilmu Statistik
2/--/--/--/--/-00
114ardiansa
Universitas Atma Jaya Yogyakarta
-/--/--/-2/--/-00
115Arie
Sekolah Tinggi Ilmu Statistik
3/--/--/--/-3/-00
116arihil
Institut Teknologi Bandung
2/-1/-1/--/--/-00
117ARTis
Institut Teknologi Telkom
-/-8/--/--/--/-00
118blink182
Institut Teknologi Sepuluh Nopember
2/--/-1/--/--/-00
119blue01
Universitas Budi Luhur
5/--/--/--/--/-00
120blue02
Universitas Budi Luhur
-/--/--/--/-3/-00
121blue03
Universitas Budi Luhur
-/--/--/--/--/-00
122blue04
Universitas Budi Luhur
-/--/--/--/--/-00
123Darc
Binus University
2/--/--/--/--/-00
124deadline
Institut Teknologi Sepuluh Nopember
4/-5/--/--/-1/-00
125DEBUS
STMIK Mikroskil
1/--/--/--/-3/-00
126HMIF_ITI
Institut Teknologi Indonesia
-/--/--/--/--/-00
127hydrant
Institut Teknologi Sepuluh Nopember
4/--/--/-3/--/-00
128ICE_BOY3
STMIK Mikroskil
2/--/--/-1/--/-00
129ikom1
Unika Soegijapranata
-/--/--/--/-1/-00
130ikom_06
UNIKA Soegijapranata
3/-1/--/--/-1/-00
131ilkomupi06
Universitas Pendidikan Indonesia
-/-1/--/--/--/-00
132IntMain
Binus University
4/-5/--/--/-2/-00
133ITATS
Institut Teknologi Adhi Tama Surabaya
3/--/--/-2/--/-00
134iteam
Widyatama University
-/--/--/--/--/-00
135jajakajawa
Universitas Indonesia
-/--/--/-3/-3/-00
136JGTR
Binus University
4/-7/-4/-4/-1/-00
137Jimmy
Binus University
-/--/--/--/--/-00
138k1r4
Universitas Sumatera Utara
1/--/--/--/--/-00
139GembelJaya
Institut Teknologi Harapan Bangsa
3/-1/--/--/-2/-00
140ganbamon
Institut Teknologi Sepuluh Nopember
3/-1/--/--/--/-00
141Denny_Dj
Binus University
1/-5/--/-1/-1/-00
142DINDAM
Universitas Sriwijaya
-/--/--/-2/-4/-00
143dna_soft
Institut Teknologi Telkom
2/-2/--/--/-4/-00
144dreaming
Institut Teknologi Sepuluh Nopember
3/-2/--/--/--/-00
145DUTA
Universitas Kristen Duta Wacana
3/--/--/--/-1/-00
146ECKS-RAY
Institut Teknologi Sepuluh Nopember
-/--/--/-3/-1/-00
147ELANG
Sekolah Tinggi Informatika & Komputer Indonesia
-/--/--/--/--/-00
148FADE
Universitas Sriwijaya
3/--/--/-1/-1/-00
149fasilkom
Mercu Buana University
-/--/--/--/--/-00
150fasilkom2
Mercu Buana University
-/-1/--/--/-2/-00
151festivals
Institut Teknologi Sepuluh Nopember
-/--/-1/-2/-5/-00
152frogroot
Widyatama University
-/-2/--/--/-1/-00
153fti-uksw
Universitas Kristen Satya Wacana
3/-4/--/--/--/-00
154fti-uksw06
Universitas Kristen Satya Wacana
3/--/--/--/--/-00
155KaaN
Binus University
-/--/--/--/--/-00

Statistics - Babak Penyisihan

Statistic dibawah ini berasal dari data yang dikumpulkan oleh Suhendry Effendy di blog nya.


Submissions

ProblemSubmissionAccepted
C/C++JavaTotalC/C++JavaTotalRate
A16888256204249.38%
B1724721992115.02%
C368440000%
D127381651621810.91%
E1805023037104720.43%
Total683231914821810010.94%


Rejected Submissions

ReasonC/C++JavaTotal
Presentation Error (PE)101
Wrong Answer (WA)414117532
Run-time Error (RTE)4169110
Time-limit Exceed (TLE)929101
Compile Error (CE)531770


Number of Problem Solved

SolveTeams
5 problems0 teams
4 problems6 teams
3 problems7 teams
2 problems14 teams
1 problems25 teams
0 problems103 teams

Daftar Tim Peserta Babak Final INC 2008

Universitas Multimedia Nusantara

  • UMN A (Ambrosius Alvin Gunawan / Yunky Hower / Harry Indra Koswanto )

Universitas Pelita Harapan

  • kulikoding (Dwika Putra / Christoforus Yoga Haryanto / William )

Binus University

  • acmon (Eko Wibowo / Lie Gunawan / Cun Cun Lim )
  • illuminati (Andreas Sanjaya Paiman / Erwin Permata / Garry Bernardy )
  • kurniady (Andrian Kurniady / Fiona Liausvia / Purnama )
  • lionheartz (Suwandy / Jonathan Sukandi / Kurniawan Suyono )
  • Phoenix (David Pratama Lumban Tobing / Johanes / Lie Albert Januar Linarco )
  • pinkpanda (Winardi Kurniawan / Eko Mirhard / Panji Kharisma )
  • Spirit4ac (Indra / James Natan Wiguna / Denise Harland )
  • TSP (Timotius Sakti / Stephen Kohar / Pascal Gerardus Angriawan )
  • wish (Sofia Setjahusada / Indra Gunawan / Willyanto )

Institut Teknologi Sepuluh Nopember

  • bangkititu (Wimbi Perdana Putra / Eka Gibran Hasany / Kurniawan Haikal )
  • eternal (Thariq Nugrohotomo / Decky Kurniawan / Tommy Adhyasa Sumardhana )
  • fortress (Barkhah Pudya Permana / Andre Parvian A / Nela Oktivani )
  • kkgj_tc07 (Jeffrey Hermanto Halimsetiawan / Kemas Dimas R. / Gita Ventyana )
  • mad (Ardi Imawan / Doni Setio Pambudi / Mario Wahyu Prabowo )
  • mkning (Ridho Rahman Hariadi / M Abidir Rokhman / Arya Nugraha Nawing )
  • peyipayi (Rindra Parama S.H. / Eky Pratama Halim / Rizky Septiandy Wicaksono )
  • senyumdonk (Purnama Anaking / M.Rohmatulloh S / Aditya Saputra )
  • SolidSnake (Aswin Rachmat Pramono / Adhilaras Putro Pamungkas / Achmad Sonif )

Institut Teknologi Bandung

  • ASDF (Aris Feryanto / Fanny Limassa / Bernardino Madaharsa Dito A)
  • Gamer (Eka Permadi Susanto / Firdi Mulia / Praba Iman Prasaja)
  • GukGuk (Samuel Simon / Dominikus Damas Putranto / Jansen)
  • K.E.F.S (Kevin Tanadi / Evan / Ferry Mulia)

Universitas Kristen Satya Wacana

  • EMI (Erisman Kriswandhani Lim / Michael Ade Soewondo / Indra Suryatama)

Parahyangan Catholic University

  • ¼skill ¾hq (Idham Yuandi / Yulius Chandra / Felix Samuel Lando)
  • cobahura2 (Felix Chandra S / Andrianto Dwi L / Aditya Nugraha )
  • Gun A Die (Chandra Diharja / William Budianto Sutisno / Hendra Gunadi )
  • haneki (Hadi Saloko / Nelson Kurniawan / Kikita Yoshehana )
  • HuraHura07 (Christian Indrayana / Suarlin Husni / Elisa )
  • Paradoks (Edric Marthanegara / Eldwin Viriya / Dicky Wira Senjaya )
  • unpar12029 (Adrian Darmawan / Michael Yohanes / Jason Ipinsaputra Kurniawan )

UIN Syarif Hidayatullah Jakarta

  • bpc_uin1 (Bima Aji Saputro / Muhammad Tri Wibowo / Retno Ayu Widiyaningrum )
  • bpc_uin4 (Afrialdi Syahputra Butar Butar / Annisa Primasari / Morteza Muthahhari )

Universitas Sumatera Utara

  • Bonggow (Izhari Ishak Aksa / Ronny P. Silitonga / Jefri Umar)

Univeristas Indonesia

  • UI_4 (Ade Saputra / Deni Lukmanul Hakim / Erik Dominikus )
  • RTC (Ricky Suryadharma / Teddy / Charles Christian )

Universitas Atma Jaya Yogyakarta

  • lumine (Ng Elyi Junaidi / Yohanes Novendriono / Erlangga Pradipta Suryanto )

Universitas Surabaya

  • ubaya1 (EDWIN MOCHSIN / RESAN TANAGO / REDEN TANAGO)
  • ubaya2 (PRASETIA GUNAWAN / HARMAN WIJAYA / YOHANES WILLIAM SAMBUDJO)
  • ubaya4 (FX. BAMBANG EKO SANTOSO / ASWIN NIOGROHO / TOMMY ADITYA LAWANTO)

Petra Christian University

  • EASt (Elizabeth Kwan / Anton Indrawan / Stephanus Surya Jaya)
  • Oct++ (Andy Basuki / Albertus Wonges / Eko Adi Prasetyo Gunawan)
  • vista (Kiswono Prayogo / Wendy Gunawan / Robin Chandra)

STMIK Mikroskil

  • SWING (SUWANDI / HENDRA GUNTUR / HENDRIK TANDIONO)
  • WONGDESO (DARWIN KOSASIH / ANDREW JAUHARI / HARTONO)

Institut Bisnis dan Informatika Indonesia

  • BISI (Linda Chandra / Shita Novelia / Daniel Stefie)
  • LOW FAT (Josephine / Yogi / Sucipto)

Institut Pertanian Bogor

  • ilkomipb (Wildan Rachman / Indra Juniawan / Ciramudya Adha Gafawidj)

Institut Teknologi Telkom

  • STT01 (Fauzi Aulia Rahman / Karina Fitriani Fatimah / Oscar T. Ardianto)

Universitas Gadjah Mada

  • aaa (Agung Nugroho / Ardian / Aaron Baratha)
  • username (Wahyono / Riza Oktavian NS / Saifuddin Noor Afifi)

Scoreboard - Hasil Akhir Babak Final INC 2008

Rank Team Name Solved Time A B C D E F G H Total att/solv
1 kurniady
Binus University
5 708 3/192 0/-- 3/286 1/7 1/25 13/-- 1/118 0/-- 22/5
2 TSP
Binus University
4 458 0/-- 0/-- 2/-- 1/6 1/26 5/216 1/130 0/-- 10/4
3 pinkpanda
Binus University
3 236 0/-- 0/-- 1/-- 1/14 2/118 2/-- 1/84 1/-- 8/3
4 acmon
Binus University
3 435 0/-- 0/-- 0/-- 1/20 5/-- 3/216 2/139 2/-- 13/3
5 EMI
Universitas Kristen Satya Wacana
3 499 1/-- 0/-- 0/-- 3/49 3/115 0/-- 4/195 0/-- 11/3
6 mkning
Institut Teknologi Sepuluh Nopember
3 519 1/-- 0/-- 0/-- 1/26 2/154 1/-- 5/239 0/-- 10/3
7 mad
Institut Teknologi Sepuluh Nopember
3 556 0/-- 0/-- 0/-- 3/84 1/261 0/-- 2/151 0/-- 6/3
8 RTC
Universitas Indonesia
3 586 0/-- 0/-- 0/-- 1/122 1/249 2/-- 1/215 0/-- 5/3
9 vista
Petra Christian University
3 661 0/-- 0/-- 0/-- 5/114 2/207 0/-- 2/220 0/-- 9/3
10 Gun A Die
Parahyangan Catholic University
2 109 0/-- 0/-- 1/-- 1/15 1/94 8/-- 12/-- 0/-- 23/2
11 kulikoding
Universitas Pelita Harapan
2 185 0/-- 0/-- 0/-- 1/46 1/139 7/-- 3/-- 0/-- 12/2
12 K.E.F.S
Institut Teknologi Bandung
2 198 0/-- 0/-- 0/-- 1/20 9/-- 0/-- 3/138 0/-- 13/2
13 eternal
Institut Teknologi Sepuluh Nopember
2 250 0/-- 0/-- 0/-- 1/28 0/-- 0/-- 2/202 0/-- 3/2
14 ¼skill ¾hq
Parahyangan Catholic University
2 278 0/-- 0/-- 0/-- 5/74 0/-- 8/-- 2/104 0/-- 15/2
15 UI_4
Universitas Indonesia
2 289 0/-- 0/-- 0/-- 1/19 5/190 4/-- 2/-- 0/-- 12/2
16 Phoenix
Binus University
2 311 0/-- 0/-- 0/-- 1/16 8/-- 0/-- 6/195 0/-- 15/2
17 haneki
Parahyangan Catholic University
2 320 0/-- 0/-- 3/-- 2/22 1/-- 0/-- 4/218 0/-- 10/2
18 unpar12029
Parahyangan Catholic University
2 331 0/-- 0/-- 0/-- 2/84 0/-- 0/-- 1/227 0/-- 3/2
19 ubaya2
Universitas Surabaya
2 391 0/-- 0/-- 0/-- 4/120 0/-- 0/-- 4/151 0/-- 8/2
20 Spirit4ac
Binus University
2 425 0/-- 0/-- 0/-- 3/146 0/-- 0/-- 1/239 0/-- 4/2
21 EASt
Petra Christian University
2 505 0/-- 0/-- 0/-- 10/128 1/197 0/-- 12/-- 0/-- 23/2
22 Gamer
Institut Teknologi Bandung
1 27 0/-- 0/-- 0/-- 1/27 0/-- 0/-- 0/-- 0/-- 1/1
23 aaa
Universitas Gadjah Mada
1 46 1/-- 0/-- 0/-- 1/46 0/-- 0/-- 0/-- 0/-- 2/1
24 UMN A
Universitas Multimedia Nusantara
1 53 0/-- 0/-- 0/-- 1/53 0/-- 1/-- 3/-- 0/-- 5/1
25 Paradoks
Parahyangan Catholic University
1 60 1/-- 0/-- 0/-- 2/40 0/-- 0/-- 1/-- 0/-- 4/1
26 username
Universitas Gadjah Mada
1 62 3/-- 0/-- 0/-- 2/42 0/-- 0/-- 3/-- 0/-- 8/1
27 kkgj_tc07
Institut Teknologi Sepuluh Nopember
1 76 0/-- 0/-- 0/-- 2/56 0/-- 0/-- 8/-- 0/-- 10/1
28 senyumdonk
Institut Teknologi Sepuluh Nopember
1 99 3/-- 0/-- 0/-- 2/79 0/-- 0/-- 0/-- 0/-- 5/1
29 bpc_uin1
UIN Syarif Hidayatullah Jakarta
1 101 2/-- 0/-- 0/-- 2/81 0/-- 4/-- 0/-- 0/-- 8/1
30 cobahura2
Parahyangan Catholic University
1 111 0/-- 0/-- 0/-- 2/91 0/-- 1/-- 5/-- 0/-- 8/1
31 ubaya1
Universitas Surabaya
1 119 0/-- 0/-- 0/-- 4/59 0/-- 0/-- 5/-- 0/-- 9/1
32 SolidSnake
Institut Teknologi Sepuluh Nopember
1 125 0/-- 0/-- 0/-- 4/65 0/-- 4/-- 2/-- 0/-- 10/1
33 STT01
Institut Teknologi Telkom
1 128 0/-- 0/-- 0/-- 3/88 0/-- 0/-- 7/-- 0/-- 10/1
34 bangkititu
Institut Teknologi Sepuluh Nopember
1 135 0/-- 0/-- 0/-- 4/75 2/-- 0/-- 5/-- 0/-- 11/1
35 Oct++
Petra Christian University
1 142 0/-- 0/-- 0/-- 3/102 9/-- 0/-- 8/-- 0/-- 20/1
36 ilkomipb
Institut Pertanian Bogor
1 144 0/-- 0/-- 0/-- 2/124 1/-- 0/-- 3/-- 0/-- 6/1
37 fortress
Institut Teknologi Sepuluh Nopember
1 163 0/-- 0/-- 0/-- 5/83 0/-- 0/-- 5/-- 0/-- 10/1
38 LOW FAT
Institut Bisnis dan Informatika Indonesia
1 165 1/-- 0/-- 0/-- 1/165 0/-- 0/-- 2/-- 0/-- 4/1
39 wish
Binus University
1 278 0/-- 0/-- 0/-- 8/138 0/-- 1/-- 0/-- 0/-- 9/1
40 HuraHura07
Parahyangan Catholic University
1 305 0/-- 0/-- 0/-- 6/205 0/-- 0/-- 8/-- 0/-- 14/1
41 peyipayi
Institut Teknologi Sepuluh Nopember
1 321 0/-- 0/-- 0/-- 4/261 0/-- 0/-- 4/-- 0/-- 8/1
42 ASDF
Institut Teknologi Bandung
0 0 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/0
42 BISI
Institut Bisnis dan Informatika Indonesia
0 0 1/-- 0/-- 0/-- 7/-- 0/-- 0/-- 0/-- 0/-- 8/0
42 Bonggow
Universitas Sumatera Utara
0 0 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/0
42 bpc_uin4
UIN Syarif Hidayatullah Jakarta
0 0 5/-- 0/-- 0/-- 4/-- 0/-- 0/-- 0/-- 0/-- 9/0
42 GukGuk
Institut Teknologi Bandung
0 0 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/-- 0/0
42 illuminati
Binus University
0 0 2/-- 0/-- 0/-- 14/-- 3/-- 0/-- 0/-- 0/-- 19/0
42 lionheartz
Binus University
0 0 3/-- 0/-- 0/-- 2/-- 0/-- 0/-- 0/-- 0/-- 5/0
42 lumine
Universitas Atma Jaya Yogyakarta
0 0 1/-- 0/-- 0/-- 7/-- 0/-- 1/-- 0/-- 0/-- 9/0
42 SWING
STMIK Mikroskil
0 0 0/-- 0/-- 0/-- 5/-- 0/-- 0/-- 0/-- 0/-- 5/0
42 ubaya4
Universitas Surabaya
0 0 0/-- 0/-- 0/-- 9/-- 0/-- 0/-- 8/-- 0/-- 17/0
42 WONGDESO
STMIK Mikroskil
0 0 0/-- 0/-- 0/-- 6/-- 0/-- 0/-- 4/-- 0/-- 10/0
Total (attempt/solved) 28/1 0/0 10/1 162/41 59/12 65/2 152/17 3/0 479/74

Statistic - Babak Final

Statistic dibawah ini berasal dari data yang dikumpulkan oleh Suhendry Effendy di blog nya.


Submissions

ProblemSubmissionAccepted
C/C++JavaTotalC/C++JavaTotalRate
A1612281013.57%
B0000000%
C1001010110.00%
D1412716832104225.00%
E481260841220.00%
F5015652023.08%
G130221521431711.18%
H3030000%
Total3988848658177515.43%


Rejected Submissions

ReasonC/C++JavaTotal
Presentation Error (PE)011
Wrong Answer (WA)18736223
Run-time Error (RTE)34943
Time-limit Exceed (TLE)11423137
Compile Error (CE)527


Number of Problem Solved

SolveTeams
8 problems0 teams
7 problems0 teams
6 problems0 teams
5 problems1 teams
4 problems1 teams
3 problems7 teams
2 problems12 teams
1 problems20 teams
0 problems8 teams
Name:  Message:
Pembahasan | Soal

Problem A - Superstitious Skylab Tower

Diberikan sebuah bilangan k. Carilah berapa banyak bilangan yang tidak memiliki angka 4 ataupun 13 (sebagai substring) dari 1 sampai k. Kalikan hasilnya dengan h. Hal yang perlu diperhatikan adalah k bisa mencapai 1012. Komputer juri (dan komputer peserta lainnya maupun komputer pada umumnya) hanya sanggup memprocess sekitar 10 juta operasi dalam 1 second. Karena time limitnya adalah 3 seconds, maka algoritma untuk soal ini haruslah jauh dibawah O(k). Kalau anda loop dari 1 sampai k, dipastikan dapat TLE.

Soal ini mirip dengan soal final E di INC 2007 yang jawabannya adalah menggunakan rekursi dengan complexitas O(digit2). Bisa aja sih di bikin O(digit), tetapi tidak perlu karena jumlah digit sudah sangat kecil (< 10). Ironisnya, orang yang memberitahu saya tentang algoritma ini tahun lalu malah gak AC di soal ini :P.

Soal ini tidak lebih sulit dari soal final E INC 2007 dan solusinya pun jauh lebih pendek. Tetapi soal ini memiliki perbedaan yang cukup membuat pusing para peserta. Yaitu angka "13" merupakan dua digit terpisah (1 dan 3). Solusinya akan jauh lebih mudah jika tidak ada angka sial ini :P.

Sebelum bisa mendapatkan jawaban dalam O(digit^2), dibutuhkan tabel Dynamic Programming yang berisikan hasil pre-calculate jumlah bilangan. States apa sajakah yang diperlukan dalam DP nya dan bagaimana cara mengisi tabel DP nya?

DP states yang dipakai adalah dp[first][length] dimana first menyatakan digit pertama dan length adalah panjang bilangan. Value dari dp[first][length] adalah banyaknya cara untuk membentuk bilangan-bilangan dengan panjang length dimana digit pertamanya adalah first (dengan mengabaikan digit 4 dan substring digit 13). Untuk mengisi tabel DP, rumus berikut digunakan:

  • Untuk semua first = [0..9] dan length = 1, dp[first][length] = 1
  • Untuk semua first = [0..9] dan length = [1..12] dimana first bukan angka 4, maka dp[first][length] = sum( dp[digit][length-1] ) dimana digit = [0..9] dan digit != 4 dan (first != 1 atau digit != 3).
Untuk lebih jelasnya, lihat code super.cpp dibawah untuk pengisian tabel dp nya. Jika anda lebih suka berpikir secara Top-Down maka lihatlah source code SuperDPTopDown.java (dp[first][length] equivalent dengan function rec(first,length) untuk top-down approachnya).

Dengan dp[first][length] sudah ter-inisialisasi penuh, kendala selanjutnya adalah bagaimana cara menggunakan DP tersebut? Kita sekarang sudah bisa mengetahui jumlah bilangan dengan panjang length dan digit pertama first hanya dengan lookup value dari tabel dp[first][length]. Pertanyaannya adalah berapa banyak bilangan yang berada dibawah k? Misalkan k = 1983. Maka untuk menghitung banyaknya bilangan dari 1 sampai k adalah dengan menjumlahkan setiap digit dari k dan digit-digit yang dibawahnya beserta panjangnya. Contoh:

digits  first  length  dp[first][length]
------------------------------------------
0xxx      0       3         711
------------------------------------------
10xx      0       2          80
11xx      1       2          71
12xx      2       2          80
15xx      5       2          80
16xx      6       2          80
17xx      7       2          80
18xx      8       2          80
------------------------------------------
190x      0       1           9
191x      1       1           8
192x      2       1           9
193x      3       1           9
195x      5       1           9
196x      6       1           9
197x      7       1           9
------------------------------------------
1980      0       0           1
1981      1       0           1
1982      2       0           1
------------------------------------------
                   TOTAL:  1327
Jadi untuk k = 1983, ada 1327 bilangan yang lebih kecil dari k yang tidak memiliki angka 4 atau 13 didalamnya. Complexitas algoritma diatas adalah O(N2) dimana N adalah panjang digit dari k.

DP diatas bisa di-optimize lebih lanjut dengan hanya menggunakan dp[length][firstIsOne]. Sebenarnya kita hanya perlu tahu apakah first itu adalah angka 1 atau bukan untuk melarang angka 3 sebagai angka selanjutnya. Sehingga DP ini hanya membutuhkan O(N) memory. Code nya dapat dilihat di super-optimized.cpp

super.cpp | super-optimized.cpp | Super.java | SuperDPTopDown.java
#include <stdio.h>
#include <string.h>

#define ok(a,b) (b!=4 && !(a==1 && b==3))

long long dp[10][13], T, h;
char k[100];

int main(){
    for (int F=0; F<10; F++) dp[F][0] = 1;
    for (int L=1; L<13; L++)
        for (int F=0; F<10; F++) if (F!=4) 
            for (int D=0; D<10; D++) if (ok(F,D))
                dp[F][L] += dp[D][L-1];

    scanf("%lld",&T);
    while (T--){
        scanf("%s %lld",k,&h);
        long long floors = 0;
        for (int i=0, L=strlen(k); i<L; i++)
            for (int F=0; F<k[i]-'0'; F++)
                if (ok(i==0?0:k[i-1]-'0',F))
                    floors += dp[F][L-i-1];
        printf("%lld\n",floors * h);
    }
}
#include <stdio.h>
#include <string.h>

long long dp[13][2], x, h, res;
int num[13], len, T;

long long rec(int len, int prev1){
    if (len==0) return 1;
    long long &ret = dp[len][prev1];
    if (ret!=-1) return ret; else ret = 0;
    for (int i=0; i<10; i++)
        if (i!=4 && !(prev1 && i==3))
            ret += rec(len-1, i==1);
    return ret;
}

int main(){
    memset(dp,-1,sizeof(dp));
    for (scanf("%d",&T); T; T--){
        scanf("%lld %lld",&x,&h);
        for (len=0; x; x/=10) num[len++] = x%10;
        for (int i=res=0; i<len; i++)
            for (int F=0; F<num[len-i-1]; F++)
                if (F!=4 && (i==0 || num[len-i]!=1 || F!=3))
                    res += rec(len-i-1, F==1);
        printf("%lld\n",res*h);
    }
}
import java.util.*;

public class Super {
    public static void main(String[] args){
        long[][] dp = new long[10][13];
        for (int F=0; F<10; F++) dp[F][0] = 1;
        for (int L=1; L<13; L++)
            for (int F=0; F<10; F++) if (F!=4) 
                for (int D=0; D<10; D++)
                    if (D!=4 && !(F==1 && D==3))
                        dp[F][L] += dp[D][L-1];

        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while (T-- > 0){
            char[] k = scan.next().toCharArray();
            long floors = 0;
            for (int i=0; i<k.length; i++)
                for (int F=0; F < k[i]-'0'; F++)
                    if (F!=4 && !(i>0 && k[i-1]=='1' && F==3))
                        floors += dp[F][k.length-i-1];
            System.out.println(floors * scan.nextInt());
        }
    }
}
import java.util.*;

public class SuperDPTopDown {
    long[][] memo = new long[10][13];

    long rec(int first, int length){
        if (length==0) return 1;
        if (memo[first][length]!=-1)
            return memo[first][length];

        long ret = 0;
        for (int i=0; i<10; i++)
            if (i!=4 && !(first==1 && i==3))
                ret += rec(i,length-1);
        return memo[first][length] = ret;
    }

    long countFloors(char[] k){
        long floors = 0;
        for (int i=0; i<k.length; i++)
            for (int j=0; j<k[i]-'0'; j++)
                if (j!=4 && !((i>0?k[i-1]-'0':0)==1 && j==3))
                    floors += rec(j,k.length-i-1);
        return floors;
    }

    void solve(){
        for (long[] m : memo) Arrays.fill(m,-1);
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while (T-- > 0){
            long floors = countFloors(scan.next().toCharArray());
            System.out.println(floors * scan.nextInt());
        }
        scan.close();
    }

    public static void main(String[] args){
        new SuperDPTopDown().solve();
    }
}

ACM-ICPC INC 2008 Final Round

Problem A

Superstitious Skylab Tower

Time Limit: 3s

The 21st century has brought exponentially-growing advances to structural engineering, such that by year 2100 there are already many orbital towers (a.k.a. space elevators) with heights reaching thousands of kilometers to the space.

In year 2100 a group of leading scientists from around the world plans to build another such tower as a research station, extending beyond the heights of the geostationary orbit. The floors in the tower will be numbered, starting sequentially from 0. However, many of the scientists were strongly superstitious and therefore they don't want to use floors numbered 4, 13, and any floor which number contains 4 and/or 13 as its substring.

So in order to overcome the problem and make effective use of all the available floors, the developer team has decided to skip such numbers in the floor numbering plan of the new tower. So the floor numbers will go something like this: ..., 3, 5, 6, ..., 12, 15, 16, ...

This decision solved the superstitions problem, yet caused another type of problem. Some of the scientists conduct ultra-high-precision Earth Science research projects and therefore need to know exact height of their observation spots (which can reach very high into the space), given the height of each floor (assumed to be exact and the same for all floors) and the floor number. Your task is to write a program calculating the heights of the floors given such parameters.

Input

The first line of input contains an integer T, the number of test cases follow.

Each case consists of two integers, k (0 <= k <= 1012) the floors which height is requested, and h (0 < h <= 1,000,000) the height for each floor. You may safely assume that all numbers are valid, in other words, do not contain the numbers 4 and/or 13 as its substring which the scientists avoid.

Output

For each test case, print the heights of the floor on a single line.

Sample InputOutput for Sample Input
5
1 3
5 3
15 3
6 888
12 888
3
12
36
4440
9768
Name:  Message:
Pembahasan | Soal

Problem B - Panda Land 5: Panda Programming Language

Diberikan sebuah program yang berisi N buah functions yang telah dideklarasi, banyaknya baris yang ada di function tersebut, dan dependensi function tersebut ke functions lainnya (suatu function A "depend" terhadap function B jika function A memanggil function B sehingga function B harus di-deklarasi sebelum function A). Anda diminta untuk menggeser deklarasi masing-masing function sehingga program keseluruhannya bisa dicompile (semua dependensi terpenuhi). Tetapi setiap kali anda menggeser suatu function ke atas atau ke bawah, anda akan dikenakan cost sebanyak jumlah baris yang dilewati dikalikan dengan jumlah baris di function yang dipindahkan. Pertanyaannya adalah berapakah cost minimum untuk membuat program nya bisa dicompile? Untuk lebih jelasnya silahkan lihat problem statementnya diatas.

Awalnya saya berpikir soal Panda ini lebih sulit dari soal H-Walaweh, tetapi setelah dipikir kembali dan dilihat waktu pengerjaannya, soal Panda lebih mudah dan lebih singkat :). Soal Panda ini adalah soal Dynamic Programming yang hampir selalu pasti keluar di kebanyakan programming contest. Penguasaan DP sudah menjadi keharusan.

DP state untuk problem ini adalah dp[def] yang valuenya adalah cost minimum untuk functions yang sudah terdeklarasi dalam bit-mask def. DP nya berjalan seperti berikut: untuk mengetahui cost minimum dari dp[def], maka kita akan mencoba untuk men-declare function lain yang belum ada di def, dan ambil cost yang paling minimum. Suatu function boleh di-declare jika semua dependensinya terpenuhi (yakni semuanya sudah di declare di def). Untuk DP versi top-downnya bisa dilihat di source code panda.cpp. DP yang straight-forward ini memiliki kompleksitas O(N*N*2N). Ada cara untuk optimisasi pengecekan cost nya sehingga DP nya bisa berjalan dalam O(N*2N). Optimisasi DP ini bisa dilihat di panda-opt.cpp.

DP versi bottom-upnya bisa dilakukan dalam O(N*N*2N) kodenya bisa dilihat di panda-btu.cpp. Untuk meng-optimize DP bottom-up menjadi O(N*2N) diperlukan urutan eksekusi DP nya sesuai hamming weight, codenya dapat dilihat di PandaBTU.java. Penjelasan DP dengan gambar bisa dilihat di website Suhendry untuk problem ini, sang penggemar soal Pandamon ini.


panda.cpp | panda-opt.cpp | Panda.java | panda-btu.cpp O(N*N*2^N) | PandaBTU.java O(N*2^N)
#include <stdio.h>
#include <string.h>

#define MAXN 18

int T,C,F,N,cost[MAXN],conf[MAXN],depend[MAXN];
int memo[1<<MAXN], inf = 100000000;

int rec(int def){
    if (def==(1<<N)-1) return 0;
    int &ret = memo[def];
    if (ret!=-1) return ret; else ret = inf;
    for (int i=0; i<N; i++) if ((def&(1<<i))==0){
        if ((depend[i] & def) != depend[i]) continue;

        int lines = 0;
        for (int j=0; j<N && conf[j]!=i; j++)
            if ((def&(1<<conf[j]))==0) lines += cost[conf[j]];
        int ccost = lines * cost[i] + rec(def | (1<<i));
        if (ccost < ret) ret = ccost;
    }
    return ret;
}

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d",&N);
        for (int i=0; i<N; i++)
            scanf("%d",&cost[i]);

        memset(depend,0,sizeof(depend));
        for (int i=0; i<N; i++)
            for (scanf("%d",&C); C--; ){
                scanf("%d",&F);
                if (i!=F-1) depend[i] |= 1<<(F-1);
            }

        for (int i=0; i<N; i++)
            scanf("%d",&conf[i]), conf[i]--;

        memset(memo,-1,sizeof(memo));
        int res = rec(0);
        printf("%d\n",res==inf? -1 : res);
    }
}
#include <stdio.h>
#include <string.h>

#define MAXN 18

int T,C,F,N,cost[MAXN],conf[MAXN],depend[MAXN];
int memo[1<<MAXN],lines[1<<MAXN], inf = 100000000;

int rec(int def){
    if (def==(1<<N)-1) return 0;
    int &ret = memo[def];
    if (ret!=-1) return ret; else ret = inf;
    for (int i=0; i<N; i++) if ((def&(1<<i))==0){
        if ((depend[i] & def) != depend[i]) continue;
        int moved = lines[(((1<<N)-1)^def) & ((1<<i)-1)];
        int ccost = moved*cost[i] + rec(def|(1<<i));
        if (ccost < ret) ret = ccost;
    }
    return ret;
}

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d",&N);
        for (int i=0; i<N; i++)
            scanf("%d",&cost[i]);

        memset(depend,0,sizeof(depend));
        for (int i=0; i<N; i++)
            for (scanf("%d",&C); C--; ){
                scanf("%d",&F);
                if (i!=F-1) depend[i] |= 1<<(F-1);
            }

        for (int i=0; i<N; i++)
            scanf("%d",&conf[i]), conf[i]--;

        for (int i=0; i<(1<<N); i++){
            int mask = 0, sum = 0;
            for (int j=0; j<N; j++)
                if ((i&(1<<j))!=0){
                    sum += cost[conf[j]];
                    mask |= 1<<conf[j];
                }
            lines[mask] = sum;
        }

        memset(memo,-1,sizeof(memo));
        int res = rec(0);
        printf("%d\n",res==inf? -1 : res);
    }
}
import java.util.*;

public class Panda {
    int[] memo = new int[1<<18];
    int[] cost, conf, depend;
    int N, inf = 100000000;

    int rec(int idx, int def){
        if (idx==N) return 0;
        if (memo[def]!=-1) return memo[def];

        int ret = inf;
        for (int i=0; i<N; i++) if ((def&(1<<i))==0){
            if ((depend[i] & def) != depend[i]) continue;

            int lines = 0;
            for (int j=0; j<N && conf[j]!=i; j++)
                if ((def&(1<<conf[j]))==0) lines += cost[conf[j]];
            ret = Math.min(ret, lines*cost[i]+rec(idx+1,def|(1<<i)));
        }
        return memo[def] = ret;
    }

    void solve(){
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while (T-- > 0){
            N = scan.nextInt();
            cost = new int[N];
            for (int i=0; i<N; i++) cost[i] = scan.nextInt();
            depend = new int[N];
            for (int i=0; i<N; i++)
                for (int C = scan.nextInt(); C-- > 0;){
                    int F = scan.nextInt() - 1;
                    if (i!=F) depend[i] |= 1 << F;
                }
            conf = new int[N];
            for (int i=0; i<N; i++) conf[i] = scan.nextInt()-1;
            Arrays.fill(memo,-1);
            System.out.printf("%d\n",rec(0,0)==inf?-1:rec(0,0));
        }
    }

    public static void main(String[] args){
        new Panda().solve();
    }
}
#include <stdio.h>
#include <string.h>

#define MAXN 18

int T,C,F,n,cost[MAXN],conf[MAXN];
int lines[1<<MAXN][MAXN];
int dp[MAXN+1][1<<MAXN];
int depend[MAXN];
int inf = 100000000;

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d",&n);
        for (int i=0; i<n; i++)
            scanf("%d",&cost[i]);

        memset(depend,0,sizeof(depend));
        for (int i=0; i<n; i++)
            for (scanf("%d",&C); C--; ){
                scanf("%d",&F);
                if (i!=F-1) depend[i] |= 1<<(F-1);
            }

        for (int i=0; i<n; i++)
            scanf("%d",&conf[i]), conf[i]--;

        memset(dp[0], 0, sizeof(dp[0]));
        for (int i=1; i<=n; i++)
            for (int j=0; j<(1<<n); j++)
                dp[i][j] = inf;

        memset(lines,0,sizeof(lines));
        for (int def=0; def<(1<<n); def++)
            for (int i=0; i<n; i++) if ((def&(1<<i))==0)
                for (int j=0; j<n && conf[j]!=i; j++)
                    if ((def&(1<<conf[j]))==0) lines[def][i] += cost[conf[j]];

        for (int idx=0; idx<n; idx++){
            for (int def=0; def<(1<<n); def++) if (dp[idx][def]<inf) {
                for (int i=0; i<n; i++) if ((def&(1<<i))==0 && (depend[i]&def)==depend[i]){
                    int cur = lines[def][i] * cost[i] + dp[idx][def];
                    int &next = dp[idx+1][def|(1<<i)];
                    if (cur < next) next = cur;
                }
            }
        }
                
        int res = dp[n][(1<<n)-1];
        printf("%d\n",res==inf? -1 : res);
    }
}
import java.util.*;

public class PandaBTU {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        for (int T = scan.nextInt(); T > 0; T--){
            int N = scan.nextInt();
            int[] cost = new int[N];
            for (int i=0; i<N; i++)
                cost[i] = scan.nextInt();

            int[] depend = new int[N];
            for (int i=0; i<N; i++)
                for (int C = scan.nextInt(); C-- > 0;){
                    int F = scan.nextInt() - 1;
                    if (i!=F) depend[i] |= 1 << F;
                }

            int[] conf = new int[N];
            for (int i=0; i<N; i++)
                conf[i] = scan.nextInt()-1;

            int[] lines = new int[1<<N];
            for (int i=0; i<(1<<N); i++){
                int mask = 0, sum = 0;
                for (int j=0; j<N; j++)
                    if ((i&(1<<j))!=0){
                        sum += cost[conf[j]];
                        mask |= 1<<conf[j];
                    }
                lines[mask] = sum;
            }

            Integer[] hamming = new Integer[1<<N];
            for (int i=0; i<(1<<N); i++) hamming[i] = i;
            Arrays.sort(hamming, new Comparator<Integer>(){
                public int compare(Integer a, Integer b){
                    return Integer.bitCount(a) - Integer.bitCount(b);
                }
            });

            int[] dp = new int[1<<N];
            int inf = 1000000000;
            Arrays.fill(dp, inf);
            dp[0] = 0;
            for (int def : hamming){
                for (int i=0; i<N; i++) if ((def&(1<<i))==0){
                    if ((depend[i] & def) != depend[i]) continue;
                    int moved = lines[(((1<<N)-1)^def) & ((1<<i)-1)];
                    int ccost = dp[def] + moved*cost[i];
                    dp[def|(1<<i)] = Math.min(dp[def|(1<<i)], ccost);
                }
            }
            int res = dp[(1<<N)-1];
            System.out.printf("%d\n",res==inf?-1:res);
        }
    }
}

ACM-ICPC INC 2008 Final Round

Problem B

Panda Land 5: Panda Programming Language

Time Limit: 5s

Unlike in human world, panda world has only one programming language, it is Panda Programming Language (PPL). This language is developed by Panda Bureau of Technology (PBT), one of the government’s special department.

This language is built based on procedural programming’s rule, so it’s completely possible to create more than one function on a program. Unfortunately, this language lacks of function prototyping ability. That means each function should have been defined before it can called by any other function. Recursive call is allowed in PPL.

Currently PBT is too busy to build that feature. Meanwhile, there’s a certain program that need to be compiled. The programmers wrote that program without taking the function definition sequence in consideration (ie. some functions are not defined before other function that call them). So, they came to human world and found you, the best programmer on earth! They need your help to write a specific program that can rearrange their program so it can be compiled. But they have one more problem, their programming environment are not so friendly as yours, so the total cost of rearrangement should be minimized!

The cost of moving a certain function is calculated by multiplying the number of line of that function to the total number of skipped line. For example, let there’re four functions defined as A, B, C and D (A at the top and D at the bottom) which have 10, 4, 6 and 3 lines respectively. Moving A below D will cost A * (B + C + D) = 10 * (4 + 6 + 3) = 130. Moving D above B (between A and B) will cost D * (C + B) = 3 * (6 + 4) = 30.

Input

The first line of input contains an integer T, the number of test cases follow.

Each case begins with an integer N (1 <= N <= 18), the number of function. The next line contains N integers (1 <= Mi <= 100) representing the number of line for each function i = 1 ... N. The next N lines each will describes ith function dependency. Each line will start with an integer C (0 <= C < N), the number of other function that is called by that ith function. Next will be C integers (1 <= Fj <= N) representing the function which it needs. The last line for each case will contains N integers representing be the initial function definition.

Output

For each case, print in a single line the minimum cost needed to rearrange that program so it can be compiled, or print "-1" if there’s no such arrangement.

Sample InputOutput for Sample Input
2
4
7 3 12 8
1 3
1 4
2 1 3
0
1 2 3 4
5
7 3 12 8 4
3 1 2 4
0
1 2
0
1 4
1 2 3 4 5
-1
161
Name:  Message:
Pembahasan | Soal

Problem C - Almost Clear

Diberikan dua buah convex polygon A dan B dan sebuah titik X. Tentukan apakah polygon A bisa terlihat dari titix X? Kalau polygon A tidak terhalang sama sekali oleh polygon B (dilihat dari titik X), maka print "CLEAR". Kalau polygon A terhalang sepenuhnya oleh polygon B maka print "NO VISION". Jika bukan kedua kasus diatas maka print "ALMOST CLEAR".

Semua koordinat yang diberikan adalah berupa bilangan bulat, sehingga tidak perlu takut akan precission-error. Hal yang perlu diperhatikan adalah jumlah titik di masing-masing polygon bisa sebanyak 1000 titik, dan jumlah testcase ada 1000. Artinya, diperlukan algoritma dengan kompleksitas kurang dari O(N2) untuk dapat memecahkan soal ini. Kalau maksa dengan algo O(N2), maka dipastikan dapat TLE :D

Kalau kita analisa lebih dalam, soal ini bisa "disederhanakan" dari Polygon menjadi Garis. Bila kita melihat sebuah polygon dari titik X. Kita cukup mengambil titik paling kiri dan paling kanan dari polygon tersebut (dilihat dari titik X). Di dalam soal diberitahu bahwa polygon A dan polygon B tidak akan intersect dan titik X berada di luar polygon. Perhatikan gambar berikut:

 

Gambar 1: Menyederhanakan problem dari bentuk Polygon (gambar kiri) menjadi bentuk Garis (gambar kanan).

Jika anda setuju dengan analisis diatas (jika tidak, bisa tulis alasannya di chatbox di kanan-atas halaman ini), maka permasalahan selanjutnya adalah bagaimana mencari titik paling kiri dan titik paling kanan dari sebuah polygon dengan titik X sebagai titik acuan (kamera)? Cara yang paling mudah adalah dengan test "belok-kiri" atau "belok-kanan". Misalkan kita ingin mencari titik paling kiri dari sebuah polygon dilihat dari titik X. Maka pertama-tama, tentukan titik sembarang di polygon sebagai titik paling kiri (sebut saja titik L), lalu untuk titik lainnya (sebut saja P), test apakah X-L-P belok-kiri? kalau iya, maka titik P berada di sebelah kiri titik L dipandang dari titik X. Maka update-lah titik P sebagai titik paling kiri L, dan cari titik lainnya di polygon sampai habis. Cara ini cuma memerlukan O(N) steps dimana N adalah jumlah titik di polygon. Cara yang sama bisa dilakukan untuk mencari titik paling kanan.

Untuk mengetahui apakah titik-titik A-B-C belok kiri, kita bisa menghitung determinant dari 3 titik tersebut dan hasilnya harus lebih besar dari nol. Jadi rumusnya adalah: ((A.x*B.y + B.x*C.y + C.x*A.y - A.y*B.x - B.y*C.x - C.y*A.x) > 0).

Sekarang kita sudah bisa mencari titik paling kiri dan kanan dari sebuah polygon menurut titik acuan X. Sehingga sekarang kita sudah bisa mengubah Polygon menjadi Garis (seperti Gambar 1 diatas). Polygon A diubah menjadi sebuah garis P-Q dan polygon B diubah menjadi sebuah garis R-S. Langkah selanjutnya tinggal menentukan apakah garis P-Q tertutup oleh garis R-S dari pandangan titik X?

Hanya ada 3 output: "NO VISION", "CLEAR", atau "ALMOST CLEAR". Bekerja dengan garis (2 titik) jauh lebih cepat daripada bekerja dengan polygon (banyak titik). Kondisi-kondisi apa-sajakah yang akan menghasilkan "NO VISION", "CLEAR", atau "ALMOST CLEAR"? Untuk lebih jelasnya, lihat gambar dibawah:



Gambar 2: Print "NO VISION" jika kedua titik P dan Q ada di area dengan background gray.
Print "CLEAR" jika kedua titik P dan Q berada di area kuning atau cyan.
Print "ALMOST CLEAR" jika kedua kondisi diatas gagal.

Jika kedua titik P dan Q berada di area gray, maka dipastikan polygon A semua tertutup oleh polygon B sehingga outputnya adalah "NO VISION". Untuk mengetahui apakah sebuah titik Y berada di area gray, kita tinggal test X-R-Y harus belok kanan, X-S-Y harus belok kiri, R-S-Y harus belok kiri. Dengan begini kita bisa cek apakah P dan Q berada di area gray atau tidak. Jika ya, maka print "NO VISION" dan selesai.

Jika kedua titik P dan Q berada di area kuning atau cyan, maka dipastikan polygon A tidak terhalang oleh polygon B sehingga outputnya adalah "CLEAR". Untuk mengetahui apakah sebuah titik Y berada di area cyan kita tinggal test X-R-Y harus belok kiri atau X-S-Y harus belok kanan. Untuk mengetahui apakah sebuah titik Y berada di area kuning, maka tinggal test R-S-Y harus belok kanan. Dengan ini kita bisa cek apakah kedua titik P dan Q berada di area cyan atau kuning. Jika ya, maka print "CLEAR" dan selesai.

Jika bukan "NO VISION" ataupun "CLEAR", maka tidak usah pusing lagi, jawabannya pasti "ALMOST CLEAR" :D.

poly.cpp | Poly.java
#include <stdio.h>

struct Point { long long x,y; };
Point A[1000], B[1000], X;
int nA, nB, T, aL, aR, bL, bR;

// return true jika a-b-c belok kiri, false jika bukan
#define left(a,b,c) ((a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x) > 0)

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d",&nA); for (int i=0; i<nA; i++) scanf("%d %d",&A[i].x,&A[i].y);
        scanf("%d",&nB); for (int i=0; i<nB; i++) scanf("%d %d",&B[i].x,&B[i].y);
        scanf("%d %d",&X.x,&X.y);

        aL = aR = bL = bR = 0;     // pilih titik 0 sebagai titik paling kiri/kanan
        for (int i=0; i<nA; i++){
            if (left(X,A[aL],A[i])) aL = i;  // update titik paling kiri polygon A
            if (!left(X,A[aR],A[i])) aR = i; // update titik paling kanan polygon A
        }
        for (int i=0; i<nB; i++){
            if (left(X,B[bL],B[i])) bL = i;  // update titik paling kiri polygon B
            if (!left(X,B[bR],B[i])) bR = i; // update titik paling kanan polygon B
        }

        Point P=A[aL], Q=A[aR], R=B[bL], S=B[bR]; // P,Q,R,S didefinisikan diatas

        bool gray = !left(X,R,P) && left(X,S,Q) && left(R,S,P) && left(R,S,Q);
        bool cyan = left(X,R,Q) || !left(X,S,P);
        bool kuning = !left(R,S,P) && !left(R,S,Q);

        if (gray){
            puts("NO VISION");
        } else if (cyan || kuning){
            puts("CLEAR");
        } else {
            puts("ALMOST CLEAR");
        }
    }
}
import java.util.*;

public class Poly {
    class Point { long x,y; }

    // return true jika a-b-c belok kiri, false jika bukan
    boolean left(Point a, Point b, Point c){
        return (a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x) > 0;
    }

    void solve(){
        Scanner scan = new Scanner(System.in);
        for (int T = scan.nextInt(); T > 0; T--){
            Point[] A = new Point[scan.nextInt()];
            for (int i=0; i<A.length; i++){
                A[i] = new Point();
                A[i].x = scan.nextInt();
                A[i].y = scan.nextInt();
            }
            Point[] B = new Point[scan.nextInt()];
            for (int i=0; i<B.length; i++){
                B[i] = new Point();
                B[i].x = scan.nextInt();
                B[i].y = scan.nextInt();
            }
            Point X = new Point();
            X.x = scan.nextInt();
            X.y = scan.nextInt();

            int aL=0,aR=0,bL=0,bR=0;   // pilih titik 0 sebagai titik paling kiri/kanan
            for (int i=0; i<A.length; i++){
                if (left(X,A[aL],A[i])) aL = i;  // update titik paling kiri polygon A
                if (!left(X,A[aR],A[i])) aR = i; // update titik paling kanan polygon A
            }
            for (int i=0; i<B.length; i++){
                if (left(X,B[bL],B[i])) bL = i;  // update titik paling kiri polygon B
                if (!left(X,B[bR],B[i])) bR = i; // update titik paling kanan polygon B
            }

            Point P=A[aL], Q=A[aR], R=B[bL], S=B[bR]; // P,Q,R,S didefinisikan diatas

            boolean gray = !left(X,R,P) && left(X,S,Q) && left(R,S,P) && left(R,S,Q);
            boolean cyan = left(X,R,Q) || !left(X,S,P);
            boolean kuning = !left(R,S,P) && !left(R,S,Q);

            if (gray){
                System.out.println("NO VISION");
            } else if (cyan || kuning){
                System.out.println("CLEAR");
            } else {
                System.out.println("ALMOST CLEAR");
            }
        }
    }

    public static void main(String[] args){
        new Poly().solve();
    }
}

ACM-ICPC INC 2008 Final Round

Problem C

Almost Clear

Time Limit: 5s

In ACM (Awkward Commodity Museum), like every other museum, collects many valuable objects from every place around the globe, therefore several surveillance cameras are installed to watch over the museum for possible unauthorized access. In order to assure maximum surveillance, Mr. Effendy as the Head Security of ACM proposed such layout that all valuable objects being displayed must be visible from one of the cameras.

In ACM, Mr. Halim from the QCD (Quality Control Department) is in charge to verify the layout Mr. Effendy proposed. Usually he develops program to help him do the verifying process, but he is currently busy helping some public forum to understand about Binary Search Tree and the likes of which a programmer like you should already mastered. You should help Mr. Halim before he’s fired because stealing company’s hour to do things irrelevant to his position.

Mr. Halim is asked to write a program that accepts a layout, and verify that all valuable objects are visible by at least one of the camera installed. You must help him! Mr. Halim is a very brilliant guy; he doesn’t require you to write a complete solution. Write a program that receives 3 parameters: polygon A, polygon B, point C and determine whether polygon A (the valuable object) is “hidden” by polygon B (other object) when a camera is installed at point C. Note that your program is only need to deal with these 3 objects and nothing more, Mr. Halim will do the rest.

You may safely assume that:
  1. Your program deals in 2-D coordinates.
  2. Polygon A and B is convex.
  3. The camera has infinite vision (meaning that it can see an object very far away).
  4. The camera can rotate 360 degrees freely.
  5. The camera cannot move.
  6. All position will be valid. Polygons do not intersect each other; camera will not be inside any of the polygons.
  7. All the characters and events described above are fictional. Any similarity of names of the characters and events is partially accidentally. No polygons were harmed during the making of this problem.

Input

The first line of input contains an integer T (1 <= T <= 1,000), the number of test cases follow.

Each case begins with an integer M1 (1 <= M1 <= 1,000), the number of vertices of polygon A, and then followed by M1 integer-pairs which are the X-coordinate and Y-coordinate of each vertex in counter-clockwise direction. The second line will be the description of polygon B in the same format and constraint as the description of polygon A. The third line will be 2 integers which are the X-coordinate and Y-coordinate of the camera respectively. All coordinates will be non-negative and fit in 31-bit integer.

Output

Output for each test case will be in one line. Print "CLEAR" if polygon A is not obstructed by polygon B at all, print "ALMOST CLEAR" if polygon A is obstructed partially by polygon B, or print "NO VISION" if polygon A is fully hidden by polygon B.

Sample InputOutput for Sample Input
3
3 5 23 24 23 16 36
4 0 10 5 10 5 20 0 20
0 0
4 22 53 34 53 34 63 22 63
4 18 31 38 31 38 46 18 46
26 0
4 36 38 48 38 48 48 36 48
4 28 16 51 16 51 30 28 30
20 57
ALMOST CLEAR
NO VISION
CLEAR
Name:  Message:
Pembahasan | Soal

Problem D - Eat or Be Eaten

Diberikan dua buah himpunan bilangan A berisikan M buah bilangan dan B berisikan N buah bilangan, tentukan berapa banyak pasangan bilangan (a,b) dimana a adalah anggota dari himpunan A dan b adalah anggota dari himpunan B dimana a lebih besar daripada b.

Hal yang perlu diperhatikan adalah besarnya M dan N bisa mencapai 20,000. Banyak peserta yang menggunakan cara brute-force O(M*N) dimana membutuhkan sekitar 400 juta kali pengecekan. Cara ini tidak efisien dan akan mendapat TLE. Cara yang lebih efisien adalah dengan mengurutkan dahulu bilangan-bilangan di himpunan A dan B dengan kompleksitas O(N log N + M log M) atau bisa disederhanakan menjadi O(N log N). Setelah bilangan-bilangan di himpunan A dan B sudah terurut, maka kita bisa menentukan berapa banyak pasangan (a,b) hanya dengan O(N + M). Sehingga kompleksitas total dari solusinya adalah O(N log N). Untuk lebih jelasnya lihat code dibawah.

eat.c | eat.cpp | Eat.java
#include <stdio.h>
#include <stdlib.h>

int intcmp(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}

int T,N,M,A[20000],B[20000];

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d %d",&N,&M);
        for (int i=0; i<N; i++) scanf("%d",&A[i]);
        for (int i=0; i<M; i++) scanf("%d",&B[i]);
        qsort(A,N,sizeof(int),intcmp);
        qsort(B,M,sizeof(int),intcmp);

        int total = 0;
        while (N>0 && M>0){
            if (A[N-1] > B[M-1])
                total += M, N--;
            else
                M--;
        }
        printf("%d\n",total);
    }
}
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int T,N,M;

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d %d",&N,&M);
        vector<int> A(N), B(M);
        for (int i=0; i<N; i++) scanf("%d",&A[i]);
        for (int i=0; i<M; i++) scanf("%d",&B[i]);
        sort(A.begin(),A.end());
        sort(B.begin(),B.end());

        int total = 0;
        while (N>0 && M>0){
            if (A[N-1] > B[M-1])
                total += M, N--;
            else
                M--;
        }
        printf("%d\n",total);
    }
}
import java.util.*;

public class Eat {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        for (int T = scan.nextInt(), N, M; T-- > 0; ){
            int[] A = new int[N = scan.nextInt()];
            int[] B = new int[M = scan.nextInt()];
            for (int i=0; i<N; i++) A[i] = scan.nextInt();
            for (int i=0; i<M; i++) B[i] = scan.nextInt();
            Arrays.sort(A);
            Arrays.sort(B);

            int total = 0;
            while (N>0 && M>0){
                if (A[N-1] > B[M-1]){
                    total += M;
                    N--;
                } else {
                    M--;
                }
            }
            System.out.println(total);
        }
    }
}

ACM-ICPC INC 2008 Final Round

Problem D

Eat or Be Eaten

Time Limit: 3s

Deep down under the sea, there’re two kinds of living organism, let’s say A and B. A is B’s predator, but A will only eat B if and only if its size is strictly bigger than its prey. For example, let the size of A = {8, 1, 7, 3, 1} and B = {3, 6, 1}, then there are 7 pairs of A – B where A > B: 8 – 3, 8 – 6, 8 – 1, 7 – 3, 7 – 6, 7 – 1, 3 – 1.


Given the size of each organism in A and B, write a program to count how many pair of A - B are there such that A is strictly bigger than B. Your program should be efficient as the number of organism may be large.


Input

The first line of input contains an integer T, the number of test cases follow.

Each case will begin with two integers N (1 <= N <= 20,000) and M (1 <= M <= 20,000), denoting the number of organism A and B respectively. The next line will contain N positive integers represent the size of each A organism. The third line will contain M positive integers represent the size of each B organism.

Output

For each case, print on a single line the number of pair A – B such that A is strictly larger than B.

Sample InputOutput for Sample Input
2
5 3
8 1 7 3 1
3 6 1
3 4
2 13 7
103 11 290 215
7
1
Name:  Message:
Pembahasan | Soal

Problem E - Indomie

Satu hal kita sehati... Indomie... :D (ada di iklan Indomie di sebelah kanan :D). Awalnya problem ini bukan problem Indomie, tapi sebuah problem aneh untuk menghitung probabilitas. Akhirnya pas lagi laper dan bikin Indomie, jadi kepikir untuk membuat cerita tentang Indomie :D (kok jadi curhat). Ok, kembali ke pembahasan.

Soal ini menanyakan berapakah probability Felix mendapatkan Indomie dalam suatu antrian jika Indomie yang tersisa adalah S dan ada N orang di depan Felix yang sedang mengantri. Selain Indomie, ada 2 items lainnya (beras dan gula) yang cukup untuk semua orang. Ini adalah soal kombinatorik yang bisa diselesaikan dengan rumus kombinatorik maupun dengan Dynamic Programming.

Kombinatorik

Secara kombinatorik, probability Felix mendapatkan Indomie adalah total kombinasi Felix mendapat Indomie dibagi dengan total kemungkinan distribusi Indomie. Felix mendapatkan Indomie kalau N orang di depannya hanya mengambil maksimal (S-1) Indomie. Untuk menghitung jumlah kombinasi pengambilannya, tinggal menggunakan rumus nCk(N,S-1) * 2N-(S-1) dimana fungsi nCk(n,k) adalah banyaknya cara mengambil k items dari n items. Untuk menghitung total semua kemungkinan distribusi Indomie adalah dengan menjumlahkan penghitungan kombinasi pengambilan dengan jumlah Indomie 0 sampai S dengan menggunakan rumus yang sama diatas. Untuk lebih jelasnya, lihat code indomie-comb.cpp dibawah.

Dynamic Programming

Secara Dynamic Programming sebenarnya lebih gampang. Tidak perlu tahu rumus kombinasi diatas untuk menyelesaikannya :). Yang perlu diketahui adalah "state" DP nya. Dalam kasus ini state nya adalah dp[N][S] yang menyatakan berapa banyak kombinasi pengambilan Indomie untuk N orang di depan Felix dan S Indomie yang tersisa. Sehingga jawabannya bisa didapat dengan menghitung dp[N][S-1] (total pengambilan dimana Felix masih mendapat Indomie) dibagi dengan dp[N][S] (total pengambilan untuk semua Indomie). Kita tidak perlu menggunakan rumus canggih seperti kombinatorik diatas, tetapi cukup menggunakan formula DP sebagai berikut:

  • dp[0][i] = 1 untuk semua i = [1..S].
  • dp[i][j] = 2*dp[i-1][j] + dp[i-1][j-1] untuk i>0 dan j=[0..S].
Untuk lebih jelasnya, lihatlah source code indomie-dp.cpp dibawah. Darimanakah formula diatas diciptakan? Saya tidak bisa berpikir ala bottom-up seperti diatas. Yang pertama kali saya buat adalah versi top-down (lihat kode indomie-dp-topdown.cpp dibawah). Dari recurrence inilah saya baru bisa membuat versi bottom-up-nya. Versi topdown nya sangat mudah, hampir sama dengan apa yang diceritakan di soal. Saya akan ajarkan cara berpikir untuk membuat dp-topdown. Awalnya kita ingin mengetahui dp[N][S], anggap anda berada di queue paling depan, maka anda punya pilihan sebagai berikut:
  1. Ambil gula, state DP nya menjadi dp[N-1][S]. (anda keluar dari queue dan jumlah Indomie tetap S).
  2. Ambil beras, state DP nya menjadi dp[N-1][S]. (anda keluar dari queue dan jumlah Indomie tetap S).
  3. Ambil Indomie, state DP nya menjadi dp[N-1][S-1]. (anda keluar dari queue dan jumlah Indomie berkurang 1).
Dengan demikian, dp[N][S] itu bisa dihitung dengan menjumlahkan semua pilihan kombinasi diatas: dp[N][S] = 2*dp[N-1][S] + dp[N-1][S-1]. Dari sanalah tercipta rumus DP tersebut. Mudah seperti membaca soal bukan? Tidak perlu keahlian khusus untuk ini.

Sekilas tentang Dynamic Programming

Dynamic Programming adalah cara universal untuk memecahkan masalah yang memiliki sub-problem seperti diatas. Banyak sekali soal programming contest yang bisa diselesaikan dengan DP jika anda mengetahui statenya. Untuk mengetahui state DP nya diperlukan analisa dan cara berpikir yang lumayan kompleks. Jika anda sudah menguasai Dynamic Programming, kemungkinan anda sukses di programming contest besar sekali (seperti Andrian Kurniady, sang champion INC 2007 dan INC 2008).

Kesalahan Umum

Banyak yang mendapatkan Wrong Answer karena menggunakan tipe data int maupun long long. Sebab penghitungan ini terlalu besar untuk ditampung didalam tipe data int maupun long long. Beberapa peserta yang menggunakan Java, menggunakan tipe data BigInteger untuk mengatasi masalah overflow ini tetapi sebenarnya cukup dengan tipe data double. Jika anda lihat spesifikasi soal, anda diminta hanya mengeluarkan 7 digit (Jika si Felix lebih paranoid lagi, butuh 100 digit maka double tidak mempan :P). Tipe data double dengan pintarnya bisa menampung 7 digit tanpa overflow sehingga tetap akurat asal exponentnya tidak melebihi batasan double (sekitar 300 digits). Ini spesifikasi tipe data double:

Double variables are stored as signed IEEE 64-bit (8-byte) double-precision floating-point numbers ranging in value from -1.79769313486231570E+308 through -4.94065645841246544E-324 for negative values and from 4.94065645841246544E-324 through 1.79769313486231570E+308 for positive values.
Jadi selama penghitungan anda tidak melebihi 300 digit, penggunaan tipe data double akan akurat-akurat saja untuk 7 digit pertama. Untuk digit ke 8 dan seterusnya mungkin bisa terjadi sedikit kesalahan dan jika exponentnya sudah ratusan, kesalahan kecil di digit ke 8 artinya kesalahan super besar! Untuk soal Indomie, karena kita hanya butuh 7 digit pertama maka kesalahan di digit ke 8 gak ngefek :D.

Soal Indomie ini sebenarnya memiliki kesalahan, sehingga jawabannya sebenarnya bukan seperti diatas. Melainkan lebih kompleks. Alasannya terdapat di After Thought sectionnya pembahasan Suhendry. Kode kombinatorik Suhendry untuk problem ini lebih efisien, lihat codenya di indomie-shu.cpp.

indomie-comb.cpp | indomie-shu.cpp | indomie-dp.cpp | indomie-dp-topdown.cpp | Indomie.java
#include <stdio.h>
#include <math.h>

// returns nCk(N,S) * 2^(N-S)
double calc(int N, int S){
    double nCk = 1.0;
    for (int i=1; i<=S; i++) nCk *= (N-i+1.0) / i;
    return nCk * pow(2.0,N-S);
}

int main(){
    for (int N,S; scanf("%d %d",&N,&S)!=EOF; ){
        if (S>N){
            puts("100.00000");
        } else {
            double total = 0, gak_dapet = calc(N,S);
            for (int i=0; i<=S; i++) total += calc(N,i);
            double dapet = total - gak_dapet;
            printf("%.5lf\n",100.0*dapet/total);
        }
    }
}
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
    int n, s;
    while ( scanf( "%d %d", &n, &s ) == 2 ) {
        double x = pow(2.0, n - s);
        for ( int i = 1; i <= s; i++ )
            x *= (double)(n - i + 1)/i;

        double b = pow(2.0, n), v = 1, w = 1;
        for ( int i = 1; i <= s; i++ ) {
            v *= n - i + 1; w *= i;
            b += pow(2.0, n - i) * v / w;
        }
        printf( "%.5lf\n", (b - x) * 100.0 / b );
    }
    return 0;
}
#include <stdio.h>

int main(){
    double dp[52][52];

    for (int i=0; i<52; i++) dp[0][i] = 1.0;
    
    for (int i=1; i<52; i++)
        for (int j=0; j<52; j++)
            dp[i][j] = 2*dp[i-1][j] + (j>0?dp[i-1][j-1]:0);

    for (int N, S; scanf("%d %d",&N,&S)!=EOF; )
        printf("%.5f\n",100.0*dp[N][S-1]/dp[N][S]);
}
#include <stdio.h>
#include <string.h>

double dp[52][52];
char vis[52][52];

double rec(int N, int S){
    if (N<0 || S<0) return 0;
    if (N==0) return 1;
    if (vis[N][S]) return dp[N][S]; else vis[N][S] = 1;
    return dp[N][S] = 2*rec(N-1,S) + rec(N-1,S-1);
}

int main(){
    for (int N,S; scanf("%d %d",&N,&S)!=EOF; ){
        memset(vis,0,sizeof(vis));
        printf("%.5lf\n", 100.0 * rec(N,S-1) / rec(N,S));
    }
}
import java.util.*;

public class Indomie {
    public static void main(String[] args){
        double[][] dp = new double[52][52];
        for (int i=1; i<52; i++) dp[0][i] = 1.0;
        for (int i=1; i<52; i++)
            for (int j=1; j<52; j++)
                dp[i][j] = 2*dp[i-1][j] + dp[i-1][j-1];

        // dp[i][j] digeser menjadi dp[i][j+1]
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextInt()){
            int N = scan.nextInt(), S = scan.nextInt();
            System.out.printf("%.5f\n",100.0*dp[N][S]/dp[N][S+1]);
        }
    }
}

ACM-ICPC INC 2008 Final Round

Problem E

Indomie

Time Limit: 3s

During recession, Felix needs to queue for SembakoPlus. Sembako, as we all know, stands for “Sembilan Bahan Pokok” which consists of 9 kinds of item: Rice, Sugar, Cooking-oil, Meat, Egg, Milk, Corn, Kerosene and Iodized Salt. SembakoPlus consists of Sembako and one more item: Indomie! Felix’s favorite of all time!! (therefore, no wonder why he could stand for this long queue)

Each person in the queue is allowed to pick only one item. No need to ask, Felix wants only Indomie. Unfortunately, they are running out of SembakoPlus stock and currently there are three kinds of item left: Rice, Sugar and Indomie. As he could see from afar, he is quite sure that Rice and Sugar will be enough for everybody.

Given the number of remaining Indomie and the number of people queuing in front of Felix, your task is to count the probability that he will get his Indomie. Felix can’t do programming right now as he is very nervous so he can’t think logically. He needs your help!


Input

There will be multiple test cases for this problem. Each test case contains two integers N (1 <= N <= 50) and S (0 <= S <= 50), where N is the number of people queuing in front of Felix and S is the remaining number of Indomie.

Output

For each case, print in a single line the probability in percentage that he will get his Indomie with 5 digits precision (he’s being paranoid).

Sample InputOutput for Sample Input
2 1
3 2
4 0
4 1
10 10
14 9
30 14
50.00000
76.92308
0.00000
33.33333
99.99831
98.65515
95.16071

Explanation for 1st sample test case:
There are two peoples queuing in front of Felix, so those two peoples could pick of the following combination {1st people, 2nd people}:
1. Rice, Rice
2. Rice, Sugar
3. Rice, Indomie
4. Sugar, Rice
5. Sugar, Sugar
6. Sugar, Indomie
7. Indomie, Rice
8. Indomie, Sugar

Since there is only one Indomie left, there are only 4 out of 8 combinations that ensure Felix to get his Indomie (1, 2, 4 and 5), hence the probability is 4/8 = 50%.

Name:  Message:
Pembahasan | Soal

Problem F - In Queries

Awalnya, tim juri ingin membuat soal ini lebih sulit lagi dengan menggunakan Segment Tree, tetapi karena keterbatasan waktu soal ini sepertinya dipermudah menjadi counting-sort biasa. FYI, Segment Tree pernah dibahas dengan gencar di milis JUG :P

Diberikan sebuah database dengan 5 kolom dan 100,000 row. Ada 5 operasi yang bisa dilakukan terhadap database ini:

  • Menambahkan 1 row ke baris paling akhir
  • Remove row ke-r (dimana row tersebut dianggap tidak ada, tanpa menggeser row lainnya)
  • Mencari nilai maximum dari column tertentu
  • Mencari nilai minimum dari column tertentu
  • Mencari berapa jumlah row yang memiliki value antara a dan b di kolom c.
Kunci untuk menyelesaikan problem ini adalah dengan membuat suatu tabel yang berfungsi sebagai counting-sort untuk masing masing kolom dan meng-update tabel tersebut jika ada data baru atau data lama yang dibuang. Dengan menggunakan tabel ini, kita bisa menjawab query hanya dengan O(M) dimana M adalah modulo dari value yang ada di setiap cell. Sehingga kompleksitas total untuk menyelesaikan problem ini adalah O(N + Q*M) dimana N adalah jumlah row pada awalnya, Q adalah jumlah query dan M adalah besarnya modulo. Untuk lebih jelasnya, lihat code dibawah.

query.cpp | Query.java
#include <stdio.h>
#include <string.h>

#define MAXV 10000
#define MAXR 101000
#define MAXC 5

char op[10], rem[MAXR];
int col[MAXC][MAXV+1];
int data[MAXR][MAXC];
int T,a,b,x,m,n;

int main(){
    scanf("%d",&T);
    for (int TC=1; TC<=T; TC++){
        printf("Case #%d:\n",TC);
        scanf("%d %d %d %d %d",&a,&b,&x,&m,&n);
        memset(data,0,sizeof(data));
        memset(rem,0,sizeof(rem));
        memset(col,0,sizeof(col));
        for (int r=0; r<n; r++)
            for (int c=0; c<MAXC; c++){
                long long v1 = (long long) a * (r==0?0:data[r-1][c]);
                long long v2 = (long long) b * (c==0?0:data[r][c-1]);
                data[r][c] = (v1 + v2 + x) % m;
                col[c][data[r][c]]++;
            }

        int q,r,c;
        scanf("%d",&q);
        while (q-- > 0){
            scanf("%s",op);
            if (op[0]=='i'){
                for (c=0; c<MAXC; c++){
                    scanf("%d",&data[n][c]);
                    col[c][data[n][c]]++;
                }
                n++;
            } else if (op[1]=='e'){
                scanf("%d",&r); r--;
                if (r<0 || r>=n || rem[r]) continue;
                for (c=0; c<MAXC; c++) col[c][data[r][c]]--;
                rem[r] = 1;
            } else if (op[2]=='x'){
                scanf("%d",&c); c--;
                for (int v=MAXV; v>=0; v--)
                    if (col[c][v]){ printf("%d\n",v); break; }
            } else if (op[1]=='i'){
                scanf("%d",&c); c--;
                for (int v=0; v<=MAXV; v++)
                    if (col[c][v]){ printf("%d\n",v); break; }
            } else {
                scanf("%d %d %d",&c,&a,&b); c--;
                int cnt = 0;
                for (int v=a; v<=b; v++) cnt += col[c][v];
                printf("%d\n",cnt);
            }
        }
    }
}
import java.util.*;

public class Query {
    public static void main(String[] args){
        final int MAXV = 10000, MAXR = 100100, MAXC = 5;
        boolean[] rem = new boolean[MAXR];
        int[][] col = new int[MAXC][MAXV+1];
        int[][] arr = new int[MAXR][MAXC];

        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        for (int TC=1; TC<=T; TC++){
            System.out.printf("Case #%d:\n",TC);

            int a = scan.nextInt();
            int b = scan.nextInt();
            int x = scan.nextInt();
            int m = scan.nextInt();
            int n = scan.nextInt();
            Arrays.fill(rem,false);
            for (int[] c : col) Arrays.fill(c,0);

            for (int r=0; r<n; r++)
                for (int c=0; c<MAXC; c++){
                    long v1 = (long) a * (r==0?0:arr[r-1][c]);
                    long v2 = (long) b * (c==0?0:arr[r][c-1]);
                    arr[r][c] = (int) ((v1 + v2 + x) % m);
                    col[c][arr[r][c]]++;
                }

            int q = scan.nextInt();
            while (q-- > 0){
                String op = scan.next();
                if (op.charAt(0)=='i'){
                    for (int c=0; c<MAXC; c++){
                        arr[n][c] = scan.nextInt();
                        col[c][arr[n][c]]++;
                    }
                    n++;
                } else if (op.charAt(1)=='e'){
                    int r = scan.nextInt() - 1;
                    if (r<0 || r>=n || rem[r]) continue;
                    for (int c=0; c<MAXC; c++) col[c][arr[r][c]]--;
                    rem[r] = true;
                } else if (op.charAt(2)=='x'){
                    int c = scan.nextInt() - 1;
                    for (int v=MAXV; v>=0; v--) if (col[c][v]>0){
                        System.out.printf("%d\n",v); break; }
                } else if (op.charAt(1)=='i'){
                    int c = scan.nextInt() - 1;
                    for (int v=0; v<=MAXV; v++) if (col[c][v]>0){
                        System.out.printf("%d\n",v); break; }
                } else {
                    int c = scan.nextInt() - 1;
                    int L = scan.nextInt();
                    int R = scan.nextInt();
                    int cnt = 0;
                    for (int v=L; v<=R; v++) cnt += col[c][v];
                    System.out.printf("%d\n",cnt);
                }
            }
        }
    }
}

ACM-ICPC INC 2008 Final Round

Problem F

In Queries

Time Limit: 3s

Currenty ITComSysSC (Information Technology Computer System Student Club) needs to develop a software module which able to handle some query on data, and here they come to ask you. All the data will be integer and stored in a table of 5 columns. For the development purpose, you will use the initial data which are generated by this function:

f(r, c) = (a . f(r – 1, c) + b . f(r, c – 1) + x) mod m
f(r, c ) = 0, for all r = 0 or c = 0.
f(r, c) = the value on row r and column c, where r = 1 ... n, and c = 1 ... 5.

a, b, x, m and n are seeds for the function and will be given as input.

Here are the queries that you should handle:
QueryTo DoExample
insert a b c d eappend {a, b, c, d, e} to the last row. a = data for 1st column, b = data for 2nd column, ..., e = data for 5th column (0 <= a, b, c, d, e < m).insert 2 10 3 4 7
remove rdelete row r.remove 3
max coutput the highest value in column c.max 3
min coutput the lowest value in column c.min 1
range c a boutput the number of row which value in column c between a and b (inclusive).range 2 1 10

Each time a remove command is executed, the specified row will be deleted but all other rows below it will not be shifted (which means the row still there, only the data is emptied). If the row to be removed is already deleted/empty or out of range, then do nothing. Insert command will always append the data to the last row, even if there’re empty rows before it (deleted rows).

You may safely assume that there’s no output query (max/min/range) on empty table.

Input

The first line of input contains an integer T, the number of test cases follow.

Each case begins with five non-negative integers a, b, x, m (1 <= m <= 10,000) and n (0 <= n <= 100,000) the seed for generating the initial data. The next row contains a single integer q (0 <= q <= 100) denoting the number of queries. The next q lines each represents the query in one of the above formats.

Output

Print "Case #X:" (X is the case number) at the first line of each test case. The following lines will be the output of the test case (each output on a single line).

Sample InputOutput for Sample Input
3
1 1 1 5 6
9
max 5
remove 2
remove 4
min 2
insert 2 4 6 3 10
range 4 1 5
insert 0 0 0 0 0
remove 7
max 3
3 3 3 3 3
2
remove 1
insert 1 1 1 1 1
2 4 3 10 2
6
remove 1
remove 2
insert 2 2 2 2 2
remove 1
remove 10
max 3
Case #1:
1
0
4
4
Case #2:
Case #3:
2
Name:  Message:
Pembahasan | Soal

Problem G - Hotel

Diberikan N hotel dan M tim, anda diminta untuk memilih sebuah hotel untuk masing-masing tim dimana hotel tersebut sesuai dengan permintaan tim tersebut dan mempunyai harga termurah. Keluarkan output harga dari hotel dan nama hotel tersebut. Jika tidak ada hotel seperti itu, maka keluarkan output "no-hotel".

Soal ini dapat dikerjakan langsung seperti yang diminta soal: untuk setiap tim pilihlah hotel terbaik buat mereka. Kompleksitasnya adalah O(N*M). Untuk lebih jelasnya, lihat source code dibawah.

hotel.cpp | Hotel.java
#include <stdio.h>

struct Hotel {
    int bedSize, roomCapacity, nAvailable, roomPrice;
    char name[30];
};

Hotel hs[51];
int T, nH, nT;

int main(){
    scanf("%d",&T);
    for (int TC=1; TC<=T; TC++){
        printf("Case #%d:\n",TC);
        scanf("%d %d",&nH,&nT);
        
        for (int i=0; i<nH; i++){
            scanf("%d",&hs[i].bedSize);
            scanf("%d",&hs[i].roomCapacity);
            scanf("%d",&hs[i].nAvailable);
            scanf("%d",&hs[i].roomPrice);
            scanf("%s",hs[i].name);
        }

        for (int i=0; i<nT; i++){
            char type[10];
            int nPeople, maxPerson;
            scanf("%s %d %d",type,&nPeople,&maxPerson);

            int totalCost = 1000000000, bedSize, suggestedHotel = -1;
            for (int j=0; j<nH; j++){
                int nPersonPerRoom = hs[j].roomCapacity;
                if (nPersonPerRoom > maxPerson) nPersonPerRoom = maxPerson;
                int nRoom = (nPeople + nPersonPerRoom - 1) / nPersonPerRoom;
                if (nRoom > hs[j].nAvailable) continue;

                int range[] = { 0, 35, 48, 62 };
                int idx = type[0]-'A';
                int min = range[idx] + 1;
                int max = range[idx + 1];
                if (hs[j].bedSize < min || max < hs[j].bedSize) continue;

                int price = nRoom * hs[j].roomPrice;
                if (price > totalCost) continue;
                if (price == totalCost && hs[j].bedSize <= bedSize) continue;

                totalCost = price;
                bedSize = hs[j].bedSize;
                suggestedHotel = j;
            }
            
            if (suggestedHotel != -1)
                printf("%d %s\n",totalCost,hs[suggestedHotel].name);
            else
                puts("no-hotel");
        }
    }
}
import java.util.*;

public class Hotel {
    int bedSize, roomCapacity, nAvailable, roomPrice;
    String name;

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        for (int TC=1; TC<=T; TC++){
            System.out.printf("Case #%d:\n",TC);

            int nH = scan.nextInt();
            int nT = scan.nextInt();
            
            Hotel[] hs = new Hotel[nH];
            for (int i=0; i<nH; i++){
                hs[i] = new Hotel();
                hs[i].bedSize = scan.nextInt();
                hs[i].roomCapacity = scan.nextInt();
                hs[i].nAvailable = scan.nextInt();
                hs[i].roomPrice = scan.nextInt();
                hs[i].name = scan.next();
            }

            for (int i=0; i<nT; i++){
                String type = scan.next();
                int nPeople = scan.nextInt();
                int maxPerson = scan.nextInt();

                String suggestedHotel = "no-hotel";
                int totalCost = Integer.MAX_VALUE;
                int bedSize = Integer.MIN_VALUE;
                for (int j=0; j<nH; j++){
                    int nPersonPerRoom = Math.min(maxPerson, hs[j].roomCapacity);
                    int nRoom = (nPeople + nPersonPerRoom - 1) / nPersonPerRoom;
                    if (nRoom > hs[j].nAvailable) continue;

                    int[] range = new int[]{ 0, 35, 48, 62 };
                    int idx = type.charAt(0)-'A';
                    int min = range[idx] + 1;
                    int max = range[idx + 1];
                    if (hs[j].bedSize < min || max < hs[j].bedSize) continue;

                    int price = nRoom * hs[j].roomPrice;
                    if (price > totalCost) continue;
                    if (price == totalCost && hs[j].bedSize <= bedSize) continue;

                    totalCost = price;
                    bedSize = hs[j].bedSize;
                    suggestedHotel = hs[j].name;
                }
                
                if (totalCost < Integer.MAX_VALUE)
                    System.out.printf("%d ",totalCost);
                System.out.println(suggestedHotel);
            }
        }
    }
}

ACM-ICPC INC 2008 Final Round

Problem G

Hotel

Time Limit: 3s

Indonesia tourism board has just sent a list of available room type of all hotels in Jakarta for teams that will participate in Indonesia Programming Contest 2008. Each record on the list contains:
  1. Hotel name (max. 25 char, alphabet only).
  2. Bed size (20 – 62).
  3. Room capacity (1 – 4).
  4. Number of available room (1 – 50).
  5. Cost per room (1 – 5,000).
To simplify the problem, let’s assume that each hotel will offer only one type of room (which means they will appear only once in the list).
Several participants have submitted their hotel preference to the committee, which consists of:
  • Prefered bed size, grouped into three categories:
    • Type A: bed size 20 – 35
    • Type B: bed size 36 – 48
    • Type C: bed size 49 - 62
  • Number of people in their teams (1 – 200).
  • Maximum number of person in a room (1 – 4). The number of people in each room will be limited to this number even if the room has more capacity.

Based on the data above, write a program to find the cheapest hotel for each team. If there’re more than one cheapest hotels, then choose one with largest bed size. If there’re still more than one, then choose one which come first on the list.

You don’t have to worry about multiple teams assigned at one hotel. What we will do here is only make a suggestion for each team, not a reservation.


Input

The first line of input contains an integer T, the number of test cases follow.

Each case will begin with two integers N (1 <= N <= 50) and M (1 <= M <= 50) the number of available hotel and the number of teams respectively. The next N lines each will contains four integers (bed size, room capacity, number of available room and the price per room) and a string which denotes the hotel’s name. The next M lines each will contains three data: bed size type (A, B or C), number of people in their teams and maximum number of person in a room.

Output

Print "Case #X:" (X is the case number) at the first line of each test case. For each team, print on a single line the total cost and the hotel name which you suggested (in the same order as the team appearance in the input), separated by a single space. If there’re no hotels that match the team’s criteria, then output “no-hotel” (without quotes).

Sample InputOutput for Sample Input
2
2 3
40 3 2 10 MyHotel
37 4 5 50 HisHotel
B 5 3
A 3 4
B 7 2
4 2
30 2 5 10 IndigoHotel
35 2 5 10 PurpleHotel
36 2 5 10 GreenHotel
36 2 5 10 BrownHotel
A 6 2
B 6 2
Case #1:
20 MyHotel
no-hotel
200 HisHotel
Case #2:
30 PurpleHotel
30 GreenHotel
Name:  Message:
Pembahasan | Soal

Problem H - Walaweh

Nama soal ini adalah "Walaweh". Saya tidak tahu darimana kata tersebut berasal, tapi saya sering orang mengatakan "walaweh... blabla *keluhan* blablabla...". Darisana kata "walaweh" atau mungkin "wallaweh" kira-kira adalah kata yang dipakai untuk meng-ekspresikan keluhan terhadap sesuatu. Begitu pula yang akan terjadi jika ada peserta yang mencoba menjawab problem ini :D. Mereka akhirnya akan mengatakan "walaweh!!" :P. Karena problem ini adalah problem yang menurut saya paling memakan waktu, entah dari segi pengertian soal maupun segi pengerjaan soal.

Soal ini sebenarnya terdiri dari dua permasalahan terpisah. Masalah pertama adalah mengubah sequence number menjadi walaweh number, dan masalah kedua adalah mengubah dari walaweh number ke sequence number. Dan dua permasalahan ini tidak terkait satu sama lain (independent). Jadi sebenarnya bobotnya harusnya adalah 2 soal (tetapi mereka digabung menjadi 1 soal :D). Rugilah bagi mereka yang mengerjakan soal ini. Tetapi sepertinya para peserta cukup jeli untuk tidak membuat soal ini :), hanya 2 tim yang mencoba menyelesaikannya di menit-menit terakhir.

Soal ini diperkirakan waktu pengerjaannya kira-kira adalah satu sampai dua jam untuk orang yang lumayan menguasai rekursi dan matematika. Untuk pengerjaannya pun harus dengan penuh konsentrasi dan ketelitian. Semakin tidak teliti, semakin lama waktu pengerjaannya :). Jika having a good day, mungkin sekali bikin recurrencenya langsung bener, who knows.

Untuk mengubah dari sequence number dengan length L dan urutan ke-N, bisa dilakukan dengan recurrence sebagai berikut:

function wal(L, N){
    if (L==1) return N
    H = 2L-1
    kasus = (L-2) % 8
    if (kasus == 0) return (N<H)? (wal(L-1,N)+"0") : (wal(L-1,N-H)+"1");
    if (kasus == 1) return (N<H)? ("0"+wal(L-1,N)) : ("1"+wal(L-1,N-H));
    if (kasus == 2) return (N<H)? (wal(L-1,N)+"1") : (wal(L-1,N-H)+"0");
    if (kasus == 3) return (N<H)? ("1"+wal(L-1,N)) : ("0"+wal(L-1,N-H));
    if (kasus == 4) return (N<H)? (wal(L-1,N)+"0") : (wal(L-1,H-(N-H)-1)+"1");
    if (kasus == 5) return (N<H)? ("0"+wal(L-1,N)) : ("1"+wal(L-1,H-(N-H)-1));
    if (kasus == 6) return (N<H)? (wal(L-1,N)+"1") : (wal(L-1,H-(N-H)-1)+"0");
    if (kasus == 7) return (N<H)? ("1"+wal(L-1,N)) : ("0"+wal(L-1,H-(N-H)-1));
    return "impossible";
}
Untuk kasus 0 sampai 3 masih mudah, tetapi untuk kasus 4 sampai 7 dibutuhkan analisa lebih dalam karena adanya reverse list tetapi itu bukan masalah jika anda sudah paham benar akan cara kerjanya. Hanya dibutuhkan pengecekan intensive terhadap hasil jawaban :D (pengecekan ini yang membuang waktu lama). Jika anda mendapatkan fungsi rekursinya langsung benar maka akan cepat, jika tidak maka debuggingnya akan lama sekali (kemungkinan harus mengecek output satu persatu dari 1 sampai 256 -> karena cyclenya adalah 8 maka akan berulang setelah 2^8 steps -> banyak sekali bukan :P).

Sebaliknya, untuk mengubah dari walaweh number menjadi sequence number (hanya mencari urutan ke-N), juga dapat dilakukan dengan fungsi recurrence sebagai berikut:

// s adalah walaweh number, i dan j adalah batas kiri dan batas kanan
function seq(s,i,j){
    if (i==j) return s[i];
    N = 2(j-i)
    kasus = (j-i-1) % 8;
    if (kasus == 0) return (s[j]=='0')? seq(s,i,j-1) : (N + seq(s,i,j-1));
    if (kasus == 1) return (s[i]=='0')? seq(s,i+1,j) : (N + seq(s,i+1,j));
    if (kasus == 2) return (s[j]=='1')? seq(s,i,j-1) : (N + seq(s,i,j-1));
    if (kasus == 3) return (s[i]=='1')? seq(s,i+1,j) : (N + seq(s,i+1,j));

    ret = 0;
    if (kasus == 4){ ret = seq(s,i,j-1); if (s[j]=='1') ret = N-ret-1 + N; }
    if (kasus == 5){ ret = seq(s,i+1,j); if (s[i]=='1') ret = N-ret-1 + N; }
    if (kasus == 6){ ret = seq(s,i,j-1); if (s[j]=='0') ret = N-ret-1 + N; }
    if (kasus == 7){ ret = seq(s,i+1,j); if (s[i]=='0') ret = N-ret-1 + N; }
    return ret;
}
Recurrence ini dan recurrence sebelumnya sama sekali bertolak belakang, seperti dua soal terpisah :) Walaweh!

Recurrence diatas bisa didapatkan hanya dengan intuisi dan kemampuan analisa yang baik. Saya sendiri juga bingung bagaimana mejelaskannya supaya dapat recurrence diatas :P.

walaweh.cpp | Walaweh.java
#include <stdio.h>
#include <string.h>
#include <string>

using namespace std;

char s[100];
long long N;
int L;

string wal(int L, long long N){
    if (L==1) return string(1,(char)('0'+N));
    long long H = 1LL << (L-1);
    switch ((L-2)%8){
        case 0: return (N<H)? (wal(L-1,N)+"0") : (wal(L-1,N-H)+"1");
        case 1: return (N<H)? ("0"+wal(L-1,N)) : ("1"+wal(L-1,N-H));
        case 2: return (N<H)? (wal(L-1,N)+"1") : (wal(L-1,N-H)+"0");
        case 3: return (N<H)? ("1"+wal(L-1,N)) : ("0"+wal(L-1,N-H));
        case 4: return (N<H)? (wal(L-1,N)+"0") : (wal(L-1,H-(N-H)-1)+"1");
        case 5: return (N<H)? ("0"+wal(L-1,N)) : ("1"+wal(L-1,H-(N-H)-1));
        case 6: return (N<H)? (wal(L-1,N)+"1") : (wal(L-1,H-(N-H)-1)+"0");
        case 7: return (N<H)? ("1"+wal(L-1,N)) : ("0"+wal(L-1,H-(N-H)-1));
    }
    return "error";
}

long long seq(char *s, int i, int j){
    if (i==j) return s[i]-'0';
    long long N = 1LL << (j-i), ret = 0, add = 0;
    switch ((j-i-1)%8){
        case 0 : return (s[j]=='0')? seq(s,i,j-1) : (N + seq(s,i,j-1));
        case 1 : return (s[i]=='0')? seq(s,i+1,j) : (N + seq(s,i+1,j));
        case 2 : return (s[j]=='1')? seq(s,i,j-1) : (N + seq(s,i,j-1));
        case 3 : return (s[i]=='1')? seq(s,i+1,j) : (N + seq(s,i+1,j));
        case 4 : ret = seq(s,i,j-1); if (s[j]=='1') ret = N-ret-1 + N; break;
        case 5 : ret = seq(s,i+1,j); if (s[i]=='1') ret = N-ret-1 + N; break;
        case 6 : ret = seq(s,i,j-1); if (s[j]=='0') ret = N-ret-1 + N; break;
        case 7 : ret = seq(s,i+1,j); if (s[i]=='0') ret = N-ret-1 + N; break;
    }
    return ret;
}

int main(){
    while (scanf("%s",s)!=EOF){
        if (s[0]=='W'){
            scanf("%d %lld",&L,&N);
            printf("%s\n",wal(L, N-1).c_str());
        } else {
            scanf("%s",s);
            printf("%lld\n",seq(s,0,strlen(s)-1)+1);
        }
    }
}
import java.util.*;
import java.io.*;

public class Walaweh {
    String wal(int L, long N){
        if (L==1) return ""+N;
        long H = 1L << (L-1);
        switch ((L-2)%8){
            case 0: return (N<H)? (wal(L-1,N)+"0") : (wal(L-1,N-H)+"1");
            case 1: return (N<H)? ("0"+wal(L-1,N)) : ("1"+wal(L-1,N-H));
            case 2: return (N<H)? (wal(L-1,N)+"1") : (wal(L-1,N-H)+"0");
            case 3: return (N<H)? ("1"+wal(L-1,N)) : ("0"+wal(L-1,N-H));
            case 4: return (N<H)? (wal(L-1,N)+"0") : (wal(L-1,H-(N-H)-1)+"1");
            case 5: return (N<H)? ("0"+wal(L-1,N)) : ("1"+wal(L-1,H-(N-H)-1));
            case 6: return (N<H)? (wal(L-1,N)+"1") : (wal(L-1,H-(N-H)-1)+"0");
            case 7: return (N<H)? ("1"+wal(L-1,N)) : ("0"+wal(L-1,H-(N-H)-1));
        }
        return "error";
    }

    long seq(String S, int i, int j){
        if (i==j) return S.charAt(i)-'0';
        long N = 1L << (j-i), ret = 0, add = 0;
        switch ((j-i-1)%8){
            case 0 : return (S.charAt(j)=='0')? seq(S,i,j-1) : (N + seq(S,i,j-1));
            case 1 : return (S.charAt(i)=='0')? seq(S,i+1,j) : (N + seq(S,i+1,j));
            case 2 : return (S.charAt(j)=='1')? seq(S,i,j-1) : (N + seq(S,i,j-1));
            case 3 : return (S.charAt(i)=='1')? seq(S,i+1,j) : (N + seq(S,i+1,j));
            case 4 : ret = seq(S,i,j-1); if (S.charAt(j)=='1') ret = N-ret-1 + N; break;
            case 5 : ret = seq(S,i+1,j); if (S.charAt(i)=='1') ret = N-ret-1 + N; break;
            case 6 : ret = seq(S,i,j-1); if (S.charAt(j)=='0') ret = N-ret-1 + N; break;
            case 7 : ret = seq(S,i+1,j); if (S.charAt(i)=='0') ret = N-ret-1 + N; break;
        }
        return ret;
    }

    void solve() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (String line; (line = br.readLine())!=null; ){
            String[] s = line.split(" ");
            if (s[0].charAt(0)=='W'){
                int L = Integer.parseInt(s[1]);
                long N = Long.parseLong(s[2]);
                bw.write(wal(L, N-1) + "\n");
            } else {
                bw.write((seq(s[1],0,s[1].length()-1)+1) + "\n");
            }
        }
        br.close();
        bw.close();
    }

    public static void main(String[] args) throws Exception {
        new Walaweh().solve();
    }
}

ACM-ICPC INC 2008 Final Round

Problem H

Walaweh

Time Limit: 8s

Walaweh number is a numbering sequence that is so troublesome (that's exactly where it gets its name, "Walaweh!"). Walaweh number is similar to binary number (only consist of zeros and ones) except that the length of the number is important (thus leading zeros are preserved). Note that the "length" of Walaweh numbers means the number of digits in the Walaweh numbers.

To simplify the wording, Walaweh numbers of length L will be written as WL, which denotes all Walaweh numbers with exactly L digits. Walaweh numbers (of any length) is an ordered list of numbers. The most basic (smallest) Walaweh numbers is W1 which are "0" and "1" in that order. WL can be generated from WL-1 except for W1 which is fixed. This is done by creating two clones (C1 and C2) of WL-1 then apply some operations (see below) on C1 and C2 to produce C1' and C2'. The combined list of numbers in C1' followed by the list of numbers in C2' (in that order) produces WL.

These are the 8 possible operations on C1 and C2:

  1. Append a digit zero to the end of all numbers in C1 and append a digit one to the end of all numbers in C2.
  2. Append a digit zero to the beginning of all numbers in C1 and append a digit one to the beginning of all numbers in C2.
  3. Append a digit one to the end of all numbers in C1 and append a digit zero to the end of all numbers in C2.
  4. Append a digit one to the beginning of all numbers in C1 and append a digit zero to the beginning of all numbers in C2.
  5. Reverse the order of the list of numbers in C2 and do operation 1 above.
  6. Reverse the order of the list of numbers in C2 and do operation 2 above.
  7. Reverse the order of the list of numbers in C2 and do operation 3 above.
  8. Reverse the order of the list of numbers in C2 and do operation 4 above.

W1 is fixed. W2 is generated by applying the first operation on W1. W3 is generated by applying the second operation on W2 and so on... and it will go back to the first operation again after the eighth operation. So, W9 is generated by applying the eighth operation on W8. W10 is generated by applying the first operation on W9 and so on... Walaweh!

Below is the list of W1, W2, W3, and W4 :

Walaweh LengthSequence NumberWalaweh Numbers
11.0
12.1
 
21.00
22.10
23.01
24.11
 
31.000
32.010
33.001
34.011
35.100
36.110
37.101
38.111
Walaweh LengthSequence NumberWalaweh Numbers
41.0001
42.0101
43.0011
44.0111
45.1001
46.1101
47.1011
48.1111
49.0000
410.0100
411.0010
412.0110
413.1000
414.1100
415.1010
416.1110

To give you an idea of "reverse the order of the list of numbers in C2" for the fifth to eighth operations, we give the last 5 numbers of W6 :

Walaweh LengthSequence NumberWalaweh Numbers
660.110011
661.101111
662.100111
663.101011
664.100011

Your job is to convert from Walaweh Length + Sequence Number into Walaweh Number and vice versa.

Input

There are multiple input, each on a line by itself. The line will either begin with the word "Walaweh" then followed by an integer number L < 64 and N < 2L or begin with the word "Sequence" then followed by a binary representation of the Walaweh number with length < 64.

Output

For input line that begins with "Walaweh" you have to output the N'th Walaweh number of length L. For those lines that begins with "Sequence" you have to output the Sequence number of the given Walaweh number (The length of the Walaweh number is already obvious from the input).

Sample Input

Walaweh 1 1
Walaweh 3 6
Walaweh 4 13
Sequence 1100
Walaweh 5 14
Sequence 1110
Sequence 01010
Walaweh 6 1
Walaweh 6 20
Walaweh 6 32
Sequence 100101
Walaweh 6 40
Walaweh 6 64
Walaweh 7 29
Sequence 0000001
Walaweh 7 100
Walaweh 15 1984
Sequence 00100101010001
Sequence 100101010001001001001001
Walaweh 20 38299
Walaweh 40 38294828288
Sequence 10100010001001001001
Walaweh 63 78487827863828368
Sequence 000011100010101010010100010010010101001001001011001010001001001

Sample Output

0
110
1000
14
11100
16
31
100010
001110
011100
54
000001
100011
0010000
40
1010000
011011000111110
10018
6619354
01101010001001010001
0101001011111100010001001010000001000001
350619
010000110001110011110100010111111001000111000100111100101100010
2769960758748826002


Foto-foto INC 2008

Comment untuk fotonya bisa langsung di website picasa.
Foto-foto pemenang bisa lihat di sini.
Foto-foto pilihan lihat disini.


© Felix Halim 2009 (Loaded in 0.17820 secs)