Minggu, 07 April 2019

ICPC WF 2019 Porto, Part 3

Day 4 - Contest Proper & Closing Ceremony

Waking up as usual, then we have breakfast. I completely forgot that usually I eat less (or not eating at all) before contest, so that I won't be sleepy during contest. Fortunately, there is still enough time for some nap, so there is no problem. After I woke up, we went to Alfândega.

There is still some time before team check-in, so I just listen to music for a while. After that, the team check-in opens, and we checked-in. In the waiting hall, we sat across Binus team. Like yesterday, Bill Poucher went around the hall, in case there is any team who want to take pictures with the ICPC trophy. Inigo wanted to take a picture, so we queued for taking picture.

I didn't notice my badge was flipped :s
Source: ICPC Live
After we took picture, Binus also wanted to take picture with the trophy. While they were waiting for their turn, their seat got taken over by another team. I wasn't paying attention when this happened :s Sorry! Anyway after a minor table slamming like yesterday (again, baka baka shi), finally it's time for us to go to the contest floor. Along the way, the MC said something like "touch the trophy for good luck", and it seems Inigo touched it. Anyway, we go to our workstation, and it looks pretty similiar with yesterday, except that the keyboard already has stickers that we put yesterday. As usual, "Do not touch anything".

All team is ready in their workstation, but the countdown timer still shows around 13 minutes before contest. John Clevenger first announced that there will be workspace in our computer, which is nice. Then, he asked Executive Director (Jeff Donahoo) and WF 2019 Director (Fernando Silva) whether the contest is ready, and they said yes. And so, he do "ICPC time warp", moving the countdown timer into around 3 minutes left, so we will start the contest on 11:50 in local time.

I checked my hand. Seems it's not trembling at that moment. Like usual, I'll be in charge of setting up the environment first, while Degol and Inigo read the problems first.

Source: Suhendry
Yawning is contagious they said
Source: Suhendry

And so, the contest started!

I begin by opening the DOMJudge and scoreboard, CLion, then terminal. I moved CLion to another workspace, while the terminal and browser is in one workspace (this is our usual configs). When I tried to create files {A..L}.cpp from terminal, I can't get the '{' right. Weird. And then I figured that the keyboard mapping has been reset into Portuguese layout; After changing it to US layout everything seems correct for me. I tried coding simple code and compile it, seems working.

After that I read my usual part in problemset, the last third of the problemset. Not sure how many problems are there, so I started from H. Hmm, so given graph of some directed pseudotrees (cycle with trees attached to it), for each node find how many nodes can reach it in at most K steps. Solution is pretty trivial; Answer for nodes in tree part can be calculated with prefix sum by using preorder numbering, and answer for nodes in cycle part can be calculated with circular prefix sum. While solution is pretty trivial, I'm quite scared since it seems the coding part can be tricky. Anyway, since this is WF and I believe easy problems in WF will have difficulty like this one, I decided to solve this first. Inigo and Degol both seems still reading the problems.

So I took the hot seat and start coding. I still have some small trouble with the keyboard, but managed to code it anyway. I changed small parts of code multiple times, and made several stupid bugs like off-by-one error or forgot to increment a counter. After it passed the sample, I submit it since it seems the sample already covered most cases I can think of. After waiting for around 1-2 minutes, we got H - Hobson's Trains Accepted on minute 33!

After that, I asked Degol about any other doable problems, while Inigo is sketching J. He said that E and A doable, and he is still trying to figure out E. A seems pretty greedy, and he explained the problem to me. Basically given 2 rows where each column has price and height, sort each rows by non-decreasing price, but height of the first row must be higher than the height of the second row in each column. I thought of a simple greedy by using multiset: After sorting each row, maintaining multiset of height for each rows. Take any column from the second row, pairing it with the smallest column that is higher than it from the first row. This seems wrong, since a lot of teams hasn't got Accepted in this problem. I decided to code it anyway.

After I finished coding and fixed the bugs, I tested on sample. Weird, if I take the smallest from the second row, it will be wrong in sample. Yet, when I take the biggest, it will get correct. Since we are pretty much reckless, we submit, and as expected, it got WA.

Our mascot
Source: ICPC Live
Since I'm not sure what the correct idea for A, I decided to postpone this problem. Degol than said he has an idea for E, but not sure how to code it. I just asked him to explain his idea. In problem E we are given a graph, that I guess can consist of several components. Looking at the output, it seems we have to print some edges. Degol said that if the component is a tree, we take the edges connecting with a leaf. If the component is not a tree, then it will be like cycle attached with trees, and we take the edges from the cycle into the tree. I found it weird, since the problem doesn't seems like we can be given pseudotree. Then I asked him if there is edge between two cycle, and he said we can skip that edge. At this point I guess he didn't really mean cycle, just a non-tree subgraph. He also added that if the component is a tree consisting of 2 nodes, the same edges has to be printed twice. I kinda doubt it, but proceed to code it.

Checking whether a component is a tree is trivial, just check whether V = E - 1. After that, finding leaves can be done by searching nodes with degree 1. For the non-tree component, I do it by using toposort, which is pretty similar with H but this one is undirected. After I finished coding, I checked sample, and it didn't pass the 1st sample. The order of (u, v) of edge is wrong. Degol than said the correct order, which I don't really remember how. Now it passed sample. Just to be sure, I tried tree with 2 nodes, and it printed the edge twice as intended. I submit it, and we got E - Dead-End Detector Accepted in minute 64! I don't really remember the last time I code something blindly without even knowing the problem, probably this is the first one?

Meanwhile Inigo is still working in J, I heard him asking Degol if there is parallel ternary search. I checked scoreboard, and it seems the next easy problem is D. I asked Degol about problem D, and the problem seems to be about bracket matching. Given circular string, find where can we start that maximize the number of valid bracket matching. After thinking for a while, this problem seems pretty straight-forward: For each number, we just find all places that can be the start of the valid bracket matching for that number. Then, we can use prefix sum again to speed up adding for each correct position. For checking whether starting from such position will result a valid bracket matching, we can use classic segment tree for bracket matching. To simplify stuff, we can concat the sequence twice so we don't have to bother with the circular detail. I'm confident that I can solve this one, and so I started to code. I told Degol and Inigo to focus on A now, since it should be a pretty easy problem and not solving it may lower our moral.

When I finished coding D, I tried sample and it was wrong. Seems I make some bugs. While I was debugging, Inigo and Degol seems to got the correct idea for A. I told them to write the solution first on paper while I was still debugging D. After quite some time, I found the bug. It was shadow declaration ~_~ I put multiple "idx" variables, and yeah you should understand the rest. I remember there is flag for warning shadow declaration, but I forgot what is it :s After bug-fixing, I finally managed to get the sample correct. Degol hasn't made any testcase, so I.. just submit it. Luckily, we got D - Circular DNA Accepted in minute 92!

Degol then proceed to code A with Inigo. I told him that they should be able to take most part from my A code. Later I noticed they renamed the original A.cpp into Ayaz.cpp :s I take a look on the scoreboard, seems the next doable problem is G. Oh, I also noticed that H still don't have really many AC, maybe it's not as easy as I think? I believe it's still on the easier part of this WF problemset though.

I read problem G. Huh, about tree, string, and query. Wait, this problem seems awfully similar, if not the same with the problem Wiwit submitted for Ngoding Seru. The problem is about calculating for each query how many people has name with prefix given in that query. For the name itself we are given a tree where each edge has an alphabet, and the name can be represented by the path from the node into the root. I remember that Wiwit said his solution is suffix array-based, while I remember that I found another solution using Aho-Corasick trie. 

After sketching a bit, I found a solution: build Aho-Corasick trie from the reversed query strings. After that, we create tree from the failure functions of the trie. Then, traverse the given name tree, adding counter in the corresponding node in Aho-Corasick trie. Finally, the answer for each node will be the sum of counters in the subtree of the failure function tree, which can be calculated in a single DFS. To get answer for each query, just print the sum of counters for the corresponding node.

Source: ICPC Live
I feel pretty lucky that the string problem in this WF can be solved with Aho-Corasick, which probably is the only string thingy that make sense to me beside hashing. I wrote some pseudocode, and when I finished, I asked Degol and Inigo about their progress. It seems they are struggling a bit in coding their solutions. I asked them to explain their idea, and they told me if the multiset of 2nd row is smaller do this, and if the 1st row is smaller then do that. I then took over the coding part, although I also has some trouble. When I finished, I checked sample and it seems correct. We submit, but it still got WA. Since I have idea for G, we printed code for A and I proceed to code G.

While I was coding G, Degol found a bug in A. I fixed it and test on samples. Seems correct, so we submit it. It got another WA. We print it, and I continued coding G. Coding G was pretty fast; However, when I tested it on sample, my code produced a wrong output. Most of them are bigger than they should be. While I was trying to debug, Degol told me a major bug in A about indexing, which surprisingly wasn't caught in sample. I switched to A, and then changed the buggy indexing part. After that, we submit it. At the 4th try, we finally get A - Azulejos Accepted in minute 115!

After that Degol and Inigo continued trying to solve other problems, while I am still debugging G. When I printed the sum of counters, they are correct. So why are my output different? And then when I checked the printf part, I feel extremely stupid. All this time, while I wanted to output dp[queryPos[i]], the one I outputted was queryPos[i]. I'll just go back to my cave of shame. After I fixed it, of course the output become correct. I submit it, and we got G - First of Her Name Accepted in minute 128!

At this point we were at the medal range. I know that it won't be for long though, I know that we are not that strong lol.

I asked Degol and Inigo what the next doable problems are. They said B and J. When I took a glance on B, it seems there are geometric picture and I immediately said "nope nope nope". Degol assured me that it is not really geometry problem, it is only one part of the problem. Basically the problem is about building arch for bridge, with the arch having half circle on top of it, and the part above those half circles are the part of the bridge. We have some points and we want to build some arch so that the cost is minimum and no points are on the bridge. The geometric part is only checking whether we can build arch from i-th point to j-th point, while the rest is basic O(N2) DP. Checking whether a point is above the half-circle can be done by checking its y-coordinate whether it's above the center of half-circle or not, and if yes then check whether the distance of the point with the center of the half-circle exceeds the radius or not.

Problem J is about golf scoring, and after Inigo explained to me, both of us agreed that this boils down to checking multiple convex lines. He said he has solution which has big complexity, that I think it won't pass. Judging from the problems, I told Degol and Inigo to focus on J, while I focus on B. Most of the times I hate doing geometry, but I have a feeling that B is not really a geometry problem.

Source: ICPC News

So like most of the time, I break down the equation for constraint checking in B. After a while, I figured out that the check can be done by finding the maximum value from several line equations. This can be done using dynamic CHT, which luckily we have added to our TRD. However, the complexity will be O(N2 log N). Not sure it will pass since there are constant factors playing here, so I decided to just try it anyway. If TLE, either I will abandon it or prune it like hell.

It took quite a while to copy code for TRD and to write the code to solve the problem. After I finished, the output for the 1st sampe didn't match the correct output. Weird. Turns out that I had typo here and there. After I finished, I submit and got WA. Nice, I was expecting TLE/AC and now I got WA. After that I found that there is a wrong comparator (> instead of >=), and change it. Submit, and it still got WA.

Since I am not sure what the problem is, I go back to my scratch paper while Inigo and Degol are discussing J. I wrote all variables and equations from the beginning again. To my horror, I found the problem: I got different variables mixed up! I have d = (x[j] - x[i]) and m = (x[i] + x[j]) / 2, and while I was writing the equations I got them mixed up. I asked Degol to help me check while I am writing the equation again from the beginning. When I finished, I feel stressed since now we have two unknown variables, d and m. However, I noticed that d can be transformed into m since x[i] is fixed. Now we only have one unknown variable. Eureka!

I quickly changed the code according to the current equations. It turns out we still have some bugs in the equation, so we have another 3 wrong submissions. While I was at loss, Inigo said he wanted to code J, so we printed code for B. When Inigo is about to code, I found what probably was the last bug in B. I fixed it, and as it passed sample (like 5 of our previous submissions :( ) we submit it. Finally, we got B - Beautiful Bridges Accepted in minute 223! If I remember correctly at this point we were at the 16th rank.

Inigo then take over the hot seat and proceed to code J, with Degol watching him. I read the rest of problems that I haven't read: C is nasty, F seems DS-like, I has grammar rule in it which kinda turn me off, K seems interesting math / probability but I think it will be too hard for us. And so, I decided to think for F. It seems DP with Segment Tree problem, but done naively will be too slow. I think that we can prune it by keeping segments where the DP values are the same, that is, by keeping track any i such that i and i+1 have different DP values. However, I don't know the complexity for this one, as I think it can be O(N2 log N) which will be too slow. I wrote pseudocode for F.

Around this time, the scoreboard froze, with us at rank 17th and 6 problems solved.

Degol and Inigo seems to have trouble in J. Apparently, their lemma was wrong. And so, I decided to code F since I already have a pseudocode, and tell Degol and Inigo to write their J solution in paper first if they managed to fix it. I was quite in a hurry, and I made lots of weird bug in F. When I finally finished coding and get samples correct, I submit it, and got WA. Pretty weird, since I expected TLE/AC. Anyway, Degol and Inigo didn't manage to fix J, so I decided that we should focus on F. After spamming for F until the last minute, I still can't change that WA into TLE/AC :(

And so, the contest is finished!

So we didn't manage to solve another problem in the last our, which means our rank will be >= 17th. I'm not disappointed at all; I mean we have tried our best, and I managed to fulfill my goal (have fun, perform better than last time, and not have any regrets). I am not regretting that I failed F; it was desperate attempt, although I am curious why it got WA.

Source: Pak Denny

Pak Denny and Bu Citra then comes to our workstation, congratulating us. We said that we didn't manage to get F Accepted, which he said is OK considering the result is already good enough. I asked about Binus and NUS, and it seems Pak Denny still didn't know their result. FJ pass by, and we said we didn't increase our AC in the last hour. After that, we took photo in our workstation. The team sitting on our right was confused where their balloon is, whether it's the one attached to the right side of workstation or the left side. We said that it's the right one. And then I noticed, the team on our right solved 6 problems as well before freeze, they are pretty strong @_@

I checked FB and got many notifications. It seems there is a thread about ICPC WF in Suhendry's FB, where people seems to be excited about this year's UI performance, saying we have potential to get medal. Sorry to disappoint though :P Although I am already used in disappointing others now :( The thread can be found here, it's in Bahasa Indonesia (last time I checked the post seems to be public)

After that we went back to the chillzone. Before going back, we "steal" some stuffs such as calculator and mousepad :P As far as I remember we are allowed to do so. In chillzone, I finally eat the lunch provided since the contest starts (it's in the bag in the workstation). It taste pretty weird to be honest :| In LINE chat, Rakha said Inigo and Pak Denny won something from ICPC Live (btw, Inigo and Pak Denny is rather diligent in doing ICPC Quest). I checked, and it's true. I told Inigo and Pak Denny, and then they went to the ICPC Office. After that, there is ICPC Challenge award ceremony for the non top-3, but I am not really interested.

After around 19:20, the closing ceremony still hasn't started. I take a look around chillzone, it's weird that there are less people than before. Pak Denny asked nearby volunteer, but she said that the ceremony still hasn't started. We decided to go to the closing ceremony venue anyway, it's on the contest floor. To my annoyance, the seats are already pretty much filled. It seems we can actually go there even before the closing ceremony started or at least announced will be started. We take a seat very far in the back of the hall.

Why would you put balloon like that :|

The closing ceremony then started. As usual, it started with some speech. After that, it is followed by the announcement for the top three of ICPC Challenge. The prize is really nice btw. Following that is the announcement for the next ICPC WF. ICPC WF 2020 will be held in Moscow, hosted by MIPT. Russia is really the overlord of CP I guess.

After that, it was the announcement for the first solvers. The first to solve in the whole contest is University of Warsaw, solving E in just 14 minutes. There are 3 problems that were unsolved before the scoreboard was frozen, so there were 7 awards. After the first solvers session finished, time for the long awaited resolver time!

The resolver start with unusual UI. Ah, probably this is for the Honorable Mention. The MC is pretty strong, reading resolver must be tiring :P For this time, the Honorable Mention are those who solved <= 3 problems. There are a lot of HM, so the MC kinda having a hard time to catch up. Luckily the resolver can be paused :P

After the HM finished, time for the named rank, who solved >= 4 problems. Solving 4 problems get joint-62 rank and solving 5 problems get joint-41 rank. I'm really intrigued in what our final rank is. I hope at most it will be in twenties. As it turns out, our final raw rank is 23, officialy being joint-21 rank. This is current best result for UI :D

Solving 7 problems is not enough to get medal. Finally, we reached the top 12. I predicted that the lowest 8 solve will still get silver medal, and it's correct. Near the end, the resolver put MSU's K first instead of I, probably so that they won't be in the first place. Although, since there is no first solver for I, I guess they will solve I and win. And it's right, MSU win ICPC WF again with 10 solved problems!

The champion!
Source: ICPC Live

I looked at the final scoreboard, and it looks like we performed well among teams in Asia Pacific region. We placed 4th, the first team in the region to not get medal. We were also quite lucky to beat some strong teams like KAIST and NUS. The scoreboard currently can be accessed here, although probably it can't be seen next season. There is a mirror scoreboard with nice color and CF ratings here as well.

Our final result

ICPC WF medalist
Asia Pacific teams
After that there will be last dinner. Both me and Degol decided to skip the dinner, with my reason being too tired and don't want to eat that late. At the entrance we noticed that it is raining heavily and the bus is not ready yet :| A woman approached us, probably noticing that we are Indonesian because we talked in Bahasa. That woman is from Malaysia. Hmm, maybe next season there will be Malaysia regional? After a while, the bus arrived. However, after waiting on the bus for almost an hour, the bus still hasn't moved :| Degol said that maybe we can actually have dinner and still catch the bus. Finally the bus move, and we arrived at the hotel safely. I take a bath, do shalat, and prepare to sleep.

Yet I can't sleep until midnight. Somehow my wrists hurt, and I can't sleep no matter how hard I try.

Day 5 - Going Home

I wake up later than usual, and when I want to use the bathroom Degol is still using it. When he finally get out, he was bringing his Switch. Never see someone bring Switch to bathroom but okay :| After taking a bath, I packed all my stuff beside my laptop. Easy to throw almost everything, though in the end I have to reconfigure since my baggage is pretty full. After that, we have last breakfast in hotel, with the pancake machine empty. I realized that starting tomorrow I have to prepare my breakfast on my own again :(

After we went back to our room, Pak Denny and Inigo came and we distribute some stuffs to their respective owners. After a couple of minutes, me and Degol do final check on the room, before going to where the shuttle bus will be with Pak Denny and Inigo. It seems my flight, Degol and Inigo's flight, and Pak Denny and Bu Citra's flight are different. Me, Degol, and Inigo go to the airport, while Pak Denny will leave in the evening.

We check-in, and my gate and Degol and Inigo's gate should be near. At the duty free, I bought some souvenirs again. Then, while the number of our gate is close (33 and 34), the actual position is quite far :| We waited in my gate though, since gate 33 is full. Finally it's time for them to board their plane, while I have to wait for another hour for my flight. I noticed that there are someone who looks like misof (and he wear IOI T-shirt) and Petr boarding my plane as well. Btw, my flight got delayed for around half an hour, hopefully there won't be any trouble :|

The flight was pretty smooth, I can sleep easily. It's the first time I'm in Zurich, and I'm surprised that they used Franc here instead of Euro :O Oh well, I'll just go straight to my boarding gate then. My flight to Dresden is also delayed for around 30 minutes :| The flight itself is again pretty smooth, although I can't sleep anymore. Finally I reached Dresden, got my baggage, and hurriedly run into the train that will depart in around 3 minutes as I don't want to wait for another 30 minutes again.

Well, vacation is over. Time to focus on bachelor thesis :s


I'm glad that I could finish my ICPC career better than I expected. Also, I'm glad that UI's performance in ICPC keeps improving. I hope that CP UI can keep improving, and can manage to outrank the current best performance we have :) Not intending to give pressure, just think as me challenging you guys :)

I'm glad that I decided to compete in ICPC again seriously this year, even if it was because Pak Denny "forced" me. Looking back at my CP career since high school, sometimes I can't believe I managed to get to this point. From someone who liked to read blogposts from TOKI Alumnis about their contests and think there is no way I can be someone like that, now being the one who write the blogpost like that and compete in similar contests as well. Although I admit, my post quality are shittier xD

I faced several failures, like being beaten by the pressure in IOI 2015, and two times failing to solve problems that may result in my team advancing to WF in 2015 and 2017. There are some times where I even questioned why I am still doing CP. However, while there was failures, there was also joys, and I can't just dwell in my failures. In the end, looking at all that happened these past few years, I can proudly say that I'm glad to be here.

I want to thank all of the people I met in this journey, who directly or indirectly helped me and shaped me into who I am right now. In particular, amongst all people, I wanted to thank them the most, in no particular order:

  • My parents, for their endless support
  • Pak Denny, for coaching ICPC in the past 4 years, and helped me a lot during these times
  • Ammar, for helping me a lot in CP discussion, and being a very good friend of mine who sometimes compete together (our poor sense of humor is compatible I guess)
  • Irvin, for introducing me to national training camp "enslavement", which undeniably keep my skills not dull until today, also for giving me several advices and notes mostly about problemsetting
While this journey is a wonderful one, like every journey, it will come to an end. The blogpost after this will be the last blogpost on this blog, which I will write in a few days (or weeks, depending on how busy I am).

ICPC WF 2019 Porto, Part 2

Day 1 - Registration

I woke up around 4:00 because of Degol's alarm. Didn't bother to turn it off since I was too lazy. Around 5:30, it's still ringing, and finally Degol is awake. When it's time for breakfast, we decided to go. I borrowed Degol's slippers (he brought 2 pairs of slippers) since I can't find any hotel sandals in our room. The breakfast is good, although maybe the best part is I don't have to prepare breakfast on my own like usual xD Pak Denny said the pastel de nata (egg tart) is delicious, but I'm already full so I decided I'll try it tomorrow.

After that, we went to Alfândega where most of our activities will be held. We took a few photos before we enter the building. There are tech showcases (I'll just say it chillzone since there are games as well) and tech trek, with our team get the later session for the tech trek. There are showcases from sponsors like 2 Sigma, Huawei, JetBrains etc. On Huawei showcase there is P30 Pro which we talked the day before, mostly about jokes of its 50x zoom. On JetBrains showcase we got yoyo, though I can't do long sleeper like usual :-? Seems it need a bit fixing.

Can replace sniper rifle's scope
Degol struggled to fix it, while I finally decided to fix it after the yoyo fell apart. Accidentally I managed to fix it sooner than Degol. Pak Denny then told us he want to fly his drone, so all of us went outside. However, Pak Denny's phone battery ran out, so he can't fly the drone. Sad :( Anyway, after that we went for the tech trek. It was about Intro to Kotlin. The presenter is funny, so it was not so bad I think. Yet because I was rather sleepy, near the end I fell asleep :/

After tech trek, we still have some spare time before lunch. So we decided to take a walk around. Then we reached Palacio da Bolsa, and decided to join the tour inside scheduled around 12:30. While waiting for the tour, we take a walk around the park in front of it. Pak Denny and Inigo visited a wine shop. While waiting for Pak Denny and Inigo, me and Degol take a walk nearby, though we didn't see much.

Monument at the park
Palacio da Bolsa
Source: Pak Denny

After Pak Denny and Inigo finished, we went to Palacio da Bolsa. Bu Citra also joined us near the start. The tour inside was nice, the tour guide surely know her stuff and is very good at it. It was not boring, unlike most tour in Indonesia. The building itself was a trade market, and during the tour we learned some stuffs from Portuguese history. There are rooms which has arabic feels in it, with writings that have absolutely no meaning xD Btw, during the tour I kept getting confused with why the tour guide keep saying "Portugal swine", only to realize later she actually said "Portugal's wine" :(

Court room

Arabic room
After that, we went back to Alfândega to have lunch. The lunch was also very delicious. The dessert was also nice, and now I believe anything with orange ingredient in it is the best here xD After lunch, we waited for team registration. The registration is like 2 years ago; we were accompanied by a volunteer, there are several posts, where we have to do / submit something at each posts. When we submit items for contest, the staff was very excited when they saw the big Tayo doll. We submitted Tayo doll, TRD, pens, ruler, and keyboard sticker (context) . We also got some stuffs like bag and contest T-shirt, which is nice. At the very last post, we were explained about ICPC Quest. I was never interested in those kind of stuffs tbh. After that, we put our contest T-shirt for team photo. This year our T-shirt's color is blue with red font, I guess to symbolize Fasilkom's color.

Anyway after that we queued for the team photo. Before the actual team photo, we have to take a "warm-up" team photo. Then, we went for the actual team photo. They took 2 photos: The first one serious, the second one smiling. It seems there is no 5-second video like before where we have to do something, which is good for me. After that, we also took photo with the volunteer. Pak Denny also asked him about local food, which I don't really hear what they are talking. Pak Denny then said he recommended a restaurant near our hotel, where we can eat Francesinha. I checked the schedule, and it seems the only time where we can eat at restaurant is only today and the day before contest. To avoid any trouble, we decided to go to that restaurant today.

Source: ICPC Live

Source: Pak Denny

P.S: I actually wore the same shirt underneath the ICPC T-shirt with the shirt I wore 2 years ago in Rapid City. It was ICPC Singapore 2015 shirt, which is my favorite ICPC-related shirt up to this day.

We went back to the hotel, and then we went to the restaurant (it was Capa Negra if I'm not wrong). When we entered, there are still lots of empty seats. I ordered "Capa Negra Francesinha", because of what Firman said long time ago: "Kalo di namanya ada original atau nama restorannya, pasti itu yang paling enak, soalnya itu yang bikin mereka sekarang sukses". Pak Denny then told the waiter that mine and Degol's shouldn't use pork. Also, Pak Denny and Bu Citra ordered a duck dish that will be shared with all of us. Then, our food come, it seems for me and Degol our Francesinha's pork layer get replaced by another cheese layer. In a nutshell, for me Francesinha is like pizza, but shaped and called like sandwich. And my God, IT IS SOOO GOOOOOD. Seems like the restaurant is really famous, when we finished eating the restaurant is full!


The inside

We went back to hotel to rest. Inigo came to my and Degol's room. I played Switch until around 10:30, while Degol sleep early because he want to do his assignments. I'm not sure he will really do it or not, but I don't really care. After I finished playing, I go to sleep.

Day 2 - Excursion, ICPC Challenge & Opening Ceremony

I woke up as usual, and find Degol is already awake, seems he actually did his assignments. During breakfast, I tried the pancake machine, this is the first time I see such machine. The pancake produced is not bad. Also I tried Pastel de Nata, tasty but not as superb as the orange pie from dinner some days ago.

We went to the excursion. There are several routes, but it seemed that the route is gacha-ed. We got the B trip, which sadly pass some places we visited before :( Not so much to say here, we went through lots of alley, and when we pass one of them the guide say that alley was a place mentioned in a book. Anyway, after the excursion we went back to Alfândega. There is empty arcade, so me and Degol played some games. We played a touhou-like game, street fighter (until we find a character that either too broken, or we are too stupid to find a way to counter it), and finally we played bomberman. Really, I sucked at bomberman. We played around 1 hour before we are tired. After some minutes, we went to have lunch. They have orange-based dessert, nice.

Not sure what the heck is this..

"Bow before me, you filthy humans" - bird

Post-lunch, we went to the east wing of Alfândega for ICPC Challenge. We used Degol's laptop for this event. It's funny that while the team sitting across us have laptop with geeky stickers, the laptop we used have weeb stickers. The ICPC Challenge itself has 2 problems, both about deciding weights for neurons in the given Neural Network. I don't really understand about NN for classifying, and it seems Degol also don't really understand. Inigo is still in 1st year, so I didn't expect him to know about NN. Anyway, we just throw some random shit, and ended in around 60th place xD

Source: ICPC Live
After that we went to Casa da Musica for the opening ceremony. We took a little walk to Rotunda which is nearby. It is purely coincidence that there is another place in UI with the same name. After that, we returned to Casa da Musica for the opening ceremony. The opening was quite standard I guess, not much to talk. The performance from locals are good, some movements are scary though. Also, I don't really get why during the performance there is a guy in the corner who carried some flags. All performance has that flag guy, who only stand there doing nothing :/ Also, it was funny that there is a child who yelled "Yaaaay" very loudly during some unexpected time, making the audience laugh. During team intro of North America, there was a technical trouble near the end, and then they repeat the team intro for that region.

Porto's Rotunda
After the ceremony is over we have dinner. There is a beef dish, but has red wine so I can't eat it :s There are some delicious dishes too though, so it's okay. Eating another orange-based dessert, now I'm sure that orange-based desserts here are the best. After dinner, all of us except Inigo go to a supermarket to search some foods that can be used as souvenir. I bought some chocolates and snacks to eat at the hotel. Then, we went back to the hotel, where I played until I was really sleepy, and decided to sleep.

Day 3 - Dress Rehearsal

Wake up and have breakfast as usual. However, for no reason I feel sleepy after breakfast, so I took a little nap. After that, we went to Alfândega for dress rehearsal. Basically it is practice session. There was quite some time before team check-in, so I read light novel for a while. After that, we queued for check-in. Inigo's digital watch was prohibited, so he took it off and put it in his bag, then return to the queue again.

After check-in, we waited at the west hall of Alfândega before dress rehearsal. Bill Poucher went around the room, bringing the ICPC WF trophy, inviting anyone who want to take photo with it and touch the trophy. I am not really interested in that stuff, only thinking how much oil that trophy has from thousands who touched it :/ (yeah I know I am pretty weird). Maybe bored or what, but there were a lot of table slamming, with some rhythm in it. I don't really like it to be honest, baka baka shi.

Finally it's time for dress rehearsal. We walked from the west wing of Alfândega into the contest floor. Our workstation is near the entrance, yet we have to take a bit of detour to go to it. In the screen on the wall of contest floor, there is John Clevenger's GIF which says "Do not touch anything", a sentence that is like mantra before any official competition. Of course, beside the GIF, he also keep saying it via mic, and there is a paper with that sentence in each workstation. Our submitted items are also there in the workstation, inside a bag. Behind our workstation is Waseda's, and I don't really remember whose workstation is beside or in front of us. From our workstation we can see NUS's workstation. The spectator's area is rather small, no way it can fit all the coaches :/ Probably there will be remote spectating area in chillzone, since if I remembered correctly there were several monitors there.

Spot where UI is!
Source: Pak Denny

The dress rehearsal then begin. I took the computer first to configure it. After I changed the key mapping, we spend a few minutes putting the keyboard stickers according to US mapping. After that, I asked Degol and Inigo what editor they usually use. They said Geany, so I opened Geany. Personally I don't really care about the editor, as for pre-WF training I usually code in Gedit :P Anyway, it seems there is no dark theme, and configuring it was quite a hassle. After that, I tried coding the easiest problem, an interactive binary search. I made a stupid bug and got WA Dx I fixed it and then it got AC. Degol tried coding for the same problem, just in order to get used to the computer. We also tried the printing. Oh, one of the best part in WF is that you can print and submit via terminal, reducing the time needed to do those stuff. We have to check the browser though if we want to see the verdicts and the standings. Also, team login in browser can be done automatically without entering username and password, pretty neat.

I was confused as I don't see any printed problems, but I think since it's dress rehearsal they don't print the problems. After Degol finished coding and got AC, Inigo tried coding another interactive problem. At this point, it was announced that for tomorrow there won't be any interactive problem :| Biggest plot twist in WF. Not to mention they also prepared the testing program for interactive in workstations so we can do local testing easily, such a waste :| When Inigo was coding, I pointed out some stuff that can be written better, to simplify coding. After that, we got AC in that problem as well. There was a MCMF problem, and I was curious how fast I can code max flow in new environment, so I tried it. While I was coding and struggling with bugs, Degol noticed an unopened envelope, which contain the printed problem and login credentials. We feel so stupid for not noticing it until the last hour. Anyway, I finished the MCMF and got AC after 1 WA. I found it annoying that Geany can't toggle comment with one shortcut, at least we can't figure out how. Out of boredom, I checked CLion. It was created by JetBrains, so it should be pretty similar with IntelliJ.

It has dark theme.
Can toggle comments.
OK let's use this IDE we never used before for tomorrow's contest!

Yes this is serious. Since we do most compile and testing in terminal, and never rely on some feature of IDE, there is no trouble switching editor right now. Anyway, at this point Pak Denny visited our workstation, asking whether we have trouble or not. Well, technically we don't have any trouble. Degol and Inigo then coded a problem from last year WF, while I was eating lunch provided in the workstation. Seems for the organizer halal = vegetarian, though it simplify lots of stuff. Near the end of the dress rehearsal, Degol submitted his code, and got AC.

Source: Pak Denny

Source: Pak Denny

After the dress rehearsal is over, it is time for coach award ceremony, held in the contest floor as well. Coach who bring teams for the X times where X is multiple of 5 is awarded here. A reminder that UI needs 1 more team in WF so that Pak Denny can get this reward as well :P It seems Steven Halim also needs 1 more to get this award.

After dress rehearsal, we went back to the chillzone, and waited a few minutes until clarification answering session. There are some clarifications, but I guess the most important are these two:

  • Can we map the upper part of enter into backslash? (while funny, this is pretty good one)
  • Can we see our submission code in DOMJudge? (important, but I already know that this is a no)

Looks like there is no troll question like in 2017, I remember there was a question about bogosort.

After the session ended, both me and Pak Denny check the schedule. Seems that the remaining ICPC sessions can be skipped. So, we decided to look for souvenirs instead. I bought some stuff for my family, since in a few week my dad will come to visit me. After we finished buying souvenirs, we went back to the hotel. Along the way, we saw vehicles that looks like bajaj, if I'm not wrong it's called Tuk-Tuk (but most likely I was wrong on this one as well). We also came across a church that also seems to be a tourist spot. Pak Denny and Inigo go to the church for a while, while me and Degol took a look around. After Pak Denny and Inigo finished, we walk around half an hour to the hotel. The wind is rather brutal at that time.

Me and Degol then played tournament in Smash Bros Ultimate, and after that all of us went to have dinner in Porto Palacio. Since I was lazy, I used Degol's slipper to go there. I totally forgot about the wind. Degol forgot about it as well. So.. our trip to Porto Palacio was really cold in our feet. After dinner which is quite good as usual, the trip back is cold as well. Inigo and Degol went for the supermarket, while I went straight back to the hotel. Pak Denny and Bu Citra took the shortcut into the hotel, and arrived faster than me :| While I was taking a bath, I didn't hear Degol knocking the door. And I didn't check my phone after bath. So.. Degol is being a refugee in Inigo's room for around half an hour.

Around 21:30 I decided to sleep, yet stupidly open Youtube before sleeping. I noticed that the second cour of "Rising of the Best Raccoon Girl" has started, and the new opening is already up in Youtube!

Guess who postponed sleep for about 1 hour, the day before the contest proper.

ICPC WF 2019 Porto, Part 1

Unlike my usual blogpost, I'll try to write this one in English. Since this WF is my last ICPC contest (2nd time at WF), I just want to write this story not in usual way :P

Before WF

You can skip this one if you want to, this one is not about the 6+1 days in WF :P

My team, Supir Tayo which consist of me (ayaze), Degol (DigiM), and Inigo (IgoRamli) qualified to WF 2019 by winning Hanoi regional 2018. Unlike previous seasons where we usually wait for announcement in CJ Hwang's blog whether UI will qualify to WF or not, this time we are 100% sure that we will qualify to WF because we won in a regional (1st time for UI to win a regional). Hence, we can plan our training in advance. Also, I believe that getting visa for Portugal should be easier than US, hopefully Inigo and Degol can get it with no trouble (I'm still traumatized with my attempts to get US visa).

Anyway, I think I'll just write how this team was formed. Basically, I was just exercising my power to pick my teammate for this season as coach assistant (this sentence seems so wrong). For picking my teammate, I have 2 main criteria:

  • We should be able to get along easily. I hate it when I have to argue over stupid things a lot with my teammate (happened before)
  • They should be able to cover stuff I am weak at or hate (such as geometry, lol)
If I remembered correctly this team was formed second, with the first was JatengPride since they have great performance during CompFest X final. I picked Degol and Inigo, because:

  • I know Degol quite well, since we have worked together for some stuff. At least I know we won't have trouble cooperating with each other. He is also good at greedy (which I am rather weak at) and can do geometry (which I truly hate). He can also code tedious stuff, although it quite some time
  • I kinda know Inigo a bit since OSN and Pelatnas. Although he was disqualified from the 1st stage of national training camp for some reason (it's very stupid reason in my opinion, which also why I rather don't want to take part in training camp again if possible), I belief he has a lot of potential, which is bad if wasted. So I took him in, planning to have him trained a bit under me. Beside, having a "random variable" in team like this seems interesting. He also seems nice and humble, so at least we won't argue a lot. Though lately it seems he became more rude at me, maybe just because we are getting friendlier :P
Before regionals, We usually trained weekly in Ristek using CF gyms. Unlike previous year, I decided to add "contest review" post-contest, where we talked a bit about our performance in that contest, what went wrong, what went good, how to prevent those wrongs etc. I think it's better to reflect on those stuff to learn better about ourselves and to improve. Anyway, we managed to get a good rank in Jakarta (5th place) and scored a win in Hanoi (champion), which is a very good feat I think.

Now comes trouble for training pre-WF:

  • I'm having research internship at TU Dresden, Germany for this semester. We won't be able to train at the same place
  • Degol almost have an exchange in uni in Singapore or Tokyo, although this was cancelled. He's in 6th semester though; I figured it will be hard for him to train
Anyway, we decided to do weekly training every sunday at 12:00 or 13:00 GMT+7 (6:00 or 07:00 at Dresden). For communication we primarily used LINE chat, to write observations or letting the other side know that we are currently coding. Didn't use video call since my internet is rather shitty. The training itself is like usual, I think now we're used to it. Maybe I'll just tell my biggest dilemma for training at that time:

  • If I have breakfast (suppose I have time to prepare), I'll be too sleepy to think
  • If I don't have breakfast, around the 3rd of 4th hour I'll be too hungry to think
In the end, usually I don't have breakfast, and around the 4th hour I'll just prepare simple food to eat while Degol or Inigo are solving problems.

Beside team training, we also prepared our Team Reference Document (TRD). Our usual TRD which was based on Sukar Ditaklukkan's TRD was written in docs. Since I found a good TRD generator from C++ and LaTeX, I decided to make a repo to make our TRD instead. Though since all of us are rather busy, not much was added to the TRD. Our TRD can be accessed here, use at your own risk.

Now this is my personal issue. Personally, I always believed that I am weaker than myself from few years ago. Also, I think in terms of knowledge, the youngsters right now know a lot more than me. For example I don't understand exotic DP such as Slope trick, Aliens trick, or some other algorithms. Yet, I am not really interested to learn those stuff (this is not good actually). Anyway, I decided that if I don't understand those stuffs, I'll fight by polishing whatever I have to its finest.

For closing of this part, my goal in this WF is quite simple: to have fun, perform better than in my last WF in 2017 (raw rank 45th, official joint-34th), and to not have any regrets. I hope I won't be stuck at one problem again like last time :s

Now here goes the real part of adventure in WF!

Day -1 - Before Departure

Spent the entire day doing stuffs so I can relax when I'm back from Porto, i.e doing laundry, grocery, etc. Degol forgot to reply whether he will bring the Tayo doll or not, so I think I'll bring the red panda doll I bought last week in Leipzig zoo, for mascot in case he didn't bring Tayo doll. Why red panda? Probably because of the influence of "Rising of the Raccoon Best Girl", but now I think red panda, raccoon or similar animals are cute. Anyway, packing was rather quick, simply throwing everything I want to bring for the next few days. Didn't bring any thick jackets, since last time I checked Porto's temperature is at least 2 digits (10 celcius is still OK, but 9 is nope for me). Luckily I still have some space in case I want to buy several souvenirs.

My red panda doll

Around 16:00 here, I think Pak Denny, Degol, and Inigo already board their plane. Probably their departure time is similiar with mine several months ago. Oh well, finally gonna meet them in Frankfurt tomorrow. At least for the first time in several months I have to wake up early in sunday morning not for team training, yay.

Gotta sleep soon, yet my body rhythm just won't let me ~_~ Hopefully I can wake up in time tomorrow to catch up the train to the airport.

Day 0 - Departure

Woke up in time to catch the train to the airport. Still so early in the morning, not many people there both in the train and the airport. It's funny that while there is only 1 person in the baggage check (me), there are around 10 airport employee standing at the baggage check xD Anyway, I didn't know that Dresden airport is quite big (around 12 gates), when I arrived several months ago I thought that the airport is small. Still 2 hours before boarding, so I kill some time by reading light novel and watching Youtube. Around the time I was going to board the plane, it seems the rest of the team already arrived at Frankfurt. And Degol said he brought the Tayo doll, don't know whether my red panda doll will be a waste or not.

After arriving at Frankfurt, I met up with them at the gaming station. Before I forgot, there are 5 participant from UI, they are Pak Denny as coach, Me, Degol, Inigo as contestant, and Bu Citra (Pak Denny's wife) as guest. After that, we decided to get something to eat, with Pak Denny very eager to eat sausage (the conversation back then, when taken out of context, is very weird). However, first we bought breads from bakery, since the halal-ness of sausage here is.. yeah. When we were eating, suddenly we came across NUS team (Steven Halim & Suhendry). After that, since Pak Denny still wanted to eat sausage, we split up, and I was left with Degol, chatting about stuff at Fasilkom and some anime/manga stuff.

After a series of time killing attempt, finally it's time to board the plane. It's taking quite some time until we can board the plane. My seat was located far from all of them (well, I don't know their seat and I just picked random seat in the morning). When I checked the ticket, it seems that the flight is around 1.5 hours (13:45 - 15:25). Fast enough. Right after I sat on my seat, I immediately tried to sleep. Then, I remembered.

Isn't Frankfurt-Porto is at least as long as Balikpapan-Jakarta?
Isn't Porto's timezone different with Frankfurt?
Then I realized that the flight is actually 2.5 hours. I feel betrayed.

After arriving in Porto, we took our luggage into ICPC volunteer place. After Pak Denny take care of several stuff, we took photo with the ICPC banner. Then, Pak Denny and Inigo went to buy SIM card to use in Porto. Oh, btw it's the first time I can use mobile data in foreign ICPC, and it's only because Vodafone can be used here as well xD Usually I never bother about mobile data in ICPC.

Ready for WF!
Source: Pak Denny

While waiting for the shuttle bus, we checked places that we can see today. I'm not really sure about where to visit, so after a while, only Inigo, Pak Denny, and Bu Citra who checked places around Porto. The bus finally arrived. Along the road, Inigo said that he saw something that may surprise me. When I asked what, he said night club. Considering that in front of Dresden hbf there are night club and inside hbf there are betting place.. I am not really surprised with that stuff anymore :P Well, the sad part of growing up is you become less and less surprised with something.

There are some hotels reserved for ICPC contestants, I think there are > 5 hotels. Our hotel is HF Tuela Porto. I shared room with Degol, Pak Denny with Bu Citra, while Inigo is alone. Another sad thing is while my room is beside Pak Denny's room, Inigo's room is in different floor. The room is nice; at least there is big TV so I can play Switch in big screen :P After putting our luggage and setting up gaming station, we went to hotel Porto Palacio to get dinner.

The dinner is good, at least I liked the fish and the dessert. At first glance, the orange pie looks like kue lapis or bolu in Indonesia. But damn, this stuff is REALLY GOOD. The cheesecake is also good, though everyone else but me agreed that cheesecake in Frankfurt is better. Also, it seems that sparkling water is called "water with gas" here, which is quite funny when we think about it.

View near the bridge

After that, we decided to take a walk around. We go near a bridge-which-i-dont-know-what-its-name-is, taking shortcut here and there . After that we walked near the river until we reach the rail museum. The trip back to the hotel was rather tiring; I don't remember we go down that much, but the trip back was like 90% uphill, and yeah it was tiring. After we got to the hotel, I spent around 30 mins - 1 hour playing Switch, until I finally decided to sleep.

Senin, 31 Desember 2018

Definitely Not a 2018 Post

Tentunya, ini blog post tentang 2018, lol.

2018 akan segera berakhir dan aku bakal ngelewatin tahun baru di pesawat. In fact, bentar lagi boarding. Aku mungkin bakal nulis beberapa hal penting di tahun ini, sama hal-hal yang lumayan aku ingat.

Ketua Ristek SIG CP

Aku daftar jadi ketua Ristek SIG CP. Kalo ditanya, motivasi kerennya supaya bisa ngajarin yang pengen belajar CP. Motivasi sebenernya sih, pengen mempertahankan tempat tinggal di Fasilkom (ruang Ristek), haha. Though yeah, aku lumayan seneng-seneng aja jadi ketua SIG CP. Punya junior member yang lumayan semangat, HRD yang bully-able, sama senior member yang pada kurang ajar. Semoga semua bisa mendapatkan sesuatu selama setahun di SIG CP, haha. 

Ikut 2 Lomba di Hari yang Sama

Nggak sengaja lolos CTF sama CP di Arkavidia, lol. CP-nya Alhamdulillah bisa rank 1, CTF-nya get rekt. Pas join ke CTF kondisiku udah puyeng sama lapar banget juga sih. Maafkan aku Fahmi sama Ricky yang kutinggal beberapa jam di awal :")


Matkul yang paling bakal diinget kayaknya, karena capeknya nggak ketulungan. Di matkul ini udah capek banget, bisa liat sifat-sifat buruk manusia juga. Kayaknya matkul ini yang lumayan bikin kacau jadwal hidupku di semester 6; Biasa ngoding buat PPL sampe jam 2 pagi, bangun jam 6 pagi buat kuliah, terus jam 2 siang sampe sore biasa tidur di Ristek karena ngantuk banget (skip beberapa matkul), dan ulangi lagi :s Kayaknya sampe sekarang saranku buat yang masih tahun kedua di Fasilkom, sebisa mungkin nyodok matkul semester 6 yang bisa disodok, karena semester 6 itu rasanya semester terlaknat di Fasilkom, paling challenging. Oiya, thanks buat teman-teman sekelompok yang membantu, maaf saya sering emosian hehe.


Oke ini udah tahun ketiga jadi SC OSN. Aslinya kayak SC lomba biasa, cuma lebih bergengsi (padahal cuma pernah SC OSN sama CompFest). Rasanya biasa aja sih :-? Hal-hal yang lumayan kuinget dari nge-SC OSN:

  • Menghabiskan malam minggu untuk nyari TC yang bikin solusiku atau solusi Rais salah. Jam 3 pagi akhirnya ketemu TC kecil yang bikin solusi Rais salah. Kembalikan waktu weekend-ku!
  • Submit soal dan keterima di OSN. Btw, soal yang kusubmit aslinya udah dibuat dari 2017, backup soal CompFest '_' Aku submit karena Ammar bilang soal yang masuk masih dikit banget. Di pagi itu juga aku ubek-ubek soal, nemu soal ini, terus bikin subtasknya dalam sekitar 30 menit. Entah kenapa SC-SC yang lain pada setuju soal ini dimasukin, dan cuma aku yang nggak minat masukin ini soal '_' Btw, nama soal aslinya K-FPB, di OSN jadi Festival FPB
  • Ngeracunin SC OSN yang lain buat nonton YowaPeda. Aku sendiri belom pernah nonton sebelumnya, cuma gak sengaja ketemu video ini di Youtube. Jadinya malah nonton YowaPeda
  • Dari semua SC OSN, yang laptopnya bisa dicolok kabel LAN cuma punyaku. Kayaknya ini alasan aku dibawa ke OSN, biar laptopnya bisa dicolok LAN terus bagi-bagi internet. Sense penamaan wifi masih kebawa YowaPeda, Andy -> Frank -> Fabian.
  • Oke yang ini bego. Jadi aku selama ini mengidentikkan kata "padang" dengan "padang pasir", dan ternyata... kota Padang lumayan hijau dan deket laut.

Nggak nge-SC Pelatnas

Lumayan representatif lah ya gambarnya. Setelah 2.5 tahun berkutat di Pelatnas, tahun ini aku nggak ikut ngurus. Ada alasannya, cuma mungkin bisa didekusi dari post ini, lol. Walaupun gitu, kadang masih diskusi-diskusi sama Ammar terkait TOKI-TOKIan, terutama yang terkait Pelatnas sama OSN. Kayaknya walaupun udah nggak nge-SC Pelatnas, masih bakal terlibat juga, albeit indirectly.

ICPC Provincial

Bagian proker dari SIG CP Ristek, ikut-ikut ICPC Provincial. Tahun ini kami ikut Vocomfest sama Maranatha. Selain itu, aku juga ikut CPC CompFest, cuma junmem sama senmem-ku pada gak bisa ikut karena jadi panitia CompFest. Awalnya, aku nggak terlalu kepengen ikut, pengennya jadi coach aja. Cuma karena ada rumor duit dari fakultas bisa susah turun kalo nggak ada yang menang.. jadinya aku harus berusaha supaya menang. Oiya, kalo ada yang nanya "kenapa nama timnya rania semua?" Karena itu nama HRD kami yang bully-able. Tapi gitu-gitu, tim yang kedaftar dengan Rania jadi coachnya menang ICPC Provincial lho (VocomFest, Maranatha, CPC CompFest). World class coach emang.

Btw, aku sendiri ngerasa timku menang di ICPC Provincial ini lumayan karena hoki :")
  • Di Vocomfest hoki di penalty
  • Di Maranatha, Anab salah ngerti soal J (kalo gak salah, yang intendednya aneh pokoknya), terus Firman nekat submit aja padahal format output gak jelas. Ini malah first solve. Terus aku salah ngitung, kukira KPK 16 sama 24 itu 24 (harusnya 48), tapi malah tetep AC '_'

Asisten Coach

Awalnya merencanakan untuk nggak ikut ICPC tahun ini, terus bilang ke Pak Denny kalo bisa bantu-bantu terkait seleksi sama latihan. Jadinya ya, aku nyiapin soal-soal seleksi, terus diskusi juga sama Pak Denny terkait pembagian timnya. Cukup lucu juga karena di course SCELE aku kedaftar jadi dosen '_' Selain asisten coach ICPC, aku juga nyiapin soal-soal latihan buat tim yang lolos Gemastik. 

Note: Dan tak disangka, dapat duit dari jadi asisten coach '_' Tapi tak apa siapa yang gak suka $$


Awalnya merencanakan untuk gak ikut ICPC tahun ini, tapi tetep "dipaksa" (perhatikan ini pakai tanda kutip) Pak Denny buat tetep ikut. Jadinya aku tetep ikut. Aku sendiri milih setim sama Degol + Inigo, memanfaatkan kekuasaan dari jadi asisten coach. Pantes orang senang berkuasa -- punya kekuasaan enak (jk). Kami dapat rank 5 di Jakarta (yey first time I got a silver medal!) dan menang di Hanoi (rather unexpected tbh). Jadinya ya, Insya Allah kami bakal ke Porto tahun depan buat WF 2019. Though, bakal susah latihannya, secara aku semester depan nggak di Indo :/ Moga aja masih bisa memberikan yang terbaik di WF deh.

Achievement unlocked: dipajang di depan Stasiun UI
tapi malu sih..

Note: lolos final Gemastik bisa lebih susah dari lolos ke WF


Di awal tahun, aku mikir "coba liat tahun ini bisa sejauh apa di Kattis deh". Awalnya karena seneng aja ngerjain soal tapi gak ikut kontes. Selain itu, mungkin bisa ngebantu buat nyiapin matkul TKTPL (kalo semester genap biasa jadi matkul CP). Cuma ya karena emang niatnya supaya ini gak terlalu serius, aku cuma ngerjain pas waktu senggang dan kepengen aja. Sampai akhir tahun ini, udah deket sama top 100, cuma aku males ngerjain lagi :P


Selain itu ada beberapa hal lain yang lumayan kuinget, kayak Pelatnas, Qlapa sama persiapan skripsi. Cuma entah kenapa males nulis, lol. Selain itu, ada juga beberapa hal lain yang lumayan depressing, kayak sesuatu yang terjadi deket akhir tahun, yang Alhamdulillah berakhir dengan baik.

Antara karena 2017 lumayan kacau, atau mungkin emang tahun ini lumayan lancar, jadinya 2018 terkesan berlalu dengan lumayan baik? In any case, banyak hal yang patut disyukuri di tahun ini :) Semoga saja yang baik++ dan yang nggak baik-- untuk tahun-tahun selanjutnya.

Aku bukan tipikal orang yang bikin resolusi buat 1 tahun sih. Kalopun ada, yang jelas nggak terkait CP. Mungkin sesuatu yang lebih berguna macam menjadi kurus supaya bisa cosplay kamen rider.

Kamis, 13 Desember 2018

ICPC Regional Singapore 2018

Nggak, aku nggak ke Singapore.

Tadi aku ikutan mirror ICPC Singapore 2018. Nah, kemarin aku gak yakin bisa ikutan apa nggak, soalnya ada yang harus kupelajari terkait TA. Terus Degol sama Inigo ada kuliah. Tapi ya, daftar-daftar aja dulu di Kattis. Oh, bisa bikin nama tim. Aku bikin nama tim cuma biar gak keliatan ikutan aja. Awalnya mau bikin "Your Lonely Tayo Driver" (pun intended) atau "Ching chong Does Not Dream of Bunny Boy Classmate" (entahlah lagi keinget Sakurajima Mail). Tapi, kalo misalnya ada kemungkinan nanti aku ikutan kontes dengan low effort, buat apa aku put effort untuk bikin nama tim. Aku liat layar, oh placeholder kalo gak ada nama timnya itu "(no name)". Aku copas, jadiin nama tim deh.

Post ini bakal bahas soal-soal yang kukerjain pas mirror, sama yang udah ku-upsolve tadi pas maghrib. Soal dibahas sesuai urutan aku ngerjain. Scoreboard mirror bisa dilihat di sini, dan solusi-solusiku bisa dilihat di sini.

Oiya, aku rada late start karena harus presentasi dan tadi dosennya agak molor datangnya :< Iya, aku selama 2 jam pertama ngerjain di kelas, setelah aku presentasi. Terus antara ngerjain A sama D aku gak ngerjain karena lagi belajar terkait TA (gak fokus sih) sama brunch.

B - Hoppers (menit ke-26)

Karena loncatnya 2, artinya semua bakal kekunjungi iff grafnya  bukan bipartite. Itung ada berapa connected component, sama cek di antara connected component itu ada yang nggak bipartite apa nggak. Bisa pake DFS/BFS biasa. Kalo ada yang bukan bipartite, jawabannya banyak_component-1. Kalo nggak ada, banyak_component. O(N + M).

L - Non-Prime Factors (menit ke-28)

Modifikasi sieve, sama loop harmonic aja. Precompute semua jawabannya dalam O(MX log MX) (MX = 2 juta), terus jawab tiap pertanyaan dalam O(1). Jadinya O(Q + MX log MX).

J - Free Food (menit ke-30)

Aslinya karena kecil bisa main loop brute force aja, cuma aku tadi pake prefix sum soalnya ngodingnya gampang juga. O(N + 365) = O(N).

C - SG Coin (menit ke-48)

Hmm, ada cerita blockchain segala. Tapi intinya sih, daripada nyari transaction string, gampangan nyari token, secara dia cuma ditambahin di akhir. Aku selalu set transaction string = "a", terus brute force mau hasil hash-nya berapa, yang merupakan kelipatan 107. Kalo token yang dibutuhin nilainya gak di luar batas, yaudah langsung ambil aja. O(1). Btw, aku salah set nilai maksimum tokennya jadi 107 di solusiku :)) tapi ya tetep nemu solusi sih.

F - Wi Know (menit ke-79)

Misal prev[d] menyatakan indeks terbesar sehingga elemen ke-d dan elemen ke-prev[d] sama. Misal 4 indeks yang mau kita ambil berturut-turut a, b, c, d. Misal kita fix-kan nilai c. Maka, a pasti paling enak pake elemen pertama yang nilainya sama dengan c. Terus, ini bakal ekivalen dengan nyari indeks d, sehingga prev[d] > a, yang nantinya dijadiin b.

Aku pake segment tree yang rada aneh rasanya. Segment tree-nya untuk nyari dari suatu range [1, x], nilai prev yang mana nilai elemennya (A[prev[]]) itu = i, untuk 1 <= i <= x. Ada mainan update berdasarkan prev, terus nyari x minimum, sehingga nilai query(1, x) itu > a. Maaf aku agak gak jelas jelasinnya, rada njelimet emang solusiku :<

Awalnya aku ngoding O(N log2 N) (binary search + query segtree), tapi TLE. Jadinya aku modifikasi jadi O(N log N), ilangin binary searchnya. Baru deh AC.

Btw, submission pertamaku buat soal ini gak sengaja masuk ke Kattis lomba aslinya :')) Untuk keadilan bersama, aku submit juga ke mirror-nya supaya dapet penalty :'))

A - Largest Triangle (menit ke-138)

Kayaknya cukup langka aku mau ngerjain geometri, dan itupun cuma karena gatel kenapa ini soal pada AC :<

Aku awalnya ngerjain urut dari titik terkiri bawah. Sort berdasarkan polar angle, terus cobain untuk tiap titik lain, pasangin ke titik sekarang sebagai alas segitiga. Tinggi segitiga harusnya bisa di-ternary search, seandainya kita ngerjainnya urut. Setelah selesai, hapus titik terkiri bawah. Cuma ya.. O(N2 log N), dan TLE :<

Habis itu aku ngide, coba daripada ternary search, dibikin macam two-pointer. Gak ngeprove kebenarannya. Disubmit, WA. Habis itu ngide lagi, jawaban harusnya ada di convex hull. Terus two-pointer lagi. Duh, WA. Pas aku bikin tes sembarang, entah kenapa ada keluar digit di belakang komanya 1, padahal harusnya 0 atau 5 (karena titiknya bilangan bulat semua). Lho, lupa dikali 5. Habis dibenerin, submit, AC. Wut. Jadinya O(N2).

Btw, pas aku mulai ngerjain ini aku masih di kelas. Terus aku gerakin tanganku buat ngebayangin alas sama tinggi segitiga. Tapi pas ngelakuin aku jadi kepikiran, itu gerakannya kayak Ultraman.

Pada titik ini, aku belajar terkait TA sama memutuskuan buat brunch, karena udah lapar banget. Habis makan aslinya udah niatin gak lanjutin. Hanya saja, iseng kepikiran sesuatu yang bego di D terus mau nyobain.

D - Bitwise (menit ke-221)

Soal macem ginian pasti hampir selalu iterasi dari bit terbesar ke terkecil, lalu cek bisa gak solusi terbaiknya masukin bit itu. Untuk ngecek apakah X bisa dibentuk di K subarray, aku pake kayak DP tapi lebih kayak greedy. Untuk kemudahan, misal or(l, r) menyatakan bitwise OR dari elemen ke-l sampai ke-r, dan dp(i) adalah pair<int, int> yang mana:

  • dp(i) = {0, or(1, i)} apabila X bukan submask dari or(1, i)
  • Selain itu, pasti ada l sehingga X submask dari or(l, i). Cari l maksimum, terus dp(i) = {1 + dp(l-1).first, dp(l-1).second)}
Mudahnya, dp(i) menyatakan {banyak subarray max, sisa or}. Selanjutnya, brute force i, sehingga dari i+1..n akan digabung dengan sisa or. Kita bisa itung banyak subarray partisi yang mana X adalah submasknya dengan mudah dalam O(N). X valid kalo banyak subarray partisi >= K.

Nah, masalahnya untuk nyobain bit-nya ada O(log 109) bit. Terus, pas kontes aku nggak kepikiran cara sliding window or selain pake prefix sum per bit. Jadinya, solusi ini kompleksitasnya O(N log2 109). Aku coba kasus sembarang di laptopku, 4 detikan. Liat TL Kattis, hmm 3 detik. Aku coba submit aja. To my surprise (and annoyance), dapet AC dalam 2.2 detik. Setelah kelai sama TL F sama A, tau-tau di sini malah lebih ringan :s Habis chat sama Ammar pasca kontes, katanya emang N diturunin jadi 500.000 di kontesnya. Oh, pantes kepangkas separo.

Anw, tadi kepikiran cara mangkas O(log 109) dari prefix sum. Intinya ganti ke sparse table sih, soalnya kita bisa precompute untuk tiap length, berapa 2 pangkat terbesar yang <= length. Jadinya sekarang ngecek or(l, r) bisa dalam O(1). Silahkan cek D2.cpp kalo masih penasaran.

I - Prolonged Password (menit ke-251)

Phew, untung yang bikin soal baik, panjang string transformasinya di rentang [2, 50]. Untuk soal ini, aku bagi 2 kasus, yang K <= 100 sama K > 100.

Pertama, misal dp(k, char) itu menyatakan panjang string kalo kita transformasi char sebanyak k kali. Ini bisa dalam O(k * |T|) doang. Untuk kemudahan, batasi dp(k, char) dengan nilai yang > 1015. Misal kita pengen nyari karakter ke-x dari string hasil transformasi char sebanyak k kali. Kita bisa iterasi sebanyak O(|T|), ngecekin karakter ke-x itu munculnya sebenarnya hasil transformasi karakter mana dari Tchar dengan memanfaatkan dp tadi. Jadinya, karakter ke-x juga bisa dicari dalam O(k * |T|).

Nah, kenapa tadi aku bagi kasus? Intinya sih:

  • Kalo K <= 100 (bukan tight bound), kita harus cek dia itu awalnya transfomasi dari karakter mana di S. Nah, masalahnya |S| <= 106. Kalo kita loop aja, bisa O(|S|) per query, TLE dong. Jadinya.. bikin prefix sum, terus binary search karakternya pake prefix sum. Lanjutnya pake solusi di atas.
  • Kalo K > 100, pasti sebenernya itu hasil transformasi dari karakter pertama terus-menerus sampai K = 100 (kasarannya, 2100 > 1015), jadi untuk K > 100 pasti karakter ke-x ada dari transformasi karakter pertama secara terus-meneurs. Aku pake semacam sparse table untuk nyari setelah berubah K-100 kali, karakter pertamanya itu jadi apa. Lanjutnya bisa pake solusi di atas.
Keseluruhannya, per query butuh O(100 * |T|), jadi totalnya O(M * 100 * |T|).

Btw, pas ngerjain ini awalnya aku kira K itu dikasih per query juga (jadi beda-beda), terus stres karena prefix sumnya bakal jebol :')

K - Conveyor Belt (menit ke-276)

Aku gak ngerjain soal ini sampe di akhir karena males baca ceritanya (yea, i'm a simple man). Habis baca singkat, intinya ini bisa dimodelin jadi network flow. Untuk kemudahan, ubah semuanya jadi 0-index (nggak ngubah solusi). Misal (i, j) artinya vertex ke-i, pada waktu j dalam modulo K. Bikin graf berikut:

  • source ke (i, i) untuk tiap 0 <= i < K, dengan kapasitas 1 (produsen)
  • (n-1, i) ke sink untuk tiap 0 <= i < K, dengan kapasitas INF (tujuan)
  • (a, i) ke (b, (i+1) mod K) untuk tiap a, b edge di input dan 0 <= i < K dengan kapasitas 1 (edge per satuan waktu modulo K)
Tinggal cari max flow dari graf tersebut. Karena banyak jawaban maksimum K ya.. O(K * BFS) = O(K2 M).

Anw, pas chat sama Ammar ternyata ada masalah wording di soal ini.

"These robots can be programmed, but their behavior on each product is deterministic, depending only on the producer which produces the respective product. ".

Ini bisa dipahami kalau untuk tiap produk, di setiap persimpangan gerakannya deterministik, jadi sebenarnya nggak bisa ada cycle (graf yang tadi mungkin ada cycle, cuma waktunya beda). Karena aku bacanya kecepetan, aku nggak nyadar ada kalimat itu. Dan kayaknya emang intended dari pembuat soal nggak kayak gitu. Jadi kasihan sama yang nggak ngerjain gara-gara mikir begitu :<

G - Rectangular City (post-contest)

Kalo gak salah pas kontes aku skip gara-gara salah ngerti soal. Pas nyoba upsolve, salah ngerti lagi :/ Btw, karena samplenya begitu, sekedar mengingatkan bahwa walaupun N event itu bentuknya persegi panjang, K titik yang diambil gak harus ngebentuk persegi panjang (sample nunjukin persegi semua).

Misal intersection dari N event itu kita nyatakan sebagai (r1, r2, c1, c2) dengan r1 <= r2 dan c1 <= c2. Kita akan pandang permasalahan r dan c ini terpisah, karena solusi permasalahan ini bisa dipakai di keduanya.

Sekarang kita fokus untuk r. Ada berapa banyak cara bikin N event, sehingga intersectionnya punya batas row (r1, r2)?

  • Ada r1N - (r1-1)N cara nentuin batas atas N event supaya batas atas intersectionnya r1. r1N artinya banyak cara yang intersectionnya <= r1, sedangkan (r1-1)N yang < r1. Kalo dikurangi jadinya pas di r1 intersectionnya
  • Dengan cara serupa, ada (R-r2+1)N - (R-r2)N cara nentuin batas bawah N event supaya batas bawah intersectionnya r2.
  • Untuk banyak cara (r1, r2), kaliin aja dua nilai itu
Nah, kalo sudah, kita bisa hitung rows[X], yang mana rows[X] menyatakan banyak cara sehingga tinggi intersectionnya X. Tinggal brute force (r1, r2) yang mungkin, terus tambahin banyak caranya ke panjangnya. Dengan cara serupa, hitung cols[Y], dengan patokan (c1, c2).

Selanjutnya, bisa kita lihat kalau rows[X] * cols[Y] menyatakan banyak cara bikin N event yang intersectionnya punya ukuran tepat X * Y. Jawaban yang kita cari itu banyak cara bikin N event yang intersectionnya punya ukuran >= K. Dengan precompute iN untuk tiap i yang mungkin di awal, kompleksitas solusi ini O(max(R, C) log N + R2 + C2 + RC).

H - Sliding Blocks (post-contest)

Ini soal lain yang males kubaca :/ Pas kontes aku udah baca dan came up sama suatu solusi, tapi males ngoding. Pas chat sama Ammar ternyata solusinya bener :P

Intinya karena bentuk grafnya tree, kita bisa cari urutan masukin baloknya pake toposort. Bikin edge berdasarkan treenya, terus berdasarkan arah slidenya. Kalo ke atas, artinya kita harus masukin ini duluan sebelum balok terdekat di bawahnya. Kalo ke kiri, artinya harus lebih dulu berdasarkan kanan terdekatnya. Dst, dst.

Solusiku O(B log B) dan lumayan jorok, copas-copas di mana-mana. Oh well, yang penting nggak TLE :P

And that's all!

Aku nggak ngerjain E, dan setelah chat dengan Ammar, untung aku nggak ngerjain. Salah ngerti soal >.> Kayaknya hampir semua tim salah ngerti soal. Kayaknya pengertian soal yang Ammar jelasin (convert -> asterisk check -> convert -> asterisk check dst) lebih doable, cuma aku nggak terlalu minat buat nyobain.

Overall, kayaknya... regional yang ini nggak terlalu susah? Mayoritas soalnya medium. Cukup yakin kalo ngerjain bertiga bareng Degol sama Inigo juga bisa AC 10-11 gitu. Agak sayang ada masalah sama soal D sama K (Donkey Kong?). Tapi ya, kontesnya cukup menarik. Menurutku Soal H sama I lumayan menarik. Terima kasih untuk panitia yang bikin mirror hehe. Semoga kalo ada ICPC Singapore lagi (mungkin beberapa tahun lagi? ada gap 3 tahun dari ICPC Singapore terakhir) bisa lebih keren lagi ^^