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.

Post-contest
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

Conclusion

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).

0 komentar:

Posting Komentar