Felix Halim .NET |  |

| Enter your search terms Submit search form

Story | Research | Programming | Scripts | Member | Miscellaneous

2008-06-29 20:18:05 Felix Halim> Hallo semua, silahkan ketik saran/kritik atau apapun disini :) 2008-07-02 08:59:32 Timotius Sakti> Cerita dan pembahasannya keren banget Felix ^^, btw g juga baru tau kalo Kur juga difoto dengan gaya seperti itu, padahal sebelumnya ngga janjian :))
2008-07-04 04:44:47 Felix J> @timo, berarti saudara sehati tapi gk seortu :P habisnya tanpa janjian bs persis gitu... hahahahaha... piss... ^o^v
2008-07-04 10:01:27 Timotius Sakti> @Felix J: Hahaha, kalo bajunya emang ud janjian :p
2008-07-04 12:44:37 si_kupluk> mas felix fotonya ga semua team ad ya? perasaan pas contest ad di-foto team =D
2008-07-04 20:38:36 Felix Halim> hmm.. yang foto tim kamu itu panitia apa orang lain? :) Panitia kyny cuman sekedar foto-foto suasana :D, gak ada sesi khusus untuk foto tim sih... Mungkin INC tahun depan mao diambilin foto tim satu-satu? :D biar saling kenal :)
2008-07-04 21:55:07 elyi> iya tuh,,,harusnya semua tim di foto tuh. Biar ada kenangan gtu + sling kenal.
2008-09-24 20:48:40 fitri> nyasarr
2008-11-06 00:54:32 orange> kapan lomba coding lagi..??
2008-11-06 00:54:35 orange> kapan lomba coding lagi..??
2008-11-06 00:54:37 orange> kapan lomba coding lagi..??
2008-11-06 00:54:37 orange> kapan lomba coding lagi..??
2008-11-07 20:07:34 Felix Halim> BNPC HS 2008 nanti Desember ini
2008-12-27 09:56:27 ghjkhgfdyfrtyy> gjfjlyyy rutfuki
2009-02-09 18:51:03 cyco> go GPL..!!! loh salah ya?
2009-06-21 02:16:56 Green> Kapan pra ACM/ICPC diadakan?
2009-06-21 03:23:17 Felix Halim> Denger2 sih bakal deket2 regional contestnya. Gak tau tanggal tepatnya.

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
1 | UMN A | Ambrosius Alvin Gunawan/Yunky Hower/Harry Indra Koswanto
2 | UMN B | Marcel Bonar Kristanda/FX. William Riyanto/Dicky Hartono
3 | UMN C | Marco Hudaya/Dimaz Mahendra Budi/Antony
Universitas Pelita Harapan
1 | kulikoding | Dwika Putra/Christoforus Yoga Haryanto/William
Binus University
1 | Phoenix | David Pratama Lumban Tobing/Johanes/Lie Albert Januar Linarco
2 | TSP | Timotius Sakti/Stephen Kohar/Pascal Gerardus Angriawan
3 | acmon | Eko Wibowo/Lie Gunawan/Cun Cun Lim
4 | kurniady | Andrian Kurniady/Fiona Liausvia/Purnama
5 | hidden | Stef/Cuncuna smile/Eko Ari Wibowo
6 | Spirit4ac | Indra/James Natan Wiguna/Denise Harland
7 | Denny_Dj | Suryadi Chandra/Denny Djuarto/Poyuandy
8 | color_ijo | Alfian Arief Phanoto/Davin Pradipta/Jastian Ganaputra
9 | illuminati | Andreas Sanjaya Paiman/Erwin Permata/Garry Bernardy
10 | JGTR | Ong Randy Pratama Joeandy/RIko Nagatama/Ronny Setiawan
11 | pinkpanda | Winardi Kurniawan/Eko Mirhard/Panji Kharisma
12 | wish | Sofia Setjahusada/Indra Gunawan/Willyanto
13 | blueman | Lay Ivan Sulaiman/Heru Prasetia/Novianto Halim
14 | IntMain | William/Ferry Yuwono/Budi Prasetyo
15 | Jimmy | adrianus/jimmy/adryn
16 | adryn | arif/pratama/zulkarnain
17 | adrianus | eric/irvan/ivan
18 | KaaN | Nelson Widjaya/Aloysius Theo Prima/Kristoforus Kevin
19 | lionheartz | Suwandy/Jonathan Sukandi/Kurniawan Suyono
20 | Darc | Anthony Ciputra/Christin/Devina Purwito
Institut Teknologi Sepuluh Nopember
1 | SolidSnake | Aswin Rachmat Pramono/Adhilaras Putro Pamungkas/Achmad Sonif
2 | fortress | Barkhah Pudya Permana/Andre Parvian A/Nela Oktivani
3 | mkning | Ridho Rahman Hariadi/M Abidir Rokhman/Arya Nugraha Nawing
4 | bangkititu | Wimbi Perdana Putra/Eka Gibran Hasany/Kurniawan Haikal
5 | peyipayi | Rindra Parama S.H./Eky Pratama Halim/Rizky Septiandy Wicaksono
6 | eternal | Thariq Nugrohotomo/Decky Kurniawan/Tommy Adhyasa Sumardhana
7 | dreaming | Tovan Setiono/Deneng Eka Putra/Mahardhika Aji S.
8 | senyumdonk | Purnama Anaking/M.Rohmatulloh S/Aditya Saputra
9 | ganbamon | Ratri Dwi Kayungyun/M. Fitrah Muttaqin/Mirza Aulia Rahman
10 | festivals | Wijanarko Sukma Pamungkas/M. Rizky Ramadhan/Andi M. Fahrur Hidayat
11 | coder_cupu | Yohanes Indra Riskajaya/Anang Dista Satria/Dommy Asfiandy
12 | WAR Team | David Agustinus/Ony Octavianto/Anugrah Pratama E
13 | kkgj_tc07 | Jeffrey Hermanto Halimsetiawan/Kemas Dimas R./Gita Ventyana
14 | ECKS-RAY | Ferbianto/Tristanto Khosiawan/Yohanes Khosiawan
15 | deadline | Satriawansyah Urbaya/Mieky Sofyan Yudinata/Charisma Reandrianto
16 | tuwek | Muchamad Agus Romansyah/M. Khairul Habib/Arimas Artadi
17 | buaya_air | Lanang Aditya Nugraha/Ahmad Rifai/Teguh Prasetya
18 | mad | Ardi Imawan/Doni Setio Pambudi/Mario Wahyu Prabowo
19 | aeos | Billy Montolalu/Koharudin/Supriadi
20 | hydrant | Fitra Raditya S./Rizki Akbar M./Ahmad Fuadi
21 | blink182 | Priya Bagus Sasikirono Ramadhan/Vega Prima Sagitara/Firman Rosdiansyah
22 | noname.cpp | Cintaniati Putri/Rahma Mustika Ningrum/Fitri Indra Indikawati
Institut Teknologi Harapan Bangsa
1 | GembelJaya | Angga Muhammad Rahadian/Imanuel Sudiono/Zavero Krishna Wibowo
Institut Teknologi Bandung
1 | GukGuk | Samuel Simon/Dominikus Damas Putranto/Jansen
2 | ASDF | Aris Feryanto/Fanny Limassa/Bernardino Madaharsa Dito A.
3 | Gamer | Eka Permadi Susanto/Firdi Mulia/Praba Iman Prasaja
4 | arihil | Arief Pratama/Muhammad Ihsan/Ilden Abi Neri
5 | K.E.F.S | Kevin Tanadi/Evan/Ferry Mulia
Universitas Kristen Satya Wacana
1 | EMI | Erisman Kriswandhani Lim/Michael Ade Soewondo/Indra Suryatama
2 | fti-uksw | ANDI TARU NUGROHO NW/OMEGA PALGUNO PURNOMO/AGHATA DHIWI ASHITA
3 | xrvel | Dicky Kurniawan/Nelfrit Christopher/Jolly Lengkono
4 | fti-uksw06 | Yongkie Purnomo BudiSaputra/Christina Victoria/Marcel Willem Aipasa
Parahyangan Catholic University
1 | cobahura2 | Felix Chandra S/Andrianto Dwi L/Aditya Nugraha
2 | Gun A Die | Chandra Diharja/William Budianto Sutisno/Hendra Gunadi
3 | HuraHura07 | Christian Indrayana/Suarlin Husni/Elisa
4 | �skill �hq | Idham Yuandi/Yulius Chandra/Felix Samuel Lando
5 | haneki | Hadi Saloko/Nelson Kurniawan/Kikita Yoshehana
6 | Paradoks | Edric Marthanegara/Eldwin Viriya/Dicky Wira Senjaya
7 | unpar12029 | Adrian Darmawan/Michael Yohanes/Jason Ipinsaputra Kurniawan
UIN Syarif Hidayatullah Jakarta
1 | TIC_Ext | Muhamad Qadhavi/Setiajid/Anton Budiwan
2 | bpc_uin1 | Bima Aji Saputro/Muhammad Tri Wibowo/Retno Ayu Widiyaningrum
3 | bpc_uin2 | Heri Nurmanto/Deni Zakya/Yunita
4 | bpc_uin3 | Heru Arya Pratama/Agunahwan A./Putra Angga Anolisa
5 | bpc_uin4 | Afrialdi Syahputra Butar Butar/Annisa Primasari/Morteza Muthahhari
6 | bpc_uin5 | Reza Andy Pradana/Edwin Adhiputra/Ardiansyah
Universitas Nasional PASIM
1 | amat | Amat Miftakhudin/Akhmad Fakhrurrozi/Irman Sulaeman
2 | cyberwitch | Ade Saprudin/Akhmad Yani/Nunuh Nurjaman
Universitas Sumatera Utara
1 | Bonggow | Izhari Ishak Aksa/Ronny P. Silitonga/Jefri Umar
2 | k1r4 | Rizky Zulkarnaen/Fachrurozi Nasution/yuyanto
Universitas Brawijaya
1 | brawijaya | Yanuar Risah Prayogi/Mirza Galih K/Mohammad Azis Fatoni
2 | UB_Team | Ratna Mufidah/Pipit Tunjungsari/Rini Alifah
Universitas Sanata Dharma
1 | code-man | Angela Ami Asmarani/Teresia Esti Seliastuti/Henricus Wahyudi
2 | trnkanBBM | BayuSanjaya/Anna Setiawan/Hertartik Clarasita Devy
3 | USD01 | Fransiskus Anggit/Hendra Christian/Wiliams Andrian
4 | USD02 | Florensius Phangestu/Dony Setiyawan Nugroho/Benidiktus
5 | USD03 | Sari Indah Anatta S./Albertus Dio/Taufik
6 | USD04 | RobinSteven/Kartono Pinaryanto/Alexander Rosyanto
Sekolah Tinggi Sandi Negara
1 | cryptocode | Arief Karfianto/Zaenal Suhardono/Tetra Widianto
Universitas Pendidikan Indonesia
1 | uteuk | Yaya Wihardi/Irvan Riswanto/Winprins
2 | ilkomupi06 | Avionic/Husni Firmansyah/Yopi
Universitas Indonesia
1 | mcntouch | Moehammad Ichsan/Rizki Mardian/Danu Widatama
2 | RTC | Ricky Suryadharma/Teddy/Charles Christian
3 | UI_4 | Ade Saputra/Deni Lukmanul Hakim/Erik Dominikus
4 | jajakajawa | Agung Firmansyah/Bayu Distiawan/Ikhlas Purwanto
Universitas Atma Jaya Yogyakarta
1 | lumine | Ng Elyi Junaidi/Yohanes Novendriono/Erlangga Pradipta Suryanto
2 | ardiansa | Bernadus Ari Nugraha/Christina Dian Hayu Kurniawati/Elisabeth Kurnia Wijayanti
3 | VeRMeL | Bafo Ade Hutiva/Anastasius Triseptian/Bagus Ade Saputra
4 | burjo | Nengsih Fitria/Vidi Valianto Shaweddy/Ridwan Yusuf
5 | cuxed | Hendri/YB Bagus Adityatama/Daphne Eka Jayanti Wesling
Universitas Surabaya
1 | ubaya1 | EDWIN MOCHSIN/RESAN TANAGO/REDEN TANAGO
2 | ubaya2 | PRASETIA GUNAWAN/HARMAN WIJAYA/YOHANES WILLIAM SAMBUDJO
3 | ubaya3 | ANDY SURYA PRANATA/WEE CIANG/BENNY KURNIAWAN SOENARJO
4 | ubaya4 | FX. BAMBANG EKO SANTOSO/ASWIN NIOGROHO/TOMMY ADITYA LAWANTO
5 | ubaya5 | ARIIS PRATAMA SETIABUDI/IVAN WIDJAJA/YULIANTO
6 | ubaya6 | SUSANTO BENNY/HARDI LIMIYANTO/JOHAN KRISTIANTO
7 | L-AC | Cendra Yamin/Dewi Maria/Aris Untung
Petra Christian University
1 | Oct++ | Andy Basuki/Albertus Wonges/Eko Adi Prasetyo Gunawan
2 | EASt | Elizabeth Kwan/Anton Indrawan/Stephanus Surya Jaya
3 | vista | Kiswono Prayogo/Wendy Gunawan/Robin Chandra
4 | "A" | Albert Halim/Adrian Hartanto/Alvin Nathaniel T.
UNIKA Soegijapranata
1 | ikom_06 | Iwan Setiawan/Doni Cahyanto Y./Marcellina Ervina S.
2 | proxie | Rhesa Varian/Hendarta Aditya S/De Rosal Ignatius Moses S
3 | ikom1 | Adi Nugroho/Ong Milo Caturangga Hariyanto/Benny Santoso
STMIK Mikroskil
1 | NEW_BIE | SUWANDI/HENDRA GUNTUR/HENDRIK TANDIONO
2 | WONGDESO | DARWIN KOSASIH/ANDREW JAUHARI/HARTONO
3 | CRYSTAL | DARWIN/SUNARIO MEGAWAN/RICHIE SETIAWAN
4 | SWING | ARWIN HALIM/JHON KEVIN/FENDY
5 | ICE_BOY3 | EIGER YAP/KASIM/ANDY PUTRA
6 | DEBUS | HABRI LOY/HENDRA SUWANDA/ULNI AHMAD PERDANA
Widyatama University
1 | RoyalFlush | Indra Pranatha/Ardhi Beniyanto/Lerry Manggara Putra
2 | frogroot | Teguh akbar/Rizki kalgasi kasim/Andreas Riadi
3 | iteam | Mathofany Boer/Asep Rukmana/Redi Widyawan
Institut Bisnis dan Informatika Indonesia
1 | BISI | Linda Chandra/Shita Novelia/Daniel Stefie
2 | LOW FAT | Josephine/Yogi/Sucipto
STMIK MDP
1 | stmik-mdp | Mohammad Iqbal/Didy Yedidyah Listyarwan/Jonni
Mercu Buana University
1 | fasilkom2 | Dian Wirawan/Fronita/Adi Wahab
2 | fasilkom | Hendra Triyatmaka/Agung Wiseso/Denny Satriyatno
Universitas Budi Luhur
1 | blue01 | Muhamad Haveis Yulindo/Hendro Purnama Sardjono/Febri Wicaksono
2 | blue02 | Shintya Yulianti/Tiharsih/Hairunnisa
3 | blue03 | Abdul Aziz Nur/Rawuh Harsongko/Christine
4 | blue04 | Alfonsius S/Pujianto/Restu Maulunida
Institut Pertanian Bogor
1 | ilkomipb | Wildan Rachman/Indra Juniawan/Ciramudya Adha Gafawidj
Institut Teknologi Telkom
1 | STT01 | Fauzi Aulia Rahman/Karina Fitriani Fatimah/Oscar T. Ardianto
2 | dna_soft | Dody Qori Utama/Alfian Akbar Gozali/Naufal Mikhdzam Ar Rozi
3 | ARTis | Rizky Ario Nugroho/Rindang Septyan/Septian Rani
4 | scratchz | Ali Murtado Fauzarrohman/Sugihartono/Saputra Aries Pratama
Dian Nuswantoro University
1 | vectorcode | Iswahyudi/Agusta Wicaksono/Ahmad Saiful Muhajjir
Universitas Sriwijaya
1 | cyborg | Binahar Agus P/Vebby Madyasari/Yuli Astuti
2 | FADE | Dede Kurniawan/Fikri Heriyanto/Adril Tabrani
3 | CYBER | M. Ali Buchari/Edvin Ramadhan/Aldefvi Roci
4 | DINDAM | Yusrizal Erwansyah/M.Nur Hasyim/Yovi Pratama
Sekolah Tinggi Informatika & Komputer Indonesia
1 | ELANG | Sonny Setiawan/Go Frendi Gunawan/Varin Dwi Saputra
Universitas Kristen Duta Wacana
1 | DUTA | Daniel Susanto/Wilbert/Yoshua Aditya Santoso
2 | WALK | Agustinus Patrisius Suku/Willy Budiman/Kharis Handoko
Universitas Gadjah Mada
1 | username | Wahyono/Riza Oktavian NS/Saifuddin Noor Afifi
2 | aaa | Agung Nugroho/Ardian/Aaron Baratha
Universitas Islam Indonesia
1 | pit-uii | DAYU BAGUS PERMATA/DWIRA MAULANA/BRIMA ARIBOWO
Universitas Kristen Maranatha
1 | TREUKM | Erick Costanio/Tri Chandra/Depenses
2 | Maranatha1 | Melingga Waty/Ade Rusmana/Samuel Christianto
3 | Maranatha2 | Louwy Ayasin/Christian Suhindar/Yulianti
Institut Teknologi Indonesia
1 | HMIF_ITI | A.A.Ayu Mirah Handayani/Rangga Effendi/Mochamad Setiady
Sekolah Tinggi Ilmu Statistik
1 | you | You Ari Faeni/I Gde Agus Arya/Abdurrahman Assel
2 | Arie | Arie Wahyu/Feby Dwi/Aris Prawisudatama
3 | takdir | Takdir/Cahya Al Kahfi/Miswar
4 | anas | Anas/Habi/Sawung
Institut Teknologi Adhi Tama Surabaya
1 | ITATS | MITA ISTINARATI/WAHYUDI KARUNIA TJUATJA/ALEXANDER ADITYA N.
Universitas Pakuan
1 | UNPAK2 | Rudi Yudhistira/Yuly Wati/Adhi Rohmat
2 | UNPAK1 | Syamsuri/Zaenal Abidin/Arizal Coto
Universitas Komputer Indonesia
1 | unikomIF2 | Rully Isma Hidayat/Friko Simanjuntak/Eko Kurniawan Khannedy
2 | unikomIF1 | Yudi Yogaswara/Eko Budi Setiawan/Adam Mukharil Bachtiar
3 | unikomIF3 | Herman Herwansyah/Herdi A/Warman Suganda

# Scoreboard - Hasil Akhir Babak Penyisihan INC 2008

Rank | Team(s) | A | B | C | D | E | Solved | Total Time
--- | --- | --- | --- | --- | --- | --- | --- | ---
1 | TSP Binus University | 2/104 | 3/59 | 3/- | 1/12 | 1/59 | 4 | 294
2 | kurniady Binus University | 6/96 | 3/83 | 4/- | 1/18 | 1/53 | 4 | 390
3 | Gun A Die Parahyangan Catholic University | 2/74 | 3/101 | 6/- | 3/105 | 1/22 | 4 | 402
4 | pinkpanda Binus University | 3/75 | 3/129 | 1/- | 1/41 | 2/68 | 4 | 413
5 | haneki Parahyangan Catholic University | 1/68 | 5/131 | -/- | 3/159 | 3/63 | 4 | 581
6 | K.E.F.S Institut Teknologi Bandung | 3/98 | 1/79 | -/- | 7/144 | 2/112 | 4 | 613
7 | acmon Binus University | 3/93 | 5/- | -/- | 2/48 | 2/40 | 3 | 261
8 | kulikoding Universitas Pelita Harapan | 2/91 | 3/149 | -/- | 1/- | 1/33 | 3 | 333
9 | RTC Universitas Indonesia | 1/128 | 1/80 | -/- | 3/- | 2/177 | 3 | 405
10 | username Universitas Gadjah Mada | 2/102 | 2/- | -/- | 1/177 | 1/110 | 3 | 409
11 | Oct++ Petra Christian University | 1/115 | -/- | -/- | 1/168 | 4/144 | 3 | 487
12 | EMI Universitas Kristen Satya Wacana | 5/- | 6/180 | 1/- | 2/92 | 1/122 | 3 | 514
13 | vista Petra Christian University | 6/150 | 3/143 | -/- | 5/- | 12/166 | 3 | 819
14 | Spirit4ac Binus University | 1/61 | 1/- | -/- | -/- | 1/103 | 2 | 164
15 | lumine Universitas Atma Jaya Yogyakarta | 1/69 | 1/- | -/- | -/- | 2/124 | 2 | 213
16 | GukGuk Institut Teknologi Bandung | 2/- | 5/- | -/- | 2/118 | 1/79 | 2 | 217
17 | UI_4 Universitas Indonesia | 1/123 | 3/- | -/- | 1/- | 1/97 | 2 | 220
18 | eternal Institut Teknologi Sepuluh Nopember | 2/77 | -/- | -/- | -/- | 1/124 | 2 | 221
19 | SWING STMIK Mikroskil | 1/76 | -/- | -/- | 1/176 | -/- | 2 | 252
20 | Phoenix Binus University | 2/- | 10/- | -/- | 2/138 | 1/123 | 2 | 281
21 | �skill �hq Parahyangan Catholic University | 5/- | 6/- | 7/- | 1/129 | 1/173 | 2 | 302
22 | Bonggow Universitas Sumatera Utara | 3/- | -/- | -/- | 2/143 | 3/116 | 2 | 319
23 | mkning Institut Teknologi Sepuluh Nopember | 5/169 | 3/- | -/- | 2/- | 1/74 | 2 | 323
24 | Paradoks Parahyangan Catholic University | 3/- | 4/- | -/- | 3/151 | 1/168 | 2 | 359
25 | illuminati Binus University | 2/112 | 3/- | -/- | 4/- | 5/150 | 2 | 362
26 | cobahura2 Parahyangan Catholic University | 6/- | 1/- | -/- | 1/178 | 4/138 | 2 | 376
27 | EASt Petra Christian University | 8/177 | -/- | 1/- | 1/- | 2/114 | 2 | 451
28 | SolidSnake Institut Teknologi Sepuluh Nopember | 7/- | 2/- | -/- | -/- | 1/50 | 1 | 50
29 | bangkititu Institut Teknologi Sepuluh Nopember | 4/- | 3/- | -/- | 2/- | 1/53 | 1 | 53
30 | senyumdonk Institut Teknologi Sepuluh Nopember | -/- | -/- | -/- | -/- | 1/86 | 1 | 86
31 | fortress Institut Teknologi Sepuluh Nopember | -/- | -/- | -/- | -/- | 1/89 | 1 | 89
32 | unpar12029 Parahyangan Catholic University | 1/- | -/- | -/- | 3/- | 1/94 | 1 | 94
33 | WONGDESO STMIK Mikroskil | -/- | 1/- | 1/- | -/- | 1/113 | 1 | 113
34 | ubaya2 Universitas Surabaya | 3/76 | 2/- | -/- | 5/- | -/- | 1 | 116
35 | ubaya4 Universitas Surabaya | -/- | 2/- | -/- | 4/- | 2/96 | 1 | 116
36 | bpc_uin1 UIN Syarif Hidayatullah Jakarta | -/- | 1/- | -/- | -/- | 1/124 | 1 | 124
37 | bpc_uin4 UIN Syarif Hidayatullah Jakarta | -/- | -/- | -/- | -/- | 1/127 | 1 | 127
38 | ASDF Institut Teknologi Bandung | 3/- | 4/- | -/- | 2/- | 1/129 | 1 | 129
39 | ubaya1 Universitas Surabaya | 2/115 | 1/- | -/- | -/- | -/- | 1 | 135
40 | kkgj_tc07 Institut Teknologi Sepuluh Nopember | 1/- | -/- | -/- | 3/- | 2/117 | 1 | 137
41 | LOW FAT Institut Bisnis dan Informatika Indonesia | 1/148 | 3/- | -/- | 2/- | -/- | 1 | 148
42 | BISI Institut Bisnis dan Informatika Indonesia | 1/153 | -/- | -/- | -/- | -/- | 1 | 153
43 | aaa Universitas Gadjah Mada | -/- | -/- | -/- | -/- | 1/153 | 1 | 153
44 | ilkomipb Institut Pertanian Bogor | -/- | -/- | -/- | 1/- | 1/154 | 1 | 154
45 | UMN A Universitas Multimedia Nusantara | 3/- | 1/- | -/- | 2/- | 1/155 | 1 | 155
46 | mad Institut Teknologi Sepuluh Nopember | 4/- | 7/- | -/- | -/- | 2/163 | 1 | 183
47 | peyipayi Institut Teknologi Sepuluh Nopember | 4/- | -/- | -/- | -/- | 4/146 | 1 | 206
48 | Gamer Institut Teknologi Bandung | 1/- | -/- | -/- | -/- | 3/178 | 1 | 218
49 | wish Binus University | -/- | 7/- | -/- | 5/139 | 4/- | 1 | 219
50 | STT01 Institut Teknologi Telkom | -/- | -/- | -/- | -/- | 4/179 | 1 | 239
51 | HuraHura07 Parahyangan Catholic University | -/- | 7/- | -/- | -/- | 8/141 | 1 | 281
52 | lionheartz Binus University | 6/- | 10/174 | -/- | 9/- | -/- | 1 | 354
53 | UMN C Universitas Multimedia Nusantara | -/- | -/- | 1/- | 2/- | -/- | 0 | 0
54 | vectorcode Dian Nuswantoro University | -/- | 1/- | -/- | -/- | -/- | 0 | 0
55 | xrvel Universitas Kristen Satya Wacana | -/- | 1/- | -/- | 1/- | -/- | 0 | 0
56 | VeRMeL Universitas Atma Jaya Yogyakarta | -/- | -/- | 6/- | -/- | 5/- | 0 | 0
57 | WALK Universitas Kristen Duta Wacana | -/- | 2/- | -/- | -/- | 1/- | 0 | 0
58 | unikomIF2 Universitas Komputer Indonesia | 1/- | -/- | -/- | -/- | -/- | 0 | 0
59 | noname.cpp Institut Teknologi Sepuluh Nopember | -/- | -/- | -/- | -/- | -/- | 0 | 0
60 | unikomIF3 Universitas Komputer Indonesia | -/- | -/- | -/- | -/- | -/- | 0 | 0
61 | NEW_BIE STMIK Mikroskil | 1/- | -/- | -/- | 4/- | 16/- | 0 | 0
62 | WAR Team Institut Teknologi Sepuluh Nopember | 3/- | 1/- | -/- | -/- | -/- | 0 | 0
63 | uteuk Universitas Pendidikan Indonesia | 2/- | -/- | -/- | 1/- | -/- | 0 | 0
64 | Maranatha2 Universitas Kristen Maranatha | -/- | -/- | -/- | -/- | -/- | 0 | 0
65 | Maranatha1 Universitas Kristen Maranatha | -/- | -/- | -/- | -/- | 3/- | 0 | 0
66 | UB_Team Universitas Brawijaya | 1/- | 1/- | -/- | -/- | -/- | 0 | 0
67 | unikomIF1 Universitas Komputer Indonesia | -/- | 1/- | -/- | -/- | -/- | 0 | 0
68 | mcntouch Universitas Indonesia | -/- | -/- | -/- | -/- | 1/- | 0 | 0
69 | UMN B Universitas Multimedia Nusantara | 2/- | 4/- | -/- | 2/- | 1/- | 0 | 0
70 | you Sekolah Tinggi Ilmu Statistik | 1/- | -/- | 1/- | -/- | 2/- | 0 | 0
71 | hidden Binus University | -/- | -/- | -/- | -/- | -/- | 0 | 0
72 | USD01 Universitas Sanata Dharma | 2/- | 1/- | 1/- | 1/- | 1/- | 0 | 0
73 | tuwek Institut Teknologi Sepuluh Nopember | 5/- | 3/- | -/- | -/- | 9/- | 0 | 0
74 | stmik-mdp STMIK MDP | -/- | -/- | -/- | -/- | 3/- | 0 | 0
75 | UNPAK1 Universitas Pakuan | -/- | -/- | -/- | -/- | -/- | 0 | 0
76 | takdir Sekolah Tinggi Ilmu Statistik | -/- | -/- | 1/- | -/- | -/- | 0 | 0
77 | TIC_Ext UIN Syarif Hidayatullah Jakarta | -/- | 1/- | -/- | -/- | -/- | 0 | 0
78 | UNPAK2 Universitas Pakuan | -/- | -/- | -/- | -/- | -/- | 0 | 0
79 | USD02 Universitas Sanata Dharma | -/- | 1/- | -/- | 1/- | -/- | 0 | 0
80 | TREUKM Universitas Kristen Maranatha | 3/- | -/- | -/- | -/- | 3/- | 0 | 0
81 | ubaya3 Universitas Surabaya | 4/- | 2/- | -/- | 1/- | -/- | 0 | 0
82 | scratchz Institut Teknologi Telkom | -/- | -/- | -/- | 2/- | 2/- | 0 | 0
83 | USD04 Universitas Sanata Dharma | 1/- | -/- | -/- | 4/- | -/- | 0 | 0
84 | pit-uii Universitas Islam Indonesia | -/- | -/- | -/- | -/- | -/- | 0 | 0
85 | proxie UNIKA Soegijapranata | 1/- | -/- | -/- | 1/- | 3/- | 0 | 0
86 | RoyalFlush Widyatama University | -/- | 1/- | -/- | -/- | -/- | 0 | 0
87 | USD03 Universitas Sanata Dharma | 3/- | 1/- | 1/- | 1/- | 1/- | 0 | 0
88 | ubaya6 Universitas Surabaya | -/- | 3/- | -/- | 3/- | 5/- | 0 | 0
89 | ubaya5 Universitas Surabaya | -/- | 1/- | -/- | 4/- | 2/- | 0 | 0
90 | trnkanBBM Universitas Sanata Dharma | 1/- | -/- | -/- | 7/- | -/- | 0 | 0
91 | L-AC Universitas Surabaya | 4/- | -/- | -/- | -/- | 1/- | 0 | 0
92 | "A" Petra Christian University | 2/- | 3/- | -/- | 1/- | -/- | 0 | 0
93 | bpc_uin3 UIN Syarif Hidayatullah Jakarta | 3/- | 1/- | -/- | -/- | -/- | 0 | 0
94 | bpc_uin5 UIN Syarif Hidayatullah Jakarta | -/- | -/- | -/- | -/- | -/- | 0 | 0
95 | brawijaya Universitas Brawijaya | 1/- | 4/- | -/- | -/- | -/- | 0 | 0
96 | buaya_air Institut Teknologi Sepuluh Nopember | 1/- | -/- | -/- | -/- | -/- | 0 | 0
97 | burjo Universitas Atma Jaya Yogyakarta | 4/- | 1/- | -/- | -/- | 7/- | 0 | 0
98 | code-man Universitas Sanata Dharma | 8/- | -/- | -/- | -/- | 2/- | 0 | 0
99 | coder_cupu Institut Teknologi Sepuluh Nopember | 1/- | 2/- | -/- | -/- | 4/- | 0 | 0
100 | color_ijo Binus University | 2/- | -/- | -/- | 1/- | 1/- | 0 | 0
101 | cryptocode Sekolah Tinggi Sandi Negara | -/- | -/- | -/- | -/- | 1/- | 0 | 0
102 | CRYSTAL STMIK Mikroskil | -/- | -/- | -/- | 1/- | 1/- | 0 | 0
103 | cuxed Universitas Atma Jaya Yogyakarta | 2/- | 6/- | -/- | -/- | -/- | 0 | 0
104 | CYBER Universitas Sriwijaya | -/- | -/- | -/- | 4/- | -/- | 0 | 0
105 | cyberwitch Universitas Nasional PASIM | 1/- | -/- | -/- | 3/- | -/- | 0 | 0
106 | cyborg Universitas Sriwijaya | 1/- | -/- | -/- | 3/- | 2/- | 0 | 0
107 | bpc_uin2 UIN Syarif Hidayatullah Jakarta | -/- | -/- | -/- | -/- | -/- | 0 | 0
108 | blueman Binus University | 4/- | -/- | 2/- | 3/- | -/- | 0 | 0
109 | adrianus Binus University | -/- | -/- | -/- | -/- | -/- | 0 | 0
110 | adryn Binus University | -/- | -/- | -/- | -/- | -/- | 0 | 0
111 | aeos Institut Teknologi Sepuluh Nopember | 4/- | 5/- | -/- | -/- | 7/- | 0 | 0
112 | amat Universitas Nasional PASIM | 1/- | -/- | -/- | -/- | 5/- | 0 | 0
113 | anas Sekolah Tinggi Ilmu Statistik | 2/- | -/- | -/- | -/- | -/- | 0 | 0
114 | ardiansa Universitas Atma Jaya Yogyakarta | -/- | -/- | -/- | 2/- | -/- | 0 | 0
115 | Arie Sekolah Tinggi Ilmu Statistik | 3/- | -/- | -/- | -/- | 3/- | 0 | 0
116 | arihil Institut Teknologi Bandung | 2/- | 1/- | 1/- | -/- | -/- | 0 | 0
117 | ARTis Institut Teknologi Telkom | -/- | 8/- | -/- | -/- | -/- | 0 | 0
118 | blink182 Institut Teknologi Sepuluh Nopember | 2/- | -/- | 1/- | -/- | -/- | 0 | 0
119 | blue01 Universitas Budi Luhur | 5/- | -/- | -/- | -/- | -/- | 0 | 0
120 | blue02 Universitas Budi Luhur | -/- | -/- | -/- | -/- | 3/- | 0 | 0
121 | blue03 Universitas Budi Luhur | -/- | -/- | -/- | -/- | -/- | 0 | 0
122 | blue04 Universitas Budi Luhur | -/- | -/- | -/- | -/- | -/- | 0 | 0
123 | Darc Binus University | 2/- | -/- | -/- | -/- | -/- | 0 | 0
124 | deadline Institut Teknologi Sepuluh Nopember | 4/- | 5/- | -/- | -/- | 1/- | 0 | 0
125 | DEBUS STMIK Mikroskil | 1/- | -/- | -/- | -/- | 3/- | 0 | 0
126 | HMIF_ITI Institut Teknologi Indonesia | -/- | -/- | -/- | -/- | -/- | 0 | 0
127 | hydrant Institut Teknologi Sepuluh Nopember | 4/- | -/- | -/- | 3/- | -/- | 0 | 0
128 | ICE_BOY3 STMIK Mikroskil | 2/- | -/- | -/- | 1/- | -/- | 0 | 0
129 | ikom1 Unika Soegijapranata | -/- | -/- | -/- | -/- | 1/- | 0 | 0
130 | ikom_06 UNIKA Soegijapranata | 3/- | 1/- | -/- | -/- | 1/- | 0 | 0
131 | ilkomupi06 Universitas Pendidikan Indonesia | -/- | 1/- | -/- | -/- | -/- | 0 | 0
132 | IntMain Binus University | 4/- | 5/- | -/- | -/- | 2/- | 0 | 0
133 | ITATS Institut Teknologi Adhi Tama Surabaya | 3/- | -/- | -/- | 2/- | -/- | 0 | 0
134 | iteam Widyatama University | -/- | -/- | -/- | -/- | -/- | 0 | 0
135 | jajakajawa Universitas Indonesia | -/- | -/- | -/- | 3/- | 3/- | 0 | 0
136 | JGTR Binus University | 4/- | 7/- | 4/- | 4/- | 1/- | 0 | 0
137 | Jimmy Binus University | -/- | -/- | -/- | -/- | -/- | 0 | 0
138 | k1r4 Universitas Sumatera Utara | 1/- | -/- | -/- | -/- | -/- | 0 | 0
139 | GembelJaya Institut Teknologi Harapan Bangsa | 3/- | 1/- | -/- | -/- | 2/- | 0 | 0
140 | ganbamon Institut Teknologi Sepuluh Nopember | 3/- | 1/- | -/- | -/- | -/- | 0 | 0
141 | Denny_Dj Binus University | 1/- | 5/- | -/- | 1/- | 1/- | 0 | 0
142 | DINDAM Universitas Sriwijaya | -/- | -/- | -/- | 2/- | 4/- | 0 | 0
143 | dna_soft Institut Teknologi Telkom | 2/- | 2/- | -/- | -/- | 4/- | 0 | 0
144 | dreaming Institut Teknologi Sepuluh Nopember | 3/- | 2/- | -/- | -/- | -/- | 0 | 0
145 | DUTA Universitas Kristen Duta Wacana | 3/- | -/- | -/- | -/- | 1/- | 0 | 0
146 | ECKS-RAY Institut Teknologi Sepuluh Nopember | -/- | -/- | -/- | 3/- | 1/- | 0 | 0
147 | ELANG Sekolah Tinggi Informatika & Komputer Indonesia | -/- | -/- | -/- | -/- | -/- | 0 | 0
148 | FADE Universitas Sriwijaya | 3/- | -/- | -/- | 1/- | 1/- | 0 | 0
149 | fasilkom Mercu Buana University | -/- | -/- | -/- | -/- | -/- | 0 | 0
150 | fasilkom2 Mercu Buana University | -/- | 1/- | -/- | -/- | 2/- | 0 | 0
151 | festivals Institut Teknologi Sepuluh Nopember | -/- | -/- | 1/- | 2/- | 5/- | 0 | 0
152 | frogroot Widyatama University | -/- | 2/- | -/- | -/- | 1/- | 0 | 0
153 | fti-uksw Universitas Kristen Satya Wacana | 3/- | 4/- | -/- | -/- | -/- | 0 | 0
154 | fti-uksw06 Universitas Kristen Satya Wacana | 3/- | -/- | -/- | -/- | -/- | 0 | 0
155 | KaaN Binus University | -/- | -/- | -/- | -/- | -/- | 0 | 0

# Statistics - Babak Penyisihan

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

## Submissions

Problem | Submission | Accepted
C/C++ | Java | Total | C/C++ | Java | Total | Rate
A | 168 | 88 | 256 | 20 | 4 | 24 | 9.38%
B | 172 | 47 | 219 | 9 | 2 | 11 | 5.02%
C | 36 | 8 | 44 | 0 | 0 | 0 | 0%
D | 127 | 38 | 165 | 16 | 2 | 18 | 10.91%
E | 180 | 50 | 230 | 37 | 10 | 47 | 20.43%
Total | 683 | 231 | 914 | 82 | 18 | 100 | 10.94%

## Rejected Submissions

Reason | C/C++ | Java | Total
Presentation Error (PE) | 1 | 0 | 1
Wrong Answer (WA) | 414 | 117 | 532
Run-time Error (RTE) | 41 | 69 | 110
Time-limit Exceed (TLE) | 92 | 9 | 101
Compile Error (CE) | 53 | 17 | 70

## Number of Problem Solved

Solve | Teams
5 problems | 0 teams
4 problems | 6 teams
3 problems | 7 teams
2 problems | 14 teams
1 problems | 25 teams
0 problems | 103 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

Problem | Submission | Accepted
C/C++ | Java | Total | C/C++ | Java | Total | Rate
A | 16 | 12 | 28 | 1 | 0 | 1 | 3.57%
B | 0 | 0 | 0 | 0 | 0 | 0 | 0%
C | 10 | 0 | 10 | 1 | 0 | 1 | 10.00%
D | 141 | 27 | 168 | 32 | 10 | 42 | 25.00%
E | 48 | 12 | 60 | 8 | 4 | 12 | 20.00%
F | 50 | 15 | 65 | 2 | 0 | 2 | 3.08%
G | 130 | 22 | 152 | 14 | 3 | 17 | 11.18%
H | 3 | 0 | 3 | 0 | 0 | 0 | 0%
Total | 398 | 88 | 486 | 58 | 17 | 75 | 15.43%

## Rejected Submissions

Reason | C/C++ | Java | Total
Presentation Error (PE) | 0 | 1 | 1
Wrong Answer (WA) | 187 | 36 | 223
Run-time Error (RTE) | 34 | 9 | 43
Time-limit Exceed (TLE) | 114 | 23 | 137
Compile Error (CE) | 5 | 2 | 7

## Number of Problem Solved

Solve | Teams
8 problems | 0 teams
7 problems | 0 teams
6 problems | 0 teams
5 problems | 1 teams
4 problems | 1 teams
3 problems | 7 teams
2 problems | 12 teams
1 problems | 20 teams
0 problems | 8 teams

2008-08-05 20:15:53 Danny> Felix, aku nga ngerti, misal 190x yg mana First = 0 Length = 1, dp[first][length] bisa 9 dapat darimana ya..?, maksudnya 190x itu, apakah urutan dari 1900 s/d 1909, btul nga...? Thx yoo..^^ 2008-08-06 03:27:06 Felix Halim> Lupakan 190x itu cuman bikin bingung kayaknya... dp[First=0][length=1] valuenya adalah 9 karena ada 9 angka yang bisa dibentuk dengan first digitnya adalah 0 dan length dari x adalah 1. Ke sembilan bilangan tersebut adalah 00,01,02,03,05,06,07,08,09. Kalo kamu masukin ke 190x itu jadinya 1900, 1901, 1902, 1903, 1905, 1906, 1907, 1908, 1909.

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 Input | Output 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 Input | Output 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

2008-07-02 23:36:37 ardiankp> problem statement rada ga jelas.. kalo yg ketutup cuma edgenya returnnya "CLEAR" ato "ALMOST CLEAR"? 2008-07-03 00:58:44 Felix Halim> kata ndok gak bakal ada testcase kayak gitu yang nyerempet2... emang sih harusnya diperjelas di soalnya...

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 Input | Output 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

2008-07-04 21:57:34 elyi> logika kita da sama sih, cuman gw salah di waktu sortnya. mungkin di sort gw terlalu lama. jadi Kena TD d. soalnya gw bikin fungsi sort sendiri 2008-07-05 00:45:29 Felix J> @elyi, pake fungsi apa emangnya? kalo pake sort versi O(N^2) TLE, tapi kalo pake STL tinggal panggil fungsi sort kok... atau paling gampang pake qsort :)
2008-07-05 05:01:09 Felix Halim> Sort nya gak boleh pake bubble-sort/insertion-sort/selection-sort karena mereka itu udah O(N^2). Kan kita mau solusinya maximum O(N log N).
2008-07-05 07:21:24 elyi> iya ni,,,gw pake bubble sort. hee....
2008-07-05 07:21:48 elyi> pantes kena LD trus. ampe 7 kali lo. he,,,,
2008-07-05 07:32:30 Felix J> @elyi, btw, LD itu apa? TLE maybe? kalo buble O(N^2) gk bisa di andelin pas datanya sampe udah puluhan ribu... kecuali emang soalnya itu memaksa kita untuk memakai bubble atau sort2 O(N^2) lainnya..

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 Input | Output 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

2009-08-05 10:56:40 cvcv> ccbcb

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 Input | Output 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%.

2008-07-02 23:54:57 apapun> mau tny, bentuk soal yg sebenarnya dari soal ini (yang katanya kudu pake segment tree) tuh kyk gmn? perubahan constrain? boleh dunk dibahas jg disini lix... ^^ 2008-07-03 01:03:01 Felix Halim> apapun: contoh soal segment-tree nya kan ada di link "milis JUG" di kiri, pembahasannya juga ada disana.
2008-07-03 01:13:35 apapun> mm...iyah...kalo rmq wa dah bs... cm blm kpikiran itu bisa dipake di soal ini tuh utk cari apanya? soalnya datanya itu kan dinamis alias isi arraynya masih bisa berubah... soalnya rmq biasa yg wa pake cm bs handle query max/min utk array yg statis... mohon pencerahannya...thx ^^
2008-07-03 01:18:36 Felix Halim> RMQ yang dinamis itu bisa dengan segment-tree. Updatenya hanya log(n) dari root sampai ke leaf.
2008-07-03 01:25:16 Felix Halim> RMQ itu cuman istilah :), implementasinya bisa banyak macam seperti dengan segment-trees, sparse-table, dynamic programming, etc...
2008-07-03 01:27:45 apapun> ow.... yg wa pake yg model DP seh, precomputer tabel dp nya.... Jd kalo mau yg dinamis ga bs yg DP bottom-up yah? anda pny cth rmq dengan memakai segment tree ga? =)
2008-07-03 01:28:15 Felix Halim> http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
2008-07-03 01:28:39 Felix Halim> Disitu lengkap berbagai macam cara untuk RMQ
2008-07-03 01:32:52 apapun> ow... sep2.... thx yah... =)
2008-07-03 08:07:49 Eko> gua ga pake2 counting-sort, just simulate it, untung tembus :P
2008-07-03 20:09:08 suhendry> @eko: hm.... apa time-limitnya kegedean ya? harusnya gak tembus. mungkin lu hoki coding lu kena bar-bar yg efisien punya :-D

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:

Query | To Do | Example
--- | --- | ---
insert a b c d e | append {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 r | delete row r. | remove 3
max c | output the highest value in column c. | max 3
min c | output the lowest value in column c. | min 1
range c a b | output 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 Input | Output 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 Input | Output 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 Length | Sequence Number | Walaweh Numbers
--- | --- | ---
1 | 1. | 0
1 | 2. | 1
2 | 1. | 00
2 | 2. | 10
2 | 3. | 01
2 | 4. | 11
3 | 1. | 000
3 | 2. | 010
3 | 3. | 001
3 | 4. | 011
3 | 5. | 100
3 | 6. | 110
3 | 7. | 101
3 | 8. | 111

Walaweh Length | Sequence Number | Walaweh Numbers
--- | --- | ---
4 | 1. | 0001
4 | 2. | 0101
4 | 3. | 0011
4 | 4. | 0111
4 | 5. | 1001
4 | 6. | 1101
4 | 7. | 1011
4 | 8. | 1111
4 | 9. | 0000
4 | 10. | 0100
4 | 11. | 0010
4 | 12. | 0110
4 | 13. | 1000
4 | 14. | 1100
4 | 15. | 1010
4 | 16. | 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 Length | Sequence Number | Walaweh Numbers
--- | --- | ---
6 | 60. | 110011
6 | 61. | 101111
6 | 62. | 100111
6 | 63. | 101011
6 | 64. | 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.

2008-06-23 21:55:06 Felix Halim> Jika ada links/news/blogs baru tentang INC 2008, tolong post link nya di chatbox ini. Thanks. 2008-07-03 21:52:51 suhendry> ini menarik nih: http://penjagacumi.blogspot.com/2005/11/tutorial-memasak-indomie-goreng.html
2008-07-04 07:31:17 Felix J> @om shu, wahuahuahuhua... sampe tutorial membuat indomie nya di cari kek gitu... hahahaha...

Name: |  | Message: |

# Blogs

- Andrian Kurniady [ Penyisihan, Final, Photos ]
- Daniel Susanto [ Surprise ]
- Dwika Putra [ PreContest | Final Round ]
- Eko Wibowo [ Curhat ]
- Felix Jingga [ Peserta Tersembunyi ]
- Heru Prasetia [ First Training | Before INC 2008 ]
- Indra Gunawan [ Babak Penyisihan | Babak Final ]
- Panji Adi Prabowo [ Rangkuman ]
- Kiki Ahmadi [ PHOENIC 05 goes to Binus: Semangat Rek!! ]
- Izhari Ishak Aksa [ Bonggow | Bonggow 'digagalkan' Unjuk Gigi ]
- Ng Elyi Junaidi [ Pengalaman | Final Round ]
- Suhendry Effendy
  - ACM/INC and ACM/ICPC 2008 On The Way ;)
  - INC 2008: Call for Participants
  - INC 2008: Practice Session
  - INC 2008: Qualification Round
  - INC 2008: Final Round
- Timotius Sakti [ Final ACM/ICPC INC 2008 ]

# Berita

- HIMTI
- Kaskus
- Yamuzaki

# Forum Diskusi

- HIMTI
- Marsudirini
- Universitas Indonesia

# Others

- Indomie Fans (Facebook)
- Indomie Satu Selera

`© Felix Halim 2009 (Loaded in 0.18390 secs)`

    Timeline:
    start_time (diff_time_with_previous) tree_structure
    0.00000 (0.00000) Total
    0.00003 (0.00003) -Logging Request
    0.00005 (0.00003) --Creating fhnet PDO...
    0.00610 (0.00605) --fhnet PDO created
    0.00613 (0.00003) --Statement created
    0.00712 (0.00099) --Statement executed

    Summary:
    start_time (duration) section_name
    0.00000 (0.18394) : Total
    0.00003 (0.00712) : Logging Request