Introduction

The 33rd International Olympiad in Informatics (IOI) 2021 was held in Singapore from 19 June to 28 June. The Malaysian team comprised Hua Zhi Vee, Je Qin Chooi, Kwong Weng Loh, and Shao Qian Chew. The leaders were Wei Xin Tan and Li Xuan Tan.

Due to the pandemic, we participated in the contest in our own homes. It was the first IOI for all four of us.

Preparation

There was no official mind-setting camp. However, Zi Song was kind enough to set us up with some other ASEAN countries, where each country prepared a sparring round. Obviously, Zi Song wrote Malaysia’s (A big thank you to Zi Song).

Je Qin’s Perspective:

Roughly a month before IOI the ASEAN countries trained together in sparring rounds, which are 5-hour contests with problems from each national TST (team selection tests) or elsewhere. Here we have to thank Zi Song for writing the Malaysian sparring round. Looking back, however, time can be better spent doing past OI instead, as most problems in the sparring round are more ICPC-style and don’t have well-written editorials. Very little can be learnt from these problems that will be useful in IOI compared to doing past JOI or IOI. Here we have to thank Zi Song again for preparing an editorial for the Malaysian sparring round.

During the IOI week, I spent my last training time solving CSES (solving almost all problems in DP, Graph, Tree, Range Queries). I recommend IOI delegates complete all CSES problems before your IOI, as I’ve learnt a lot from solving these problems.

Contest Day 1

Day 1 tasks: Candies, Keys, Parks. An online judge is available here.

Hua Zhi’s Perspective

This is my first time participating in IOI, and although I didn’t have much hope for a medal, I decided I have to do my best and not leave any regrets.

The first few subtasks were trivial and were just a matter of implementing them. I decided to skip those first and focus on harder subtasks, then implementing them altogether. I had no idea how to solve candies (except for subtask 1), and my solution for parks was quite implementation-heavy, so I decided to focus on keys first. I had no idea how to go further than 37, so I decided on 37. After spending a couple of minutes on the first subtask on candies. I decided to focus on one single problem. Since I had some ideas on parks, I decided to spend all my time on them. My idea was correct, but it exceeded the time limit for larger cases. I managed to optimize it to linear complexity from a simple observation that used a lot of loops. By the four hour mark, I had 95 points. I wanted to get a three-digit number, hence I spent about 25 minutes on subtask two on candies. I proceeded to try the harder subtasks of candies but failed. After the contest ended and after some discussions, I realized I missed solving fountains just by one more simple observation. Although I had some regrets, I was happy with the results (11 + 37 + 55 = 103).

Kwong Weng’s Perspective

This is my first time participating in IOI, so I was nervous but at the same time excited for it although it was held online instead of onsite due to the current pandemic situation. My hope is to give it my best and at least get a medal.

As usual, I was presented with 3 problems, which are Candies, Keys and Parks. I spent the first 15 minutes reading through the problems, and none of them seemed to be easier than the other. Therefore, I followed my initial plan to use 45 minutes on each problem, in their given order. I managed to grab 11 points for Candies and was upset to realise the third subtask requires segment tree beats (a modified segment tree to allow segment addition and max/min operation, which ordinary segment tree can’t handle) because I heard about it but I didn’t learn it. Then, I went on trying Keys. I coded a brute-force BFS which gave me 37 points. I managed to construct a greedy solution for Parks, which I submitted in hope of an AC. Unfortunately, it only got 30 points. Being unable to make any further progress for Candies and Keys, I decided to go all in and tried to fix my solution for Parks to get an AC. I tried to create counterexamples for my approach, but none of them made my solution fail, which was bad because I couldn’t. After getting stuck for 2 hours, I ended up with (11 + 37 + 30 = 78 points) for Day 1, which was below my expectation but at least I was at the top 50%. Apparently, it was a difficult Day 1.

Shao Qian’s Perspective

This is my first participation in IOI, even though it was held completely online. I am still very grateful that I got to participate. Day 1 was a very rough start for me. I spent the first 5-10 mins reading candy and keys, and I thought I had a concrete solution for every subtask except for the last one so I started coding away. One hour later, to my absolute horror, the solution was wrong. The idea still somewhat works for subtask 3, which was worth 26 points. But I had to code sqrt decomposition + keeping a segment tree in each bucket which was very difficult to implement. In the end, I decided to put it off first and get the trivial 11 points. With about 3 and a half hours left, I tried keys and parks, which I found very hard. For keys, the 37 O(n^2) BFS subtasks were trivial to most people, but further subtasks were a complete brick wall for me. In the end, I didn’t manage to get further than 37. And finally parks, I really regretted my decision on this problem.. I spent some time thinking about it. I saw that I had no concrete construction, and even worse, I somehow misread subtask 2 which was simply two vertical lines! In the end, I didn’t even bother to try to write a solution past subtask 1, with around 2 hours left and with 11+37+5 I decided to go for the 26 points subtask on candy. I spent the entire 2 hours coding and debugging that subtask, but in the end, I made no progress and ended up having the lowest score on the Malaysian team and was in the no-medal range, heartbroken, I had no high expectation for day 2.

Codecombat

Shao Qian’s Perspective:

I did not participate, after day 1 I wanted to rest. So I did exactly that and enjoyed the spectacle of someone from the Indonesian team crushing other participants with a score along the lines of 38 - 0.

Hua Zhi’s Perspective:

It was a desperate attempt at getting some cash prize. Je Qin and I tried to imitate ideas from higher-ranked players, but we failed horribly, as they were better and more experienced than us. It was fun overall, and I even watched the finals. It was fun watching different strategies at play.

Contest Day 2

“Check your screen recordings” - Wei Xin.

Day 2 Tasks: DNA, Dungeons, Registers. An online judge is available here.

Hua Zhi’s Perspective

I started with dna since it seems easy. Indeed, it was destroyed in about half an hour. It felt good for a moment but just for a moment. Registers was confusing, so I started with dungeons first. The first subtask was just simulating, but I could not proceed further than that. I then focused on registers. The first two subtasks were okay but I spent a long time debugging (I didn’t know how the “arrays” worked). I felt hopeless after that and ate some pizza. Then, I had an idea for dungeons but apparently, it was still too slow. After some time, I realized I can optimize it by precomputing 2^i steps for each node, getting the idea from binary lifting. I got the last 13 points in the last 15 minutes. It ended with (100 + 24 + 21 = 145)

Kwong Weng’s Perspective

I started off with DNA because it looked easy. Indeed, I got my first AC after 30 minutes. This was good news. Then I went on to Dungeons, and I managed to grab the easiest worth 11 points. Registers, on the other hand, was quite implementation heavy and I spent quite a lot of time solving the first 2 subtasks for 21 points. Then I moved back to Dungeons and tried to solve the third subtask. I spent about 1-2 hours debugging and finally managed to get the 13 points. My final score is 100 + 24 + 21 = 145 points, which is satisfactory, I thought. However, it turned out that my Day 2 performance was worse compared to Day 1 (in terms of ranking), but nevertheless, I managed to get a Bronze medal, and I was quite happy about it since this is my first participation.

Shao Qian’s Perspective

With 2 rest days, we were back refreshed. I spent the first 15 mins reading DNA and dungeons playing with ideas on both, I didn’t bother to read registers yet because well, the statement was 6 pages long and had 9 operations you can do on the registers . After a while I decided to go for a DNA, my plan was to go for each subtask in order and not repeat the same mistake I did with candies on day 1. To my surprise the final two subtasks were surprisingly easy. The solution ended up just being keeping 6 prefix sums then printing a single line. I ACed after 50 mins. I was somewhat relieved but yet also somewhat worried because I found it too easy and if everyone ACed as well then the 100 pts wouldn’t be much of a significance (after day 2 as it happened that was exactly the case, DNA ended up breaking the record as the IOI problem with most ACs, having 300 ACs out of 381 participants), after ACing DNA I immediately started on dungeons, in the end I solved subtask 1,3,4 with subtask 1 being pure brute force and 3 and 4 being basic binary lifting (I missed the observation needed on top on binary lifting for further subtasks). I spent quite some time on subtask 2 which was worth 26 points but I didn’t manage to solve it during the contest, next was registers. After reading the laborious statement, it turned out that the problem isn’t actually as complex as it first seems. it just had a lot of operations it needed to describe. I solved the first 2 subtasks with exactly 20 queries, After the first two subtasks I made no further progress, subtask 3 and 4 was some assembly magic which I only knew after the contest (guess I am taking assembly lessons to counter metaprogramming problems), in the end, my score was 100+36+21 = 157 which was highest on the MYS team in day 2, I was satisfied but still somewhat worried that my disaster of a day 1 would drag me down. But in the end, I still managed to pull through, I was happy with my results.

Je Qin’s Perspective (Day 1 + 2)

Once you have gotten this far, you will get a medal if you do your best. You won’t fall below the baseline (bronze cutoff) if you solved all trivial subtasks. Look what happened on Day 1. For Day 2, it is my mistake that I’ve spent too much time on DNA following the strategy of solving each subtask in turn, which cost me the time to get the second (trivial) subtask of Registers. Getting that 11 points will secure me a bronze, as I’m 6 points below the cutoff. Ironically, another 5 minutes are all I need out of the 5 hours.

Surprisingly, DNA is so trivial against the backdrop of IOI, especially after Day 1 when you need segment tree beats to solve a subtask of the first problem. The strategy of solving subtasks instead of attempting AC had failed me miserably in DNA and cost me my medal. I can only blame myself because a highly-skilled Olympian can quickly gauge the difficulty of a problem, and adapt his strategy accordingly. I’ve played too safe.

Closing Ceremony

We received three bronze, which was a great achievement, as we were all first-timers.

The results are available here.

Thoughts

Hua Zhi

It was a fun experience, from the training to the contest itself. I even joined one of the virtual tours for fun. I look forward to participating in the contest on-site.

I was quite sad I could have ACed D1C if I had a little more time. Nonetheless, I am grateful for being able to participate in such a prestigious competition and am very happy to get a bronze medal.

Je Qin

Now some personal reflections. I felt terrible when the ranking is out, especially when the cutoff is almost within reach and I know that I can get that bronze if I have just a bit more time. Being the odd one out in the team stings too. The week after IOI was no better when I suddenly have time to do things that I wanted, but what I enjoyed all these months leading up to IOI was preparing for IOI. I took some time before resuming my normal life, which shed light on how I view things. I had been too obsessive about getting a medal in IOI. To quote: “Success cannot be pursued, only ensued”. You shouldn’t aim to get a medal. Instead, aim to be good in CP, and a medal will naturally fall within your reach. For me, IOI 2021 is less of a competition, but of growth that I’m grateful for.

Kwong Weng

Overall, it’s an enjoyable and memorable experience despite having to do it online. I am a little sad that I did not manage to get an AC for Parks which could have gotten me a silver medal, but I am happy with a bronze medal. I am looking forward to joining future IOI’s onsite because it’s obviously much better than doing it alone at home. Nevertheless, I should not only seek for medals, instead improvements towards a better competitive programmer are more important.

Shao Qian

IOI 2021 was a fun experience, even though it was online. I enjoyed the contest and the few months of training leading up to it, we even had the chance to train and interact with people from other ASEAN countries which was fun (again big thanks to Zi Song). Overall it was a fun experience, obviously I had regrets about my performance but nonetheless, I am grateful that I have had the opportunity to participate and even win a bronze medal and anymore said would be otherwise, I look forward to IOI 2022 : )