Nimble
Given a line of squares labeled 0, 1, 2, …. Several coins are placed on some squares (it’s possible to have more than one coin on a single square). Two players take turns. One move consists of taking any one coin and moving it to any square to the left of it. It’s possible that the coin moved into a square already containing coins.

Poker Nim
This game is played as a standard Nim Game, but players have option to either substracting stones (like in standard Nim Game) or adding more stones in a pile but not exceeding the original number of stones in that pile. To ensure the game termination, each player is allowed to add stones at most k (a finite number of) times.

Turning Turtles
Given a horizontal line of N coins with some coins showing heads and some tails. Each turn, a player have to flip one coin from head to tail, and in the same time (if he/she wants), flip one more coin to the left of it.

For example, consider this sequence of N = 10 coins:

1 2 3 4 5 6 7 8 9 10
T H T T H H T T T H

Possible moves from this position are:

• Flip one coin from head to tail. Eg., coin in position 6 from head to tail.
• Flip one coin from head to tail and flip another coin (from tail to head) to the left of it. Eg., coin in position 6 from head to tail and flip coin in position 3 from tail to head.
• Flip one coin from head to tail and flip another coin (from head to tail) to the left of it. Eg., coin in position 6 from head to tail and flip coin in position 2 from head to tail.

Silver Dollar Game (without silver dollar)
This game is played on a line of squares labeled 0, 1, 2, … with several coins are placed in some square such that no two coins are placed in a same square. One move consists of moving one coin to its left onto any empty square and not passing any other coin. The game ends when a player cannot make any legal moves, since all the coins are jammed at the left-end of the strip.

For example, given these 4 coins in position {2, 5, 7, 10}:

1 2 3 4 5 6 7 8 9 10 11
0 1 0 0 1 0 1 0 0  0  1

Possible moves from this position is:

• Move coin in position 11 to position 10, 9 or 8.
• Move coin in position 7 to position 6.
• Move coin in position 5 to position 4 or 3.
• Move coin in position 2 to position 1.

1 2 3 4 5 6 7 8 9 10 11
0 1 * * 1 0 1 * *  *  1

Nim is a two player combinatorial/mathematical game strategy. Given a number of piles which in each pile contains some numbers of stones. In each turn, player choose one pile and remove any number of stones (at least one) from that pile. In a normal play, player who cannot move is considered lose (ie., one who take the last stone is the winner). There is another variation where player who cannot move is considered as winning (misere play).

Nim game is an impartial game, which means the possible moves from any position are the same for each player. The only difference between two players is who move first. Chess, for example, is not an impartial game because one player play white pieces while the other play black pieces. According to this, ANY impartial game can be transformed into a Nim game using Sprague-Grundy Theorem. So, solving a Nim game is essential to solve any impartial game. I’ll discuss about Grundy number in other time.

Fortunately, there is a simple winning formula for Nim game.

Any position where the xor value of all piles is not zero is a winning position, otherwise it is a losing position. This xor value usually refered as nim-sum.

For example, let there be 5 piles of stones consisting: {2, 5, 1, 7, 3} stones respectively. The nim-sum of those piles are: 2 ⊕ 5 ⊕ 1 ⊕ 7 ⊕ 3 = 2, which is a winning position (who ever play first have a winning strategy). Another example, let there be 5 piles of stones consisting: {3, 5, 1, 4, 3} stones respectively. The nim-sum of those piles are: 3 ⊕ 5 ⊕ 1 ⊕ 4 ⊕ 3 = 0, which is a losing position (who ever play second have a winning strategy). When I said “winning strategy”, it means there is a strategy which ensure the winning of the respective player.

What is the reason behind that formula?

Here is the main idea. If the nim-sum is not zero, you always have at least one move which change the nim-sum into zero. In other hand, if the nim-sum is zero, you can only change it into a non-zero nim-sum. Note that the end game state (no stones) have a zero nim-sum. Which means, whoever is able to maintain the zero nim-sum for his/her enemy will win this game.

Let x₁, x₂, …, x_n be the size of piles before a move, and y₁, y₂, …, y_n be the size of piles after a move. Let s = x₁ ⊕ x₂ ⊕ … ⊕ x_n (ie., nim-sum before a move) and t = y₁ ⊕ y₂ ⊕ … ⊕ y_n (ie., nim-sum after a move).

First we observe the relation between s and t. In this game a move consists of removing any number of stones (at least 1) from any one pile. Supposed the chosen pile is pile k, so x_k is its previous number of stones in k^th, y_k is its number of stones after the move, and x_k ≠ y_k because we have to remove at least 1 stone, or to be precise, y_k < x_k.

Notice that x ⊕ x = 0 and xor obeys associative and commutative laws.

t = 0 ⊕ t
  = s ⊕ s ⊕ t
  = s ⊕ (x1 ⊕ ... ⊕ xn) ⊕ (y1 ⊕ ... ⊕ yn)
  = s ⊕ (x1 ⊕ y1) ⊕ ... ⊕ (xn ⊕ yn)
  = s ⊕ 0 ⊕ ... ⊕ 0 ⊕ (xk ⊕ yk) ⊕ 0 ⊕ ... ⊕ 0
  = s ⊕ xk ⊕ yk

t = s ⊕ xk ⊕ yk    (1)

We will use (1) equation to proof the subsequence lemma.

Lemma 1. If s = 0, then t ≠ 0 no matter what the move is made.
Proof: From (1) we can see that if s = 0, then any move will produce t ≠ 0 because x_k ⊕ y_k ≠ 0 (since x_k ≠ y_k).

Lemma 2. If s ≠ 0, then it always possible to make a move so t = 0.
Proof: This following strategy will cause t = 0. Find d,the leftmost non-zero bit in binary representation of s and choose pile k (any pile) which d^th bit is also non-zero. Such k must exists, otherwise d^th of s must be zero. Then we can claim that y_k < x_k for y_k = s ⊕ x_k since all bits to the left of d is the same in x_k and y_k, while the d_th bit is changed from 1 to 0, and the remaining right bits can only do at most 2^d-1 changes.

t = s ⊕ xk ⊕ yk
  = s ⊕ xk ⊕ (s ⊕ xk)
  = 0

Thus the respective player can make a move by taking x_k – y_k stones from pile k.

This following example will ilustrate the strategy used in proof of lemma 2.

Let there be 5 piles which stones are: {18, 6, 3, 20, 9).

18: 1 0 0 1 0
 6: 0 0 1 1 0
 3: 0 0 0 1 1
20: 1 0 1 0 0
 9: 0 1 0 0 1
------------- ⊕
 s: 0 1 0 1 0

The leftmost 1-bit of s lies in the 4^th. Find any pile which 4^th bit is 1, in our case, there’s only one: pile with 9 stones. Change the 4^th bit of that pile (with 9 stones) into 0. Because of changing this 4^th bit, we already ensure that the value of that pile will be less than its previous value (9) no matter what changes we’ll make in the remaining right bits. So, for the right bits, change all bit positions from 0 to 1 or vice-versa wherever it is 1 in s (we want to make t = 0).

18: 1 0 0 1 0
 6: 0 0 1 1 0
 3: 0 0 0 1 1
20: 1 0 1 0 0
 3: 0 0 0 1 1
------------- ⊕
 t: 0 0 0 0 0

If the player always maintain t = 0 for his/her enemy, then at the end he/she will win this game as nim-sum for the end game (no stones) is zero.

I’ll discuss several example of impartial game which turn out to be Nim Game in the next post.

All transportation and accomodation expenses are paid by the committee. I stayed at Lanson Place Ambassador Row, a four-star hotel located at Ampang. I got a very nice room, it has living/study room, bedroom, bathroom and kitchen. There’re two TVs, one in the living room and one in bedroom. There’re also microwave, water-heater, refrigerator and cutlery in the kitchen. Eko said that room was a “suit” type, I don’t know what it means.

The agenda for first day was judge meeting, so I came to IIUM (escorted by a committee) and met other judges. There are 3 judges who have already in the meeting room: Dr. Hossam El Gindy (chief), Marini Abu Bakar and Niko Ibrahim. Actually there is one more judge (Dr. Teddy Mantoro), but he said that he couldn’t attend judge meeting and practice session (icpc day-1). Hossam gave me a copy of problemset which will be used in the contest. I proposed two problems for this ICPC, apparently they’re put in problem B and G. I noticed one of the problem was exactly the same with a problem in ITBPC (one of Indonesia local contest), given an infinite size chessboard count the minimum step needed to move from one cell to another cell with knight move. I told Hossam about that problem and he agreed to withdraw the problem. Surprisingly, Marini also knew that problem from a Malaysia local contest, the more reason we should withdraw the problem. Hossam proposed another problem to substitute the withdrawn problem. Somehow I felt that I have encountered that new problem, but I couldn’t remember, so I just let it pass. We discussed the solution to the problem and I coded it.

Back to the hotel and I was hungry. Unfortunately, there’s not many choice for dinner. I went to a persian restaurant and ordered some kind of grilled chicken. They surely took a lot of time to prepare the food, but the food was okay.

The agenda for ICPC Day-1 was opening ceremony and practice session for contestants. Before opening ceremony, Hossam has setup PC2 for practice session. He decided to set the time-limit for each problem quite large and hid it from the contestants. When I asked him why we hid the time-limit, he said that he followed ICPC World Final. I don’t understand the reason behind this, but the time-limit was so generous, so I think it’s okay.

The trouble in practice session appeared after half hour elapsed time. Some teams begun to “test” the server and judge machines. They tested whether their codes will exceed the time-limit by doing a lot of iterations or even an infinite loop. Some teams also tested the stack size by doing recursion. In ICPC Jakarta I just let contestants did this, but in here the problem was: time-limit for each problem was large! There are 4 judges and all judge machines test contestant’s “solution” which consumed a lot of time (because it did a lot of iterations), and at one time I saw there’re more than 30 pending submissions. Hossam then decided that such submission is not allowed anymore, because it will obstruct “real” solution from other contestants.

After practice session I realized that judge machines are quite fast, so I suggested Hossam to decrease the time-limit for the contest proper. I also tested the brute-force solution for my two problems in judge machines and as I suspected they run quite fast, so I decided to decrease the time-limit more for my problems.

ICPC Day-2 was the contest proper. I wear ICPC shirt given by committee the day before, but Hossam did not, because he said his shirt was too small (yes, he has a big body).

The contest begun and there’re some submissions for easy problem. Strangely, they all got Wrong Answer. I doubt such easy problem could lead to many wrong answers, so I checked the contestants’ output and compare them to judge’s output. I found the input which made the output different. At first I thought the contestants’ were wrong, but then I realized that I looked at a wrong panel (I mixed up judge and contestant panel). Apparently there’s a bug in judge’s output. Hossam decided to remove that particular case (only 1 case) and rejudged the submissions. This happened very early in the contest so only a few teams knew about this.

Later there’re several reports about teams whose name in ranklist were wrong. Hossam investigated the problem and found the cause. It seems that all teams id are shifted by 3. To fix this the committee rename all teams manualy in PC2.

Before the contest begun, I said to Hossam that the problemset might be not hard enough for some strong teams. And I was right. Team +1 ironwood branch from National Taiwan University solved all the problems in just 3 hours, which made them the winner. And there are 3 more teams which solve all the problems in last hour.

The closing ceremony was quite simple but nice. There are two categories of champion, national and regional champion. The regional winners are:
1. +1 ironwood branch, National Taiwan University.
2. ETC, Fudan University.
3. Dongskar Pedongi, Institut Teknologi Bandung.

I think Dongskar Pedongi will qualify to World Final as ETC is not from this sub-region.

Meanwhile, BINUS teams were not doing well. They only solved 3 and 4 problems (compared to the winner which solved 9 problems).

Well, that’s my story in ACM-ICPC Kuala Lumpur.

Lah terus ini post tentang apa? Di sini gw cuma mau post tentang cerita tentang pengalaman atau kejadian-kejadian unik yang gw alamin di INC kemarin aja. Mumpung masih segar dalam ingatan, kalau nunggu bulan depan udah keburu lupa. Nulis post ini cuma perlu waktu sekitar 1 jam (kalau pembahasan bisa satu hari). Tenang aja, pembahasan pasti dibuat, cuma ya minggu-minggu depan…

INC 2011 adalah INC pertama gw dimana gw nggak di Jakarta, ho oh, seperti yang pak Freddy bilang di penutupan INC yang lalu, gw lagi di Singapore. Jadi banyak urusan gw di INC yang dikerjain ama Eko dan Timo, sekalian mereka belajar mana tau tahun depan bisa gw tinggal jadi gw cuma ngeset soal doank (tapi kayanya sih belum bisa).

Gw balik Jakarta dari Kamis malam, tiga hari sebelum INC, karena gw juga mau sekalian perpanjang KTP. Kalau Sabtu/Minggu kayanya kelurahan tutup sedangkan Senin gw harus ke Bandung buat Pelantas 1 TOKI, jadi mau ga mau deh. Tapi ternyata perpanjang KTP hari Jumat kemarin itu adalah kesalahan besar, komputer di kelurahannya rusak x( sia-sia gw datang dari pagi jam 9 dan nungguin mereka benerin satu hari yang akhirnya bilang “kayanya lama nih baru bener, ntar sore jam 4 baru balik ya”. Karena jam 5:30 gw ada janji mau ketemuan Fiona, yo wes tinggal, lupakan KTP.

Preparation

Satu hari sebelum INC (Sabtu) biasanya gw dan beberapa juri lain ngecek kesiapan sistem di ruang kontes (lab) sekaligus ngecek time-limit tiap soal di komputer kontes. Gw ga inget tahun-tahun sebelumnya gimana, tapi gw baru diingetin kalo ternyata praktikum mahasiswa masih berjalan jadi kita ga bisa pake ruang lab (doh!) siang hari. Padahal plan gw, pagi/siang beresin sistem INC, sore/malam kencan. Solusi: berdayakan Eko. Gw minta dia yang ngecek sistem dan tes time-limit sore-sore di lab.

Sabtu pagi gw ke BINUS, tepatnya ke Multiplus seberang kampus Anggrek, buat ngeprint dan fotokopi soal untuk practice session. Karena soal-soal ini telat masuk ke penggandaan (emang baru selesai disiapin Kamis/Jumat) jadi gw bilang ke Muhsin kalo gw yang akan kopi sendiri. Sebelum ke Multiplus gw ketemu Ricat di tengah jalan, dia mau kuliah kayanya. Pas nyampe Multiplus gw baru tahu… ternyata Multiplus seberang Anggrek udah bangkrut, gw buka pintunya, cuma ada batu-batu dan sampah Haiyah, ya sudah, pindah ke fotokopi Daya, yang untungnya bisa ngeprint juga (sebelumnya gw taunya dia cuma bisa fotokopi aja).

Selesai fotokopi soal practice, gw mampir makan di Petojo (rumah makan Petojo sebelah Daya) dan pesan menu gw yang “biasa”: nasi putih + mie goreng. Selesai makan, gw ke ATM bentar di kampus, baru balik dari SG blum ngambil duit, pas nyeberang balik mo nyari taksi… gw ketemu rombongan 3 orang aneh yang manggil gw dan terus nyengir-nyengir: Eko, Winardi, Albert. Eko ngomel-ngomel protes bilang katanya gw ga bisa dateng mo pergi kencan, ya emang ga bisa, itu udah saatnya pergi, kan yang gw bilang ga bisa itu sore/malam Selamat bekerja ya…

Malam sebelum INC kali ini ternyata gw masih beresin soal, tepatnya soal C punya Ilham. Sampe beberapa hari menjelang final, Ilham belum berhasil menyelesaikan codenya yang O(N^2 lg N), katanya ada masalah di implementasi salah satu bagian algonya. Untung udah bikin backup plan dengan menurunkan N di soal jadi 500 (sebelumnya 1000) dan siapin solusi O(N^3 lg N). Masalah di soal ini bukan cuma solusinya, tapi gimana cara generate testcasenya?? Random graph tentu ga akan bisa karena outputnya kemungkinan besar NO. Alhasil Risan dan Ilham akhirnya berhasil bikin generator graph buat soal ini. Ilham udah disain 40 jenis testcase, tapi karena dirasa masih kurang, ya udah ditambah 20 case lagi dari generator Risan (makanya soal C ada ralat soal T jadi 60). Yah, selesai beresin soal C udah jam 3:30 dan gw harus bangun jam 5:30, masih ada dua jam, mari tidur… sialnya gw udah guling-gulingan 1 jam masih ga bisa tidur! ya uda deh, ga usah tidur sekalian >.<

D-Day

Minggu pagi gw sampe ke lab jam 7:30, ternyata Aditya (ketua INC) udah mulai briefing ke anak-anak panitia yang lain. Gw langsung setup admin PC2 di lab, set user/pass dan upload semua data buat keperluan practice session. Kali ini kita pakenya PC2 versi 9.2 yang masih beta, soalnya 9.2 bisa ngubah output limit (ada satu soal rese yang outputnya >4M), sambil berharap gak ada masalah serius di 9.2. Kata Eko waktu itu dia pake pas penyisihan sih ga ada masalah.

Jam 8 peserta mulai datang (sebenarnya cuma 1 peserta aneh yang berencana kerja jadi cleaning service yang datang sebelum/tepat 8:00) dan registrasi ulang. Gw udah titipin ke yang jaga registrasi buat kumpulin team notebook peserta. Sekitar jam 8 lewat gw mendengar kabar yang super duper luar biasa mengejutkan: soal final terkunci di ruang akademis Syahdan. Udah gitu Building Management (BM) yang bisa dimintain buka ruang lagi ga ada katanya (nice). Di masa-masa panik gini si Ceemot minta gw print dan kopi ulang, masih ada dua jam harusnya sempat. Haih, ya wes, gw seret Eko dan ajak dia turun ke lantai 1 trus ke tempat fotokopi yang entah mana yang buka di hari Minggu. Pas di lantai 1 sebelum keluar dari gedung Anggrek, gw ngeliat protekom… tiba-tiba timbul ide, kenapa ga tanya mereka aja? Setelah tanya mereka, kita dialihkan ke basement tempat orang BM nongkrong soalnya katanya orangnya ada (lho). Lampu ruangnya sih nyala, tapi dikunci, ternyata orang yang jaga lagi makan, ya uda gw dikasi nomor hp si BM. Setelah gw telpon, ternyata dia juga udah ditelpon sama salah satu panitia, dan masalah udah beres. Beres? hmm… lega, tapi koq gw ga ditelpon/sms Ceemot buat cancel fotokopinya yah x( grrr…

Balik ke lantai 8 ngider-ngider sampai acara pembukaan di mulai. Gw bertugas ngasi technical briefing ke peserta pas pembukaan. Supaya lancar tentunya gw udah siapin slide buat mengcover apa aja yang mau gw sampein (meskipun pada akhirnya ada beberapa poin kecil yg kelupaan). Banyak pertanyaan dari peserta… ralat, banyak pertanyaan dari salah satu peserta (yang suka ngaku ganteng), pertanyaannya macam-macam dari yang normal sampai ga normal. Di sini gw juga sempat perkenalin beberapa problem setter, awalnya sih gw cuma mau mereka berdiri di tempat biar keliatan yang mana, tapi pak Freddy di depan gw bilang: “suruh maju aja su”. Yo wes >:) huahahaha, jangan salahkan saya kalian jadi panjangan

Selesai briefing, gw ama juri-juri lain buru-buru ke ruang kontes peserta dan ngecek team notebook mereka, karena ternyata team notebook udah ditaro di meja masing-masing peserta, padahal belum dicek. Gak ada yang notebooknya bermasalah kecuali satu tim, dari BINUS , ya itu tim punya peserta aneh yang pengen jadi cleaning service tadi. Mereka ngasi dua tim notebook yang isinya beda sama sekali, jadi total 50 halaman

Gak lama kemudian peserta mulai masuk ke ruang kontes, gw sendiri buru-buru ke ruang juri dan start practice sessionnya. Beberapa masalah timbul pas practice session, sebagian besar berkaitan dengan printing. Ya karena gw ga ngerti ya gw serahkan aja ke aslab yang ngerti masalahnya di mana. Untuk printing sendiri, di babak practice session hasil print hanya diperlihatkan ke peserta tapi ga dikasi (ditarik lagi), supaya ga disimpan sebelum babak final.

Crash

10:30 practice session selesai, gw minta Surya reset server PC2 dan gw mulai siapin data buat babak final. Sebenarnya gw agak khawatir dengan babak final, soalnya total size testcase itu ~50M, gw udah wanti-wanti ke Eko (selaku pemilik salah satu soal yang inputnya gede) kalo hal ini bisa jadi masalah. Soalnya pas 2008 juga pernah kejadian model gini, PC2 nya berlaku aneh, dan akhirnya ketauan karena heap size PC2 nya kurang gede buat handle data banyak, tapi waktu itu juga ga sampe segini banyaknya. Selesai upload semua data, setting ini itu, juri udah ada yang mulai login, si Surya mau aktifin scoreboard PC2 nya. NAH! kejadian juga kan, server PC2 tiba-tiba crash, out of memory >.<

Kata si Eko dia udah gedein heap size JVM buat PC2 sampe 1G, ya gw bilang kurang. Tapi ternyata memory di server cuma 2G , What?? Gawat, kalo digedein lagi servernya yang jadi matek ga punya memory. Ya udah coba gedein jadi 1.5G dulu dan liat apa yang terjadi, meanwhile gw ke ruang kontes dan umumin kalo kontes diundur. Musti gw umumin, soalnya aba-aba start contestnya pake timer yang ditampilkan pake proyektor infokus, jadi mereka bakal mulai sendiri kalo timernya abis. Setelah diset jadi 1.5G, gw upload ulang semua datanya, dan minta semua juri login, memori yang kepake udah 1G, padahal peserta belum login dan kontes belum jalan. Kemudian gw minta semua peserta login dulu, buat ngecek pemakaian memori nya di server, ternyata jadi > 1.2G. ughh… tinggal 300M sisanya, dan gw gak tau behaviour server PC2 kalo kontes lagi jalan >.< Gak berani ambil resiko, kalo servernya crash di tengah kontes bakal repot. Ya udah akhirnya diambil keputusan, beberapa soal yang inputnya gede dipisah, ga diupload di server PC2, karena kebetulan soal-soal yang inputnya gede itu bukan soal gampang, jadi submissionnya bakal dikit. Trus judge soal input gede itu gimana? Kita bikin satu server PC2 bayangan lagi pake komputer lab, dan submission untuk soal-soal itu akan disubmit ulang ke server bayangan ini, jadi bebannya dibagi gitu. Kalaupun server bayangan crash, ga masalah, tinggal restart ulang (gak mempengaruhi jalannya kontes). Alhasil server PC2 yang buat kontes cuma makan sekitar 300M (ya iya lah), woh... lega, kontes mulai!!

Contest Begins!

5 menit pertama, belum ada submission… *sunyi senyap*, padahal tahun-tahun sebelumnya juri diserbu di awal-awal kontes dari soal bonusnya. Hehehe, gw emang akui tingkat kesulitan soal final tahun ini lebih tinggi dari tahun sebelumnya, termasuk soal bonusnya. Terutama soal bonus kali ini emang sengaja dipilih yang emang gampang, tapi codingnya nggak 1-2 menit. Untuk soal bonusnya malah gw udah kasi “bocoran” pas briefing, jadi sebenarnya bisa skip langsung baca input-output dan coding

Submission pertama datang dari Saklar Lhompat (UI) untuk soal B di menit 11, yang tentunya AC. Submission kedua dari Apis Volan (BINUS) juga untuk soal B di menit 13. Gak lama kemudian satu per satu tim mulai mengirim submission, tapi ritmenya lambat banget, kalau gw perhatiin rata-ratanya 1.5 submission per menit. Dongskar (ITB) gimana? mereka ternyata ngehajar soal H duluan, yang adalah soal termudah kedua, baru sehabis itu mereka babat soal B. Setelah satu jam berlalu, peringkat satu (kalau ga salah) diraih sementara oleh Vidina (UI) dengan jumlah solve 3, kalo di ICPC Jakarta tahun-tahun lalu satu jam udah 5-6 soal . Vidina lumayan juga, karena setau gw anggotanya itu anak-anak semester baru semua.

Mendekati 1.5 jam, Dongskar submit soal E sebagai soal ketiga mereka, dan AC! Ruang juri langsung rame, soalnya E itu bukan soal yang termasuk bonus atopun medium. Buka source codenya, ga ngerti dia coding apa, close lagi. Ternyata tingkah laku Dongskar yang AC di soal E ini membuat beberapa tim “tertipu” ikut-ikutan ngerjain soal E. Sempat gw perhatiin di scoreboard, untuk soal E 6 tim di bawah Dongskar semuanya merah-merah, cuma ijo sendiri di paling atas. Gw bilang “tertipu” karena banyak soal lain yang lebih solvable daripada soal E, seperti soal A, F dan I.

Lewat 1.5 jam (kira-kira) belum banyak perubahan dan gw mulai ngantuk, maklum dua hari berturut-turut tidurnya kurang banget, terutama hari sebelumnya ga tidur. Juri yang lain sepertinya bisa menangani kejadian-kejadian yang bakal muncul, jadi ya udah gw tidur bentar di ruang juri, dengan berbagai pose, yang diabadikan oleh Eko Buluk. Pas gw lagi tidur di kursi si Fiona dateng, akhirnya nyampe, dia abis gereja dan baru sempet ke BINUS. Ya gw bangun, dan *masih* ga banyak perubahan. Ada beberapa klarifikasi yang mostly ga penting (cuma ga baca soal dengan teliti). Gak lama kemudian gw menghilang selama satu jam, makan siang, si Eko sempat beberapa kali sms/nelpon karena ada klarifikasi, yang seperti gw bilang tadi, itu gara-gara ga baca soal dengan teliti.

Balik ke ruang juri, yang leading masih Dongskar dengan total solve 6, dan tim kedua solve cuma 3, gilak, dua kali lipat >.< Dongskar solve 6 sih udah gw antisipasi, tapi tim lain cuma solve 3 itu ga gw expect, apa mungkin gara-gara "tertipu" soal E tadi ya. Gak lama kemudian Saklar Lhompat menyusul AC juga di soal E setelah sebelumnya sempat fail satu kali, jadi mereka sementara di tempat kedua dengan solve 4.

1 jam menjelang akhir kontes, scoreboard freezed, balon stop. Apis Volan, tim unggulan dari BINUS baru solve 3! Muhsin (kepala lab computing) udah stress ngeliatin scoreboard . Tapi dalam masa freeze ini, ternyata mereka melakukan sesuatu yang mengagetkan semua yang ada di ruang juri, mereka solve 3, soal E, I dan A! Si Muhsin dan Ceemot langsung girang joged-joged. Bipartite, tim kedua dari BINUS juga ternyata berhasil menyelesaikan soal F (yang emang menurut gw ga susah), dan berhasil naik ke rank 4. Saklar Lhompat dilain pihak, ga melakukan submission apa-apa selama 1 jam terakhir, katanya mereka ngebug di satu soal, entah bug apaan.

Menjelang akhir kontes, juri tiba-tiba diserang dengan spam, terutama dari TePeBe (ITB) dan Vanaheimr (BINUS). Yang TePeBe emang submission ga jelas, sedangkan Vanaheimr kayaknya desperate submission (18 submission fail semua). Yang jadi problem adalah soal E itu judgenya di server bayangan, jadi juri yang ngejudge Vanaheimr itu rada kerepotan (belum selesai dijudge udah masuk submission baru untuk soal yang sama dari tim yang sama).

End

Kontes berakhir dan sesuai dugaan awal dimenangkan oleh Dongskar Pedongi (ITB) dengan solve 7, di tempat kedua adalah Apis Volan dengan solve 6, dan di tempat ketiga adalah Saklar Lhompat dengan solve 4. Pas di practice session gw sempat broadcast klarifikasi kalo sesi pembahasan setelah kontes ditiadakan. Ya jelas. 16:00 bubar kontes, 16:00 mulai pembahasan, gw belum lulus dari ujian ninja, belum bisa bunshin no jutsu. Selesai kontes, juri (terutama gw) belum bisa langsung keluar dari ruangan, karena perlu cek dan rekap beberapa data, jadi impossible gw bisa langsung ke hall begitu kontes selesai. Selain itu gw juga yakin abis bubaran kontes para peserta pasti masih ngobrol-ngobrol dan ngabisin snack yang ada, bakal susah disuruh naik ke hall.

Penutupan diawali dengan kata sambutan/penutup? dari pak Freddy, sehabis itu gw membacakan daftar pemenang, dimulai dari honorable mention (solve >= 2), rank 18 (solve >= 3) dan naik sampai ke rank 1. Di sertifikat peserta yang non 3 besar semua tertulis honorable mention, soalnya itu pre-printed sebelum kontes. Ga keburu kalo semua diprint ranknya setelah kontes. Mungkin bisa diusul untuk tahun depan sertifikat rank-nya dikirim aja ke univ yang bersangkutan.

Bubar acara, saatnya memalak yang dapet duit. Thanks buat Ricky dan Hudi atas traktirannya di Petojo Reinhart dilupakan…
Huahahahahahaha…

Tahun sebelumnya Universitas Bina Nusantara dipercaya untuk menjadi host salah satu regional site ICPC (ICPC Jakarta), namun tahun ini direktur ICPC Asia menginginkan ICPC Jakarta dirotasi (“gantian”) dengan site-site lain, sehingga ICPC Jakarta tahun ini tidak ada (sambil berharap tahun depan kembali ada).

Karena tidak ada ICPC Jakarta, maka Universitas Bina Nusantara kembali menyelenggarakan INC sebagai kontes pemrograman tingkat nasional menggunakan sistem yang sama persis dengan ICPC dan terdiri dari dua babak, yaitu: penyisihan (online) dan final (onsite).

Di post ini saya akan memberikan pembahasan dari soal-soal penyisihan yang baru saja berlalu, sekaligus sedikit membahas mengenai beberapa kendala yang dihadapi peserta pada babak penyisihan.

Soal ACM-ICPC INC 2011 – Qualification Round dapat dilihat di sini.

Scoreboard babak penyisihan bisa dilihat di sini (kalau linknya mati artinya pathnya sudah berubah, akan saya update nanti).

Data uji sengaja tidak dirilis namun kalian bisa mencoba soal ini (nanti) di tokilearning.org karena data uji aslinya akan saya upload di sana.

Eko Wibowo (salah satu juri) juga sudah menulis blog tentang babak penyisihan yang lalu, postnya bisa dibaca di sini.

Pembahasan untuk masing-masing soal bisa dilihat di:
A – Frog in a Bus
B – The Yellow Dungeon
C – Divisor Game
D – Counting Different Bits
E – Rearranging Boxes
F – 1D Array Multiplication
G – Time Zone Conversion
Lain Lain

Kalau mau comment atau bertanya mengenai soal tertentu, tolong disebutkan soal mana yang dimaksud (comment di post ini semuanya digabung).

Yang patut diperhatikan, juara keempat itu dari BINUS juga (Pelopor Compfest), isinya hanya 1 orang: Winardi Kurniawan, dia dikhianati dua anggota timnya (Panji Kharisma dan Eko Mirhard) :p. Tapi bersyukur juga Panji ga ikut, kalau Winardi sendiri AC 7, tapi kalau Winardi + Panji kayaknya jadi AC 5 [-(

Ok, di sini gw mau kasi pembahasan singkat tentang soal-soal yang keluar. IMO, soal-soalnya ga susah, tapi ga ada satupun tim yang solve semua soal (pada mentok di soal E).

Soal bisa didownload di sini.

Scoreboard bisa dilihat di sini (tapi sepertinya link ini ga permanen).

A. Segiempat Terluas
Ini soal paling mudah. Luas maksimum bisa dibentuk oleh persegi (bujur sangkar), jadi solusinya tinggal (L/4)².

Heran, koq soal kayak gini perlu 10 menit..?

B. Pelat Terbalik
Angka 9 hanya bisa dipakai kalau ada angka 6, begitu juga sebaliknya. Kita mau membuat palindrome dengan angka-angka itu (9 dipasangkan dengan 6). Tinggal proses dari angka 9 sampai angka 0 (descending) dan cek apa angka itu (dan pasangannya) bisa dipake atau ngga. Kalau bisa tambahkan angka itu dari depan dan pasangannya dari belakang.

C. Gajah Catur
Untuk mengecek berapa poin yang bisa didapatkan dengan meletakkan gajah di sebuah petak kita memerlukan iterasi O(N), dan total terdapat N² petak (N ≤ 1000), sehingga algoritma bruteforce naif O(N³) tidak bisa digunakan di sini (akan mendapatkan Time Limit Exceed).

Seandainya yang ingin diletakkan bukan gajah, tapi benteng (bisa bergerak horizontal/vertikal tapi tidak diagonal), maka soal ini tentu jadi lebih mudah bukan? Hitung jumlah poin untuk setiap baris dan setiap kolom. Kemudian uji di semua petak berapa poin yang bisa didapatkan dari petak itu. Ini bisa dilakukan dalam O(1). Misalkan posisi yang mau diuji adalah (r,c), maka total poin = sumrow[r] + sumcol[c] – 2 * value[r][c]. Total kompleksitasnya O(N²).

EDIT: corrected 2 * value[r][c], thank to Jonathan Irvin Gunawan.

Sekarang bagaimana untuk soal ini (gajah)? Putar saja papannya 45 derajat. Jadi sebagai ganti sumrow dan sumcol, kita akan mendapatkan sumdiag1[] (diagonal kiribawah-kananatas) dan sumdiag2[] (diagonal kiriatas-kananbawah).

Note: Bukan beneran diputar 45 derajat ya, maksudnya “lihat”nya begitu. Masalah detil implementasinya coba dipikirin.

D. Lho?
Ya… just do it aja, ga susah, semua peserta juga bisa.

E. Jalan-Jalan
Tidak ada satupun tim yang berhasil menyelesaikan soal ini, jadi jelas ini soal yang paling sulit di kontes kali ini.

Sama seperti penyisihan, solusi soal tersulit kali ini juga menggunakan matrix exponentation.

Pikirkan dulu formula dp-nya:

f(a,b,m): ada berapa banyak path untuk mencapai goal dengan K langkah di mana sekarang kita berada di node a dan sebelumnya berada di node b dan sudah melangkah tepat m kali.

f(a,b,m) = jumlah f(c,a,m+1) untuk semua c = a..h dan c != b.

Jika formula di atas dimasukkan ke dalam matrix, tentunya parameter m tidak perlu kita ikutkan. Masih ada a dan b? Ya masukin aja semua…

Matrixnya jadi kira-kira gini:

[ f(a,a,1), f(a,b,1), f(a,c,1), ..., f(b,a,1), ..., f(h,g,1), f(h,h,1) ]

Trus pikirin matrix transisinya, supaya kalau dikaliin hasilnya jadi:

[ f(a,a,2), f(a,b,2), f(a,c,2), ..., f(b,a,2), ..., f(h,g,2), f(h,h,2) ]

Node di graphnya kan cuma ada 8, total statenya jadi cuma ada 8*8 = 64, kecil. Jadi matrix awalnya 1 x 64 dan matrix transisinya 64 x 64. Sisanya tinggal urusan permatrixan.

F. Robot Pos
Soalnya ga jelas =.=. Awalnya gw kira kota awal dan tujuannya itu berupa titik, tapi setelah baca contoh input, sepertinya yang dimaksud kota itu adalah garis. Intinya, robotnya mulai dari sisi kiri menghadap ke sisi kanan, pertanyaanya adalah apakah si robot bisa mencapai sisi kanan yang jauhnya infinite.

Kunci untuk mencapai sisi kanan ada pada aturan ke-3: “Jika pada suatu waktu ia diperintahkan sekaligus belok kiri dan kanan, robot tersebut akan tetap melaju lurus tanpa belok.”

Coba perhatikan contoh input 3: 30 dan 22.

Si robot akan bergerak lurus (karena aturan ke-3) pada saat menempuh jarak ke 330. Ketika mencapai jarak 330, si robot sudah belok kiri sebanyak 330/30 – 1 = 10 kali, dan belok kanan sebanyak 330/22 – 1 = 14 kali. Setelah berbelok ke kiri sebanyak 10 kali dan ke kanan sebanyak 14 kali, maka si robot akan menghadap ke arah kota tujuan, dan kemudian dia akan bergerak lurus karena aturan ke-3, sebelum ia mulai berbelok-belok lagi. Dengan demikian perlahan-lahan si robot akan bergerak ke arah kota tujuan.

Ringkasnya, Jika selisih jumlah belok ke kiri dan ke kanan sebelum robot bergerak lurus adalah kelipatan 4, maka jawab Ya, jika tidak jawab Tidak.

EDIT: Setelah dipikir-pikir lagi… ternyata jika jawabannya Ya dan robot itu mulai dari posisi (x,y) menghadap ke kanan maka semua posisi dari (x,y), (x+1,y), (x+2,y), …, (INF, y) itu bisa divisit Jadi kalo kotanya berupa titikpun ga masalah, keren juga ini soal…

G. Arsitek Perumahan
Secara intuitif kan bisa kepikir kalau cost minimum itu bisa didapatkan dari deret yang terurut (contohnya sengaja kasi ga sorted supaya misleading). Jadi yang perlu dilakukan pertama kali adalah sort datanya, O(N lg N). Kemudian u/ setiap h[i], cari pasangannya h[j] sedemikian sehingga h[j] – h[i] ≤ M dan j adalah maksimal. Gimana cara mencarinya? binary search. Total O(N lg N).

H. Si A, Si B, Si C II
Pertama, urutkan dulu {X, Y, Z}. Penjelasan berikut mengasumsikan X < Y < Z.

Partisi rentang bilangan 1..Z menjadi 3 bagian:
a: 1..X
b: X+1..Y
c: Y+1..Z

Kita definisikan f(p,q,r) adalah jumlah triplet di mana orang pertama menggunakan rentang p, orang kedua menggunakan rentang q dan orang ketiga menggunakan rentang r.

Rentang a bisa dipakai 3 kali, rentang b hanya 2 kali, sedangkan rentang c hanya bisa 1 kali. Jumlahkan saja semua kombinasi penggunaan rentangnya.

ANS = f(a,a,a) * 1 + f(a,a,b) * 3 + f(a,a,c) * 3 + f(a,b,b) * 3 + f(a,b,c) * 6

f(a,a,b) dikali 3 karena ada 3 kombinasi untuk f(a,a,b) yaitu : f(a,a,b), f(a,b,a) dan f(b,a,a). Begitu juga yang lainnya.

Jika X ≤ Y dan/atau Y ≤ Z (seperti di contoh 1 dan 2), tinggal disesuaikan saja cara di atas.

I used this structure to solve problem H on Jollymoo 11 (a local “practice” contest at BINUS University). The problem was originated from Codeforces – Yandex Algorithm 2011 Round 1 Problem D, “Sum of Medians”, which can also be solved by segment tree.

Problem: supposed you want to create a data structure that serves these operations:

• ADD x, add x into the set, assuming x is not in the set.
• DEL x, remove x from the set, assuming x is already in the set.
• COUNT a b, return the number of elements x which is between a and b, inclusive.

Let x be between 1 and 100,000. If x is larger than that but the distribution is sparse, you should “normalize” the data first into 1..P where P is the number of distinct x.

Those who have learnt segment tree should recognize this problem as it can simply be solved by a segment tree structure. Yes it does, but here I want to show another structure that can also solve this problem.

First, create a “square” array to contain all the number. By “square” I mean if N is 100,000 then you should create an array of ~400 x ~400. Actually it’s not necessarily a square (you can go with 300 x 500, etc) but square is the ideal size.

Let the array size be M x M and let’s call it ARR[1..M][1..M]. Note that I use 1-based index array, you should make any necessary change in following explanation to meet your need.

We will use ARR[1] to store all values between 1 and M, ARR[2] to store all values betwen M+1 and 2M, ARR[3] to store all values between 2M+1 and 3M, and so on. I’ll call ARR[1..M] as slots. You can just declare each element as a boolean value because we only need to know whether there is an element of that value.

We also need an array of integer of size M, let’s call it NUM[1..M]. We will use NUM[c] to store the number of elements that are currently exists in slot ARR[c].

For each ADD x query, we need to do this:

• Find the appropriate slot for x (eg. if M is 400 and x is 900, the slot might be ARR[3]).
• Turn on the flag on ARR’s element which corresponds to x (eg. ARR[3][100] for x = 900 and M = 400).
• Recalculate NUM of that slot (eg. NUM[3]).

You can see that NUM[c] at any time will always hold the number of elements in slot ARR[c].

In this problem, ADD query is O(1). Finding the appropriate slot is easy, turning the flag on is also easy, recalculating NUM is also trivial (just increase its value by one). In another problem, ADD query might need more process (as in “Sum of Median”).

For each DEL x query, do the similar things as in ADD query (turn off the flag and recalculate NUM).

For each COUNT a b query, we need to do this:

• Find the appropriate slot for a and b.
• Iterate in slot a from element which correspond to a to M (the end), count the number of existing elements.
• Iterate in slot b from 1 (the beginning) to the element which correspond to b, count the number of existing elements.
• Iterate NUM from slot a+1 through slot b-1, sum the number of existing elements.

COUNT query is O(sqrt(N)) as we need to iterate through at most M elements.

As you can conclude, this structure need O(sqrt(N)) for each query, worse than segment tree which need O(lg(N)), but it’s simpler to code for you who are not familiar with segment tree.

Soal-soal Jollymoo 11 bisa dilihat di SINI.

Soal-soal kontes ini beberapa diambil dari arsip kontes-kontes lama (SRM, Codeforces, dll) yang diubah dan disiapkan, jadi gw ga ngambil credits apapun untuk soal-soal yang ada.

A. Po Memungut Bola
Mula-mula formulasikan dulu soal ini ke dalam bentuk:

f(S) = _{i=1..N, j=1..N, i and j not in S} min{ f(S U i U j) + cost[0][i] + cost[i][j] + cost[j][0] }

S: himpunan yang berisi bola-bola yang sudah dikumpulkan.
f(S): jarak minimum yang diperlukan untuk mengumpulkan semua bola yang tidak ada di dalam himpunan S.
U: union, gabungan.
cost[a][b]: jarak dari a ke b.
0: posisi awal Po.

Perhatikan bahwa i bisa sama dengan j, yang artinya hanya 1 bola yang diambil. Tentunya himpunan di atas bisa direpresentasikan ke dalam bitmask karena N maksimal hanya 20, sehingga formula di atas bisa kita implementasikan ke dalam dynamic programming. Berapa kompleksitasnya? Ada sebanyak 2^N state dan untuk menghitung sebuah state diperlukan iterasi N² sehingga total kompleksitas waktunya adalah O(N² . 2^N). Solusi ini masih TLE.

Solusi di atas bisa kita optimisasi dengan ide seperti ini: Seandainya terdapat 4 bola: a, b, c dan d; urutan pengambilan a-b dan c-d (ambil a dan b, kemudian ambil c dan d) akan menghasilkan total jarak yang sama dengan urutan c-d dan a-b. Dengan ide ini, kita bisa menghilangkan salah satu iterasi (i) dan cukup melakukan iterasi pada j (pilih satu bola sembarang dan iterasi pasangannya). Dengan demikian total kompleksitas yang diperlukan menjadi O(N . 2^N).

Note: hanya perlu menambahkan satu line “break;” di solusi yang O(N² . 2^N).

B. Bilangan K-Prima
Ada beberapa yang menyelesaikan soal B dengan bar-bar, iterasi dari 1..N dan cari ada berapa bilangan yang k-prima. Setiap bilangan diuji k-primanya dengan iterasi akar n. Solusi ini cukup ok, tapi karena time-limitnya hanya 1 detik, solusi ini pasti dapat TLE (tanpa optimasi).

Pertama, hitung dulu (precompute) faktor bilangan prima terbesar dari setiap bilangan dari 1..MAXN (100.000). Ini bisa dilakukan dengan modifikasi algoritma sieve.

int f[100005] = {0};
for ( int i = 2; i <= maxn; i++ ) {
  if ( f[i] == 0 ) {
    for ( int j = i; j <= maxn; j += i ) {
      f[j] = i;
    }
  }
}

Code di atas ada iterasi dua tingkat tapi kompleksitasnya bukan O(N²), tapi hanya O(N lg N). Mengapa? ada hubungannya dengan harmonic series.

Berikutnya, untuk setiap query tinggal looping dari 1..N dan hitung ada berapa bilangan yang memenuhi k-prima.

C. Gaji Perusahaan
Rasanya soal ini nggak susah, tinggal DP sederhana aja.

D. Putar dan Berputar
Soal ini bisa diartikan begini: diberikan sebuah directed graph dimana setiap node hanya memiliki sebuah out-degree, cari path terpanjang yang tidak melewati edge yang sama dua kali.

Tentunya graph tersebut bisa memiliki cycle, jadi kita terlebih dahulu harus mencari semua cycle yang ada pada graph tersebut. Jika semua cycle sudah didapatkan, sisanya mudah.

E. Himpunan Bilangan Pembagi
Soal ini juga nggak susah, ada banyak approach yang bisa dipakai buat menyelesaikan soal ini, salah satunya adalah DP. Bisa juga diselesaikan dengan menghitung jumlah faktor prima dari N.

Contoh, 72 = 2³ * 3², sehingga total ada (3 + 2) + 1 bilangan yang lebih kecil dari N yang habis membagi N dan bilangan itu juga habis dibagi bilangan yang lebih kecil.

72 = 2³ * 3²
24 = 2³ * 3¹
8 = 2³ * 3⁰
4 = 2² * 3⁰
2 = 2¹ * 3⁰
1 = 2⁰ * 3⁰

EDIT: Yang terakhir seharusnya 2⁰ * 3⁰, tadinya 2⁰ * 3². Thanks to William.

F. Interval
Hanya ada 4 jenis output yang mungkin, yaitu:

• Tidak ada interval yang overlap, jika demikian output semua interval.
• Tidak ada interval yang demikian, output -1.
• Ada satu interval yang demikian.
• Ada dua interval yang demikian.

Keempat kemungkinan output tersebut sudah diberikan di contoh input, jadi seharusnya tidak ada yang terkena “tricky case” di soal ini.

Untuk menyelesaikan soal ini, kita perlu mengetahui berapa interval yang bisa diambil maksimal sedemikan sehingga tidak ada interval yang saling overlap. Jika kita mengetahui ini, maka interval yang tidak diambil itu adalah interval yang akan menyebabkan overlap.

Mula-mula urutkan data interval yang ada berdasarkan R (end) secara menaik, dan ambil interval satu per satu namun interval tersebut tidak boleh overlap dengan interval-interval yang sudah diambil. Mirip dengan interval selection problem kan?

Jika dari proses di atas didapatkan tidak ada interval yang tidak diambil, maka output semua interval. Jika ada dua atau lebih interval yang tidak diambil, maka output -1. Jika hanya ada satu interval yang tidak diambil, kita harus memeriksa bagaimana interval ini overlap dengan interval yang lain. Jika interval ini hanya overlap dengan satu interval lain, maka output interval ini dan interval yang overlap itu (dua angka), tapi jika interval ini overlap dengan dua atau lebih interval lain, maka output hanya interval ini (satu angka).

G. Koleksi Perangko
Soal mudah. Jual semua perangko yang pak Janggut punya dan beli lagi perangko-perangko dari harga yang paling murah.

H. Jumlah Data Terurut
Sepertinya ini soal yang paling sulit yang ada di Jollymoo 11. Felix Halim berhasil AC di soal ini, TAPI solusi dia seharusnya masih TLE. Test case yang gw generate untuk soal ini emang ga terlalu kuat, cuma random aja, gw akan generate case criticalnya dan reupload casenya ntar.

Soal ini bisa diselesaikan dengan segment array (gw jelasin di post lain deh) atau segment tree. Solusi segment tree sebenarnya baru kepikiran beberapa hari yang lalu setelah kontes selesai.

Solusi segment tree:
Range bilangan input bisa mencapai 1 miliar, tapi jumlah angka yang berbeda tidak akan lebih dari N, oleh karena itu kita perlu “normalisasi” dulu data-datanya. Caranya? baca dulu semua input dan simpan angka apa saja yang muncul. Ubah angka-angka itu jadi dari 0..X, di mana X adalah jumlah bilangan berbeda yang muncul.

Gunakan segment tree untuk menangani setiap query insert/delete/sum. Setiap node di segment tree perlu menyimpan dua informasi ini:

• Banyaknya bilangan yang ada di subtree node tersebut.
• SUM[0..4] dari subtree tersebut.

SUM[0] adalah jumlah semua bilangan kelima dimulai dari index-0: 0, 5, 10, 15, …
SUM[1] adalah jumlah semua bilangan kelima dimulai dari index-1: 1, 6, 11, 16, …
SUM[x] adalah jumlah semua bilangan kelima dimulai dari index-x: x, x+5, x+10, …

Jika kita ingin menghitung SUM[2] dari sebuah node, maka kita hanya perlu menjumlahkan SUM[2] dari node kiri dan SUM[p] dari node kanan, di mana p adalah index yang sesuai dengan jumlah node yang ada di subtree kiri. Misalnya di subtree kiri ada 2 node, maka di subtree kanan kita memerlukan SUM[0] untuk menghitung SUM[2] dari parentnya.

KIRI KANAN
[a b] [c d e f]

c adalah index-0 dari subtree kanan, sehingga untuk menghitung SUM[2] dari parent node, kita perlu menjumlahkan SUM[2] dari node kiri (yang nilainya 0) dan SUM[0] dari node kanan.

I. Tikus Pintar
Ga banyak yang bisa dijelasin, BFS/DFS aja, graphnya kan berupa tree jadi harusnya ga susah.

Babak penyisihan Compfest mahasiswa barusan berlalu, ada 5 soal, 4 mudah dan 1 “susah” (susah buat yang baru belajar). Kemarin gw dapat link scoreboardnya, tapi sekarang scoreboardnya udah berubah jadi untuk kategori SMA. Sepertinya link itu cuma temporer, jadi ga gw cantumin di sini (karena ntar bisa ilang juga). Hasilnya, sekitar 20an tim berhasil solve 4, tidak ada tim yang solve 5. Dari BINUS kalau ga salah ada 4 tim yang lolos ke final, dan ada satu tim veteran yang memalukan (termalas #1 + termalas #2 + manusia-normal) =.=

Dari kemarin gw ditanyain solusi soal D (soal yang ga ada yang bisa solve di kontes), jadi gw kepikiran untuk bikin write-up penyisihan Compfest mahasiswa yang barusan lewat. Soal D ini emang rada lain sendiri ngelihat soal-soal lain yang tingkat kesulitannya jauh banget sama soal D .

Soal penyisihan mahasiswa bisa dilihat di sini.

A. Bayar atau Kabur
Soal bonus? Kalau ga bisa, coba belajar solve soal-soal mudah dari online judge dulu.

printf( "%d\n", (s[0] == 'b' ? X : 0) - L * R * J );

B. Kalimat Logika
Mula-mula pisahkan elemen-elemen dalam kalimat input berdasarkan karakter ‘^’. Karena di soal ini hanya ada karakter konjugasi (‘^’) maka soal ini menjadi mudah untuk diselesaikan. Seperti yang kita ketahui, jika ada salah satu elemen bernilai S, maka nilai kebenaran kalimat tersebut pasti salah.

Dengan demikian kita hanya perlu memeriksa apakah ada elemen yang bernilai S atau ~B. Jika ada, maka output “salah”. Jika tidak ada, kita harus memeriksa apakah ada elemen yang berupa variable, jika ada maka output “mungkin”, jika tidak maka output “benar”. Kalimat yang memiliki variable tidak mungkin memiliki output “benar” karena kita tidak bisa membuat tautologi hanya dengan operasi konjugasi (‘^’) dan negasi (‘~’).

C. Titik dan Garis
Kurang ngerti apa yang dimaksud soalnya dengan “titik”. Apakah hanya titik yang berada di sisi/sudut persegi, atau titik yang timbul karena perpotongan garis di dalam persegi juga dihitung. Tapi kalau dilihat dari contoh input/outputnya, sepertinya pemahaman yang kedua yang benar.

Setiap penambahan sebuah garis yang ke-k, bisa menambah jumlah titik sebanyak k+1, yaitu k-1 titik yang timbul dari perpotongan dengan k-1 garis sebelumnya, dan 2 titik yang terletak di sisi persegi.

Soal ini juga tidak menyebutkan berapa batasan input untuk N, hanya disebutkan berupa “bilangan bulat” (10¹⁰⁰ kan juga bilangan bulat). Tapi kalau kita asumsikan inputnya muat dalam integer (32 bit), maka solusinya bisa dibruteforce (coba tambahkan garis satu per satu), karena jumlah garis yang dibutuhkan tidak akan lebih dari akar dari N.

EDIT: ternyata batasan input ada tertulis di soal (di bagian problem description, bukan bagian input :p). N maksimum hanya 1 miliar, artinya muat di dalam integer 32 bit.

D. Coin Change Deluxe
Sepertinya ini soal yang paling sulit di penyisihan Compfest 2011 untuk tingkat mahasiswa (tidak ada tim yang berhasil menyelesaikannya). Pas baca soal ini sebenarnya langsung kepikiran solusinya, tapi jadi bingung koq ga ada tim yang berhasil solve? (lumba-lumba ITB mana? si ricat mana?) Belakangan baru tahu ternyata itu lumba-lumba ga ikutan. Si ricat? patut dipertanyakan dia ngapain aja x(.

Untuk solve soal ini, kita harus sudah bisa dynamic programming (DP) dan perkalian matrix.

Bagi yang sudah bisa DP, tentu bisa langsung berpikir bagaimana formula DP nya.

f(X) = f(X-M1) + f(X-M2) + ... + f(X-MN)

Dengan kompleksitas space O(X) dan kompleksitas time O(X.N).

Karena X bisa mencapai 1 miliar, tentu solusi DP di atas tidak mencukupi. Solusi lainnya? Matrix Exponentation. Topik ini pernah saya bahas (sekilas) di sini, coba dipelajari kalo belum pernah belajar.

Kalau diperhatikan, formula DP di atas itu mirip dengan formula Fibonacci. Jadi kita bisa menyelesaikan soal ini dengan membangun matrix berukuran 32 x 32 (karena M maksimal adalah 32) dan mengisinya dengan nilai-nilai yang diperlukan untuk perhitungan perkalian matrixnya.

Contoh,

misalnya hanya ada 2 jenis koin yaitu 2 dan 5, maka formula DP kita adalah:

f(X) = f(X-2) + f(X-5)

Sehingga kita bisa membuat matrix:

0 0 0 0 1
1 0 0 0 0
0 1 0 0 0
0 0 1 0 1
0 0 0 1 0

Note: matrix di atas gw perkecil jadi 5 x 5 untuk mempermudah gambarnya aja, aslinya 32 x 32.

Sekarang coba perhatikan perkalian dua matrix berikut:

                   0 0 0 0 1
                   1 0 0 0 0
(f0 f1 f2 f3 f4) * 0 1 0 0 0  =  (f1 f2 f3 f4 f0+f3)
                   0 0 1 0 1
                   0 0 0 1 0

Sesuai formula DP kita, f₀+f₃ adalah f₅. Dengan demikian matrix A (f₀ f₁ f₂ f₃ f₄) jika dikalikan dengan matrix B (matrix transisi) akan menghasilkan matrix A’ (f₁ f₂ f₃ f₄ f₅), yang jika dikalikan lagi dengan matrix B akan menghasilkan matrix (f₂ f₃ f₄ f₅ f₆) dan seterusnya.

Nilai dari f₀ adalah 1 dan f_i=1..32 bisa digenerate dengan DP. Sedangkan untuk i=33..X, kita selesaikan dengan matrix di atas.

Perkalian matrix bersifat asosiatif, artinya A * B * B = (A * B) * B = A * (B * B). Dengan demikian kita bisa menghitung solusi kita dengan A * B^X, di mana A adalah matrix awal/hasil (yang kiri) dan B adalah matrix transisi (yang kanan). Mengalikan dua buah matrix memerlukan kompleksitas O(s³) di mana s adalah ukuran matrix (di sini adalah 32), dan menghitung pangkat p^X memerlukan kompleksitas O(lg X) dengan divide and conquer, sehingga total kompleksitas time yang diperlukan untuk menyelesaikan soal ini adalah O(s³ . lg X).

E. Sakla Lhompa
Beberapa analisa diperlukan untuk menyelesaikan soal ini.

Jumlah langkah yang diperlukan oleh Sakla dan Lhompa adalah sama. Seandainya bidak Sakla dan Lhompa bisa menempati tempat yang sama (bidak yang datang belakangan tidak mendapat giliran tambahan), maka tentu saja Sakla akan selalu menjadi pemenang (karena Sakla jalan duluan). Jadi jika Lhompa ingin menang, ia harus mendapatkan “loncatan extra” dari bidak Sakla.

Lhompa hanya bisa mendapatkan loncatan extra jika dan hanya jika jumlah langkah minimum yang diperlukan untuk mencapai tujuan adalah genap. Bayangkan jika papannya berukuran 1 x 5, maka diperlukan 4 lompatan untuk mencapai tujuan (ada 3 petak yang berada di antara Sakla dan Lhompa). Karena Lhompa selalu mendapat giliran kedua, maka petak tengah yang merupakan “pertemuan Sakla dan Lhompa” pasti dimasuki dahulu oleh Sakla, yang artinya Lhompa bisa mendapatkan giliran tambahan di petak itu. Kondisi ini bisa digeneralisasi menjadi papan berukuran N x M (selalu ada strategi untuk Lhompa agar mendapatkan giliran tambahan jika jumlah langkah yang diperlukan adalah genap), dengan demikian kita hanya perlu memeriksa apakah (N – 1) + (M – 1) adalah bilangan genap atau ganjil.

Soal-soalnya bisa dilihat di sini.

• Tentang Peserta
• Pembahasan Soal