IOI 2018, Tsukuba, Japan

Introduction

The 30th International Olympiad in Informatics (IOI) 2018 is held in Tsukuba, Ibaraki, Japan from 1st of September to 8th of September. The Malaysian team comprised Zi Song Yeoh, Jia Qing Tan, Jia Jun Lee, and Wei Xin Tan. The leaders were Yihang Ho and Chris Boo.

Mind-setting Camp

We rented a place at Suasana Loft Sentral for the mind-setting camp, where we mainly solved problems from other OI contests and discussed solutions. We did sports such as ping pong for bonding, where Wei Xin held amazing record of 100% lose rate against Zi Song across 15+ sets (3 of which ended with deuces). The overall atmosphere was cheerful. The camp ended with us departing from KLIA 2 to Japan.

Pre-departure group photo

Day 1-Arrival (1/9)

Even though the flight was 7 hours long and most of us had trouble getting some sleep, instead of feeling tired most of us felt excited as this is our first time in Japan! After around an hour of bus ride, we have arrived at Tsukuba, Ibaraki and were greeted by our lovely guide, Hisae, and had lunch.

Team arrives.

Source: https://ioi2018.jp/609/

Since we are in Japan, how can we not visit Akihabara, the home to everything anime, manga, and games? After settling all our luggage in our accommodation, we (along with some other teams) immediately went and took the Tsukuba Express line to Akihabara Station. After almost getting lost, we finally made it to Akihabara and were able to experience it first-hand.

Some photos of Akihabara

As expected, there were all sorts of anime goodies there which are rarely seen anywhere else. After much exploring (sadly not so much as we arrived there at around 4pm and had to go back to the venue by 7pm), we had dinner at some restaurant (which was nice) and managed to go back to our accommodation by curfew. Finally, the fatigue started to set in and everyone had a good night sleep.

Day 2-Opening Ceremony (2/9)

Today is the opening ceremony of IOI 2018. We were seated next to the Mexico team. To say their sombrero is big is an understatement. The opening ceremony started out with a live concert by the IOI 2018’s virtual ambassador and vocaloid, IA and her sister ONE (pronounced as “O-Neh”), where they performed the song “Reload” and the IOI 2018 Theme Song, “Euphoria”.

IA and ONE

Source: https://ioi2018.jp/737/

It was then followed by a series of speeches, including one from the Princess Kako of Akishino. After which are team introductions, with team Australia doing their “Ogee-Ogee-Ogee”, and Croatia team giving (throwing) away hats. Later, we started the practise session to test out the environment, find out how the system works etc. The problems were from JOI. After some revising at night, the teams went and get a good rest for Day 1.

Day 3-Contest Day 1 (3/9)

“Please do not touch anything.” The announcer said again and again when we are in the contest hall. After much anxious waiting, the contest finally began.

Day 1 tasks: combo, seats, werewolf.

Zi Song’s Perspective:

I started with combo since it seems easy. Indeed, it was destroyed within half an hour but looking at the progress bar it can be seen that combo is obviously the easiest problem anyway.

Next, I had to choose between werewolf and seats but since werewolf looked doable I gave it a try (to see how many points I could scrap). I tried to do sqrt decomp and then use some dsu structure to solve it (like JOI 2018 Open Contest P3) but I always had to use O(nsqrt(n)) time per block 😞 After 2 hours however, I managed to form a feasible idea and I realized the idea did not use sqrt decomp! I coded the solution and submitted, expecting it to maybe TLE since it was unoptimized, but I managed to get AC!

I had 200 points with about 2 hrs+ to go. Obviously, I went and get the easy 17 points on seats and then I went straight to the 33-point H=1 subtask. I thought it would be doable and in fact I managed to come up with an O(Qsqrt(N)logN) solution (or something like that) but I had no luck getting it to pass 😞

I ended the day with 217 points which was sufficient for tied rank 11. However, the scores were pretty close except Benq who perfected the day while the 2nd place is like 237 points (again a huge tie). I was not far above the gold cut-off however and last year I choked on day 2 so I could not relax yet.

Jia Jun’s Perspective:

This is my first time participating in the IOI, and I felt both nervous and exciting.

We entered the hall and waited about 30 mins while the staff member setting up the environment and servers.

After the host announced the start of the competition, I opened my envelope and 3 sets of the question were waiting ahead: Combo, Seats, and Werewolf. I read through all 3 of them and I had a good feeling about Combo, so I started working hard on it.

I managed to get 30 points on my first attempt, using a naive solution, and I kept on doing some math, try and errors on my paper.

After some clever observation on the constraints, I finally get an AC in Combo. There are about 2 and a half hours left, but I was scoreless after the first 100 points. I got stuck in a wrong algorithm for the problem Seats. I thought it was correct at the time being but I missed some trivial cases. It could be easy 30+ points by brute force, but my luck and so as the time ran out.

My score is below 2/3 of the total contestants, so I had to work hard to climb back in Day 2.

Jia Qing’s perspective:

At first, I used about half hours to read through all the problems. I only solve 30-points subtask solution of problem Combo at first. Since I forgot a quite important condition which is the first character won’t appear again, I wasted a long time to think about it. After that, I went to think another two problems. After trying the case of a line graph in problem werewolf, but I failed. So I went to try the problem seats. The subtask 1,2,4 is solved by some observation. But unfortunately, I wasted about two hours to think and coded a wrong solution of the subtask 5. At last, I only get 47 points.

Wei Xin’s perspective:

I started out by reading all 3 problems, as one should always do in any contests since it is not guaranteed the problems presented are sorted in increasing difficulty. Combo seems to be easiest, where you have to guess a string using minimum number of queries. The 30-points subtask is indeed the easiest to implement. After getting it, I tried to fully solve the problem. The main issue is that all the solutions have asymptomatically same time complexity wise O(n), therefore time-complexity is not the issue, but rather an optimal number of queries are needed. After about 1-2 hours, I realised there was a tiny but important detail of the problem statement which I have misread. Sadly, I don’t see any way I can incorporate the detail into strategies that I came up with, turns out my way of solving is not optimal to begin with. Seats seems like it requires extensive knowledge of data structures to solve, so I did not pay to much attention to it. Werewolf, however, is graph theory, my favourite types of problem. The first 15-points subtask was rather easy to implement, but the peculiar (at least for me) style of input of IOI did cost me some time debugging. After which I went back and forth between combo and werewolf, hoping I can still do something about them. Alas, due to time constraint, and the stress imposed by the live statistics showing that combo is the easiest problem, I was not flexible enough to switch my strategy on tackling combo. As for werewolf, I tried implementing a segment tree solution for the case of a line graph. However. I messed up the implementation somewhere down the line and couldn’t get that in time as well. The contest ended with me only getting 45 points, so that’s unfortunate.

After the contest has ended, we went around Tsukuba visiting convenience stores and supermarkets buying some of the famous local snacks and chocolates. 

Day 4-Excursion Day 1 (4/9)

For the excursion, we went to visit Japan Aerospace Exploration Agency (JAXA) Space Dome, where we got to see some models of rockets and spacecrafts, even astronauts’ suits. Makes one think how of how far we have come, how our desire for knowledge even brought us to exploring outer space.

After that, we went and visit the Geological Museum and Science Square Tsukuba of National Institute of Advanced Industrial Science and Technology (AIST). We got the chance to see some very interesting fossils and how the earthquakes have affected Japan throughout the years. The Science Square Tsukuba also showcased some recent developments in research to better our lives, such as the invention of robot baby seal Paro, which can help in therapy.

One of said robots.

We also got to visit the Warp Station Edo, which is a recreation of the traditional Japanese town for filming TV shows or moving.

What is IOI without some fun? We joined the Fun Time at night, where we get to try our hands on various juggling activities and circus tricks, such as spinning plates, juggling sticks, and balloon-art.

Source: https://ioi2018.jp/823/

Day 5-Contest Day 2 (5/9)

There was less delay as everyone is already familiar with how the contest will start.

Day 2 tasks: dolls, highway, meetings

Zi Song’s Perspective:

I started with highway since it is an interactive problem. I tried to solve the tree case and I thought I solved it. Then I proceeded to the graph case and at some point, thought I had an at least 90-point solution. Initially I thought of using Heavy-Light Decomposition to solve the tree case but to my horror I realized it fails (on a star tree). Luckily, I was able to come up with another idea that works (picking nodes from leaves) and submitted a solution. Alas, I got 51 points (only solved the tree case).

I quickly tried to figure out what was wrong since around 2 hours had passed at that point I think. I was panicking a bit but after some random stress testing I managed to find the bug and could fix it and got 90 points. That was good enough on this problem for me, I thought.

Then I looked at the score bar and was shocked to see that highway had the least total points scored! I quickly went to dolls which had the most scored points but I could not do better than using 2N switches which sadly only gives 37 points 😞 I tried to figure it out for the next hour but did not manage to kill it 😞 In the last 20 minutes or so, I quickly scraped some points on meetings and got 4+17 (brute force + segment tree) but alas I was not able to code the 15-point simple subtask in time (which most people got).

I ended the day with 150 points exactly (39 (2 from trivial subtask) + 90 + 21 = 150) and I thought I screwed up. Surely based on the statistics doll might have been a giveaway and thus everyone would surely have a base score of 100 on that day. I thought I was not getting gold and could only get silver now.

The story had a happy ending though. I came out of the contest hall, slightly sad about my performance, but then got congratulated by another team guide (who was also from Malaysia) and I was told that I made the gold cut-off. I was shocked at the moment but when I checked the results I was indeed in 14th place which is around halfway from the gold cut-off to first place. It seemed like dolls was indeed the most solved problem of the day in the end, but it was probably like last year’s Day 1 problem wiring and the statistics might have also influenced a lot of people to work on dolls.

Jia Jun’s perspective:

We went through the same schedule as day 1, but the questions are way harder than I thought.

The 3 questions are Mechanical Dolls, Highway Tolls, Meetings. I read through all of them and I really don’t have a clue where to start.

I wasted the first 2 hours trying all kinds of algorithms on every question, but it just didn’t work. Mechanical Dolls is a pretty long question and it took me quite a long time to understand it. I did what I could but I end up with 6 points only. I really didn’t do well

on the second day, maybe due to inexperience and lack of practice. Although I did not win any medal in the end, it motivates

to work harder. I felt blessed and honoured to be a part of this competition and a member of team Malaysia.

Jia Qing’s perspective:

Same as day 1, I read through the problems at first. Before the contest, we thought that it will be an output only problem, but there were none. After reading the problems, I checked the scoring contribution. And I started to try the most scored problem which is problem meetings. First two subtask solved by some brute force and third subtask solved by a segment tree. After that, I went to try the problem doll, the first subtask can be solved easily but it’s only 2 marks. And I wasted some time to try subtask 2, but I need to left some time to try problem highway so I didn’t solve it at last. The subtask 1,2,3 of highway problem were solved on paper but I only have time to code out the two of them. At the end of the contest, I only got 50 points. It’s so terrible.

Wei Xin’s perspective:

The same routine, I started by reading all 3 problems. Meeting was easy to understand and looked standard, so my initial fear is that it will be the easiest among the 3 problems for that day. I did have some idea for an O(n^2) solution for the first 19-points subtask, which I implemented and fortunately, it passed for the 2 subtasks. Since the problem is about querying a range [l, r], I suspected Mo’s algorithm may be needed for the following subtasks, however, I cannot think of an easy of a way to update the answer easily. Subtask 3 seems doable without Mo’s algorithm, and a segment tree seems to do just fine, but I do not wish to miss out on other problems too, so I made a mental note to come back to that later and thought about other problems as well.

The live statistics indicated that dolls is the easiest, so I tried that for a little, before realising even just testing out ideas are very time consuming (try to simulate the process on a paper and you’ll understand), and any ideas I could think of would take a ton of time to implement, so I just abandoned it, as highway is another graph problem and I think I would have a better shot at it. I started by tackling the tree cases. Initially, I thought it would require some HLD techniques which I am not familiar with. Regardless I spent some time thinking about the problem and was able to come up with a solution worth 6 points, and with a bit of tinkering worth 11 points. However, the segment tree solution for the subtask I mentioned earlier worth 17 points and both seem equally time-consuming for implementation, so I went for the segment tree subtask first.

It may be due to the way I defined the data structures because I ended with quite a lot of casework and about 200 lines of codes, which took me quite some time to implement. No matter, after submitted once I finished implementing at about 3 hours mark. It didn’t work. My heart sank a bit and I started to doubt my solution. Is it entirely wrong or is it just some bug? I believe I did prove the idea to be correct but that was rather easy, did I miss something? Then I decided it is probably just some bug in the code, but as mentioned it is 200 lines. I’m starting to feel stressed out. No matter, I did define everything quite rigorously, and I believe my case works are correct, it is probably just the problem of implementation. So, I recoded some of the parts, looking through each line carefully. Once I am done, I submitted and, lo and behold, it worked. I was so relieved when I saw the 36 points I let out a small “Yes.”. It is still scary thinking back if I did not get the subtask I would’ve spent about 2 to 3 hours for nothing.

I quickly went back to Highway and started with the line graph case. The problem is about querying about a graph by modifying the edges to determine 2 nodes. For the case of the line graph and knowing 1 of the nodes, the other nodes can be found by a simple binary search. However initially I thought the way I modified the edges would give me a TLE if I were to submit it, so I spent a bit of time defining a pointer to efficiently update the edges (after contest Zi Song told me it didn’t matter if I didn’t use a pointer since we are not querying a lot of times, I would’ve only modified O(nlogn) times and it would still pass, sadly I didn’t realise this during the contest). Once I got the 6 points, I quickly modified a bit to get another 5 points, totalling 11 points for that problem. Unfortunately, it is almost the end of the contest, and I didn’t get much time thinking about one of the subtasks, which was worth another 7 points and didn’t seem hard to implement as well. So, I ended up with 47 points on day 2, totalling 92 points for this IOI. I still regret I didn’t get combo, which if I did would put me at a much higher ranking, but I definitely do not regret the time I put into Informatics Olympiad.

After the contest, we get to enjoy the spectacular joint performance of shamisen and wodaiko by the Kiraku-za theater troupe and ‘Mugenjuku’ shamisen students from Tsukuba University, where they performed songs such as “SoranBushi” and “Kokoro no Naka no Taiyo”.

Day 6-Excursion Day 2 (6/9)

For today’s excursion, we get to visit the Hitachi Seaside Park, which is filled with beautiful sceneries.

Basically Windows XP desktop background

Following that is the visit to Oarai Shrine near the ocean, where we learned how to pray in their shrine, got the chance to enjoy the sea breeze, and climbed a lot of stairs.

Like, a lot

The excursion ended with a visit to the Aqua World Oarai, where we got to see various marine life, and a dolphin and sea lion show.

Day 7-Closing Ceremony (7/9)

The morning started with a knowledge fair, where we chose to sit through the film concert performed by IA, and an informative talk about competitive programming and future careers by iwiwi, who was top 4 on TopCoder.

We also got treated some of the local sushi’s and puddings by Ivan, Malaysian guide for Norway for lunch.

Thanks Ivan!

Sadly, everything must come to an end. Today will be the closing ceremony of IOI 2018. There were a lot of speeches by various committee members. Most of us felt bittersweet as this will be our last IOI. What is not sad though is the fact that our Zi Song just brought home Malaysia its first gold medal in IOI!

Congratulations to Zi Song!

Last group photo

Following that is the Sayonara Party, where contestants get to congratulate (or comfort) one another on their performance, take pictures together and get contact details to keep in touch with each other.

Since the Sayonara Party ended rather early, we had Hisae took us to a noodle shop, to try out some local ramen.

And it was good!

We went back to dorm to get some rest early as our flight back the next day is quite early.

Day 8-Farewell (8/9)

After we got to the airport in the morning, we did some last-minute shopping for souvenirs. We then departed from Narita airport and had a smooth flight back to Malaysia at 10.20am. Sayonara Japan!

We would like to express our sincere gratitude to the hosts for holding such an amazing IOI and the volunteers for helping. Not to mention our trainers, family members, and friends for the support along the way. Thank you!