IOI 2019, Baku, Azerbaijan

Introduction

The 31st International Olympiad in Informatics (IOI) 2018 is held in Baku, Azerbaijan from 4th of August to 11th of August. The Malaysian team comprised Jia Jun Lee, Ming Yean Lim, Kel Zin Tan, and Li Xuan Tan. The leaders were Wei Xin Tan and Zun Yuan Lim.

Mindsetting Camp (July 28 - August 2)

We checked in to Suasana Sentral Loft (same old place), where we stayed for the entire duration of the mindsetting camp. Ming Yean (aka mlyean) and Wei Xin (aka duckmoon) arrived the night before, and the rest of us (Kel Zin, aka kelzzin2, aka mechfrog88 and Jia Jun, aka 2xJelly) check in on the day itself.

The daily schedule of the mindsetting camp could be approximated by : wake up, bread/biscuits for breakfast, morning sharing session (where everyone gets a topic to research and share), go to nuSentral for lunch, mock contest in afternoon, “give up and start discussing” about 3 hours in, go to nuSentral for dinner, continued problem solving/ping-pong/free time at night. I spend a lot of my free time working on a robotics project for my school’s team at a competition. Oh well.

Sometime around the third night, somehow cough Kel Zin gets introduced to the Muffin Song, and soon the apartment is frequently filled with the suicidal cries of a freshly-baked muffin. No explanation is needed, just watch the video. Wei Xin shares past IOI experiences such as the team going out on their own and nearly getting lost in the legendary Akihabara district (spoiler alert: not so much freedom this time, although we do get awesome excursions). I also share with the team IMO 2019’s problem 5, which feels very, very much like a CP problem. There is also a night when a joke about Azerbaijan perhaps being dangerous ends up in Wei Xin googling “Azerbaijan war” and finding out that the last such report was in 2017 :monkaS:

At nuSentral, we frequently go to the Quizinn food court for lunch and dinner, as well as the grocery store on Lower Ground floor to buy breakfast (because we don’t all wake at the same time and thus going out for breakfast is not so simple). Other “notable visits” include Sakae Sushi and Pasta Zanmai.

After 5 days of problem solving, we’re all better prepared for the IOI. Documents have been taken care of by our deputy leader Wei Xin, and nothing really important goes wrong. We check out of Suasana Sentral around noon on August 2, to meet at KLIA later that night for the flight to Baku via Sharjah.

Departure Day (August 2)

Between checking out of Suasana Sentral and meeting at KLIA for our flight to Baku is a gap of 12 hours. duckmoon bemoans the length of time he will have to spend alone since he can’t go “home” before going to KLIA, oops… The end result is Wei Xin coming to my house to kill time and we go to the airport together at night.

Upon reaching the airport and going to the departure level, we see something “unusual”: about 300 immigrants/pilgrims/tourists queuing to check in, and their luggage mostly consists of MASSIVE plastic-wrapped packs of… Bedsheets? This unusual line literally spans half the check-in area. What.

Half an hour later, the team gathers in full near the Air Arabia check-in counter, and Kel Zin brings the promised Malaysian flag. Several pictures with parents later, we’re off to check-in (which takes a while considering the surprisingly long queue of passengers to Sharjah), and we get the boarding passes straight to Sharjah, with assurances that our bags will be put on the correct flight in transit. The flight is decent, and we land in Sharjah International, where we initially try to locate all possible boarding gates (our return transit is very short, so it helps to know where to go), only to find that the airport isn’t actually that big. It does have a food court, some duty-free shops, and… A playground.

A few hours of lounging around the airport later, we board the flight to Baku, and other than a gate change an hour before departure, nothing major goes wrong. The meal I chose for this flight was much better than the one I chose for KUL-SHJ… oops. Leaving the heat of Sharjah is a welcome relief for some of the team members…

Arrival Day (August 3)

…and we arrive in Baku to be blown away, literally. They don’t call Baku the City of Winds for nothing. Before all the stories about wind, though… We’re blown away (last pun) by the incredible design of the airport. The airport looks very modern, with geometric designs seemingly everywhere. IOI staff meet us at the immigration counters and guide us to the luggage carousels to get our things. This billboard appears on the large screen in the area:

Nicely done, Azerbaijan! After a brief luggage scare when our bags take the longest to arrive despite being among the last to be loaded onto the plane (maybe the plane’s cargo hold is FIFO), we pass customs and meet our leader, Zun Yuan (aka redocyz). After registering at the IOI welcoming counter and a bit of currency exchange, we leave for the Athletes’ Village.

We’re the only team on the van because we arrived early, so we’re accompanied by lots of IOI staff and guides. We meet our guide, Bakhtiyar here, and he introduces us to some of Baku’s culture and architecture as we pass by. Kel Zin also gets dragged into what is apparently the national dance, and an impromptu dance session ensues inside the van.

Upon arriving at the Athletes’ Village, we go to the recreation center/helpdesk to register, getting an IOI bag with a bunch of gifts. There are really strong winds outside, and the sharp corners of the buildings tend to create mini-vortices or tornadoes that whip up all manner of random stuff on the ground. This is at first quite amusing to us, as we observe things like buckets rolling around, plastic bags flying wildly and such. After checking in, we head to our room whereas Zun Yuan and Wei Xin head to the leaders’ accommodation… or so we thought.

The lift isn’t working, so we drag our luggage up to the 10th floor of the building to get to our room, except that our room is on the 9th floor. Oops. A while later, we’re told that Wei Xin is supposed to be with us… then inexplicably Zun Yuan returns from the hotel. After some confusion, Zun Yuan and Wei Xin return to their hotel, and the rest of us lounge around or do some coding in the room, although we’re restricted by the fact that there’s no WiFi in the rooms. The room is fairly nice, with four two-person bedrooms and a four-person bedroom, for the four of us and Bakhtiyar. We take two of the two-person bedrooms and Bakhtiyar another, leaving two empty rooms (some other teams apparently had to share rooms). Bakhtiyar warns us not to open the windows or go onto the balcony, since the winds are very strong and sand can frequently blow into the rooms. We’ve experienced the strong winds while outside, so everyone agrees not to leave any window open (thankfully). On this evening, we also get our first taste of Azerbaijani food, which is impressively flavorful. The overall environment is nice and windy, albeit cold at night when we settle in for a night of sleep.

Day 1 (August 4)

4/8 was the official Day 1 of IOI and most of the teams arrive on this day. But since we arrived a day earlier, we then had a lot of free time throughout the day. Li Xuan and Ming Yean share a room while Jia Jun and me share another room with a balcony (which has a nice view!) . Li Xuan had set his alarm and woke us all up at 7:00 am. Personally, I was quite comfortable with the timezone in Baku (GMT+4) which was 4 hour earlier than Malaysia’s time. Waking up at 7:00 am in Baku means waking up in 11:00 am in Malaysia which was perfect for me. After that , Bakhtiyar brought us to have our first breakfast in Baku. The food was basically ham, chicken , beef and sausage (normal western breakfast). Nevertheless , I enjoyed the food and have some nice yogurt.

After breakfast, we spent most of our time in recreation and entertainment room, which had table tennis , table football and snooker installed, for the contestants to play. We spent most of our time playing table football , Li Xuan even joked about that table football is our national sport. Also, more teams had arrived and the recreation room was getting busier. Besides playing table football, we found a sofa to sit down and played with our phone. Li Xuan was answering SPM maths problem and the rest of us were just surfing the web. Bakhtiyar tried to talked to us and wanted us to be more socialize. He also brought his friends together to talk with us (apparently it doesn’t work). We spent our time in the room until lunchtime. The lunch was better and notably there’s russian salad which was very special in taste. After lunch ,we went back to the recreation room to kill time. Then, Wei Xin and Zun Yuan arrived at athlete’s village. They had lunch at the dining room and then we returned to our room and got some rest.

In the evening, there was a bus tour of Baku City and Highland Park. Baktiyar brought us to the buses which were parked outside athele’s villages. Then we started to find out our bus with the corresponding bus number which had written on our name tag (10). However, the bus was not sorted with number! So we just did a linear search. We found every number but no 10!! Then Bakhtiyar just brought us up to a random bus. The bus was quite new and the driver looks experienced. There was also a safety instruction in the seat pocket just like the one in every flight. After few minutes, we started our journey and I was amazed by the scenery in Baku City. The city was like baby born between the west and east , tradision and modern. Most of the buildings in Baku are gothic styled. But there were also some exception such as Flame Tower and Heydar Aliyev Center which are very modern and stylish. I tried to take pictures but the bus’s window was coated with shades. The tourist guide told us about the buildings and places throughout the road trip. Bakhtiyar also did a great job explaining stuff to us.

The Highland Park is somewhere which let us to view the city in Baku at once. The park was located beside Caspian Sea and Flame Tower , we took a lot of photos and listened to the history of Azerbaijan. We were there about 2 hours and then we return to athele’s village. Meanwhile Zun Yan and Wei Xin returned to Boulevard Hotel. Then comes the dinner time. The food was fabulous this time and I enjoyed it a lot. After dinner we just went back to our room and get some rest.

Day 2 / Opening Ceremony (August 5)

We woke up early in the morning, went for breakfast, and start walking towards the National Gymnastics Arena. Today is still a windy day, we can barely walk in a straight line and trash are blown all over the place. There were police stopping the traffic in order to secure our safety when crossing the road. We then walk down a tunnel that lead us to the arena. Upon arriving at the National Gymnastics Arena, another wave of strong wind was waiting for us. We then split into 2 pairs, which Li Xuan and I wait at gate L, whereas Kel Zin and Ming Yean went to the other gate. While queuing for the security check before entering the hall, the strong winds are still blowing, it is so powerful that we thought our lifetime knowledge about coding (Data Structure / Algorithm / Template Code…) were getting blown away! After a short while, we finally get into the contest hall. We get to our seats and begin waiting for the practice session to start. After about half an hour, the practice session started! I begin looking through the LINUX environment, familiarise myself with the IDE’s and contest website. Then I start logging into my account, looking at seems to be the easiest problem of all problems, which most of the contestants had already solved. After an hour of coding and submitting answers, I found myself stuck at about 50 points, which my code went WA at the last subtask. I was frustrated but I can’t do nothing about it. So instead of continue working on the other problems, I went to code some template code and data structure that I might use in the contest, just to make sure I remember the code and able to code it quickly during contest. The practise session ends in about an hour later. Li xuan was stuck in the same question too during the practise session, while the other two already completed more the half the problems. After the session ends, we have a brief discussion with our team leaders, and submit things we needed during the contest. We went back to the Athletes’ Village to have lunch. After lunch, we hop on to our bus and went to Baku Convention Center for our opening ceremony. First of all is the speeches by the chairman, sponsors, directors, etc. Then, we were presented with traditional Azerbaijani dance and musical performance, it was amazing, truly shows how Asian and European musical instrument were able to fuse together beautifully. However, the only flaw is that the spotlight was constantly flashing at our direction, which makes us difficult to enjoy the show. Next, each team were asked to stand up from their seats in order to welcome them. We bring out our Malaysia flag, which was bought just before our flight, and embrace the love and applause from all the teams. The ceremony ended after that. We moved to a nearby hall to have some drinks and also discuss with the team leaders. After that, we went back to Athletes’ Village to have dinner. When we were about to went back our room, our team guide told us he need to quarantine our electronic devices, where we kept most our notes in it. We were shocked because we thought we could still revise our code. We quickly look through all of our notes in our phones and laptops, memorise every details that our brain can contain. After the quarantine, we slept early to reserve energy for the day after, which is Contest Day 1.

Day 3 / Contest Day 1 (August 6)

MYS-2 (Kel Zin)’s perspective : The tasks were Rectangles, Shoes and Split.

I was very nervous. Since Rectangles was the first task, I read through it and thought that I can tackle the first subtask with brute force. Then I just started doing it without looking at other problems (which was very bad). I code and debug but just couldn’t get it right. 50 minutes had passed and I was very worried that I might get 0 marks. Zun Yan had jokingly told us yesterday to not get 0 marks as it would be a disgrace for Malaysia team. I was getting more worried and only I decided to just gave up on Rectangles and look at Shoes.

When I saw the first subtask of Shoes, I was a little bit confused. “Isn’t this just 2 line of code ?” I tried to code it out and boom , I got 10 marks for it. I was very relieved when I saw the 10 marks. Finally no 0 anymore. Finally I didn’t have to worry becoming a disgrace for Malaysia.

Things started to get well afterwards. I got 30 marks in Shoes and also solved the first subtaks in Rectangle. Then I realized that Shoes might be the easiest tasks in day 1 and just thought that perhaps I could get AC in Shoes. So I tried and tried then finally I got it. I was very happy and asked for a banana from the IOI committee. Then, I continued to look through Split and solve the brute force subtaks.

Now I had solved the easy subtasks and trying to get more marks. There was about one and a half hour left. But I started to feel abit dizzy. I tried to solve Rectangles but I just couldn’t. I looked at the next subtaks of Split and just thought that it was too complicated and I gave up on it (apparently it was the easy one). I didn’t get any more marks since then. The total score for me on the first day would be 136.

MYS-3 (Li Xuan)’s perspective : Going into the contest hall with basically nothing is a whole different experience from the IMO ._. Also, my mouse was rendered almost unusable by residue from the sticker that was used to label it… No choice but to use the provided mouse, oh well.

Contest starts on time, and everyone opens their problem folders (we got a Chinese translation of the problems as well thanks to @mechfrog88’s request).

Shoes looks the most doable immediately.. and subtask N=1 is free 10, lol. At first glance, split looks like the tree case should provide an insight to solve the entire problem. Rect looks nearly unapproachable.

So my first instinct was to attempt shoes. After getting free 25 (N=1, and all left shoes are to the left of all right shoes), I start trying to think of a solution for the whole problem, since it doesn’t seem THAT difficult… can greedy work? No (at this point my brain crashed and I thought the answer was no, because I couldn’t find a proof). Let’s try the brute force subtask N=8…and I had no idea how I could implement the brute force. I spent a long time (~2 hours?) here just thinking about what else could solve the full problem… until I discovered that greedy apparently works. This problem was apparently somewhat controversial because it appeared as Codeforces 995B (with lower constraints). Now the question is how to implement greedy? Naïve solution TLEs because checking both shoes in each pair is O(N2), so we need a way to find efficiently, for any given shoe, the other shoe’s position. It’s here that I thought of using two PBDS to store (size, position), one sorted by size and the other by position. Iterating through the position PBDS, in log(N) on the other PBDS we can find the position of its pair. This should be O(N log N) which should pass… except my implementation fails terribly, and I spend the next 2 hours hopelessly debugging my ~200 lines of code.

With around 30 minutes to go, I’m still stuck on 0-25-0, and I start to think that I’ll probably fail to debug shoes. So I move to attempting the subtasks on split. 7 points for the line graph case is immediate, and after a while, I find out that we can check whether or not there exists a subtree that’s “small enough” that the complement is big enough to hold a connected component of another size, but also “large enough” so that this subtree can itself hold a connected component of some size. It should be doable by DFS and storing subtree sizes, then the colouring is a matter of just making sure we colour a connected component and don’t mess up the number of nodes of each colour. Coded and passed samples… WA. Still 7. There has to be a bug somewhere in the colouring, but I couldn’t find it in time and finished with 0-25-7.

Post-contest analysis period : we’re allowed to look back on our code and submit some unofficial attempts. I fixed a compilation error and submitted for split.. nope, still 7. Also, it appears that at some time I attempted to code a brute force for ~10 points on rect, but I don’t ever remember coding it, nor did I submit it.. Hmm.

Overall, definitely not a good day, and coding speed is still my biggest problem doing CP.

MYS-4 (Ming Yean)’s perspective : I started by writing a quick brute force for subtask 1 of “Rectangles”. Surprisingly enough, subtask 5 was also free, there was probably another solution to it. After running out of ideas, I tried “Shoes”, since it seemed to be the easiest problem among the three. Subtask 1 was a little too easy, subtask 2 and 3 were just about trying out all permutations. I implemented a solution where I count inversions using merge sort, giving O(n log n) complexity, given that I know some optimal way to arrange the pairs. This solution got 65 points, which at the time I thought was quite high.

After solving subtask 4, I went on to the next problem, “Split”. Looking at subtask 3, the restriction to trees didn’t seem too hard, and if I could solve it, then I can easily adapt it to solve subtasks 1 and 2 as well. My idea was to run a DFS, for each edge, try to remove it and see if the remaining components have at least a certain size. After some debugging, I the got the 22 points, and just getting a spanning subtree via DFS and using the same code solves subtasks 1 and 2 as mentioned. For subtask 4, I tried getting a DFS tree starting at each vertex and running my previous code on that. I was not sure if this approach was correct, but it didn’t pass the time limit anyways.

At this point I had slightly over an hour left, so I looked at “Rectangles” again, because this was the problem I had the lowest score on at the time. I tried searching for some important quantities that may help with the problem, such as the index of the next largest element to the left or right, etc., and try to relate it to the problem, but it didn’t seem to work and I didn’t make much progress in that hour.

After the competition ended, I was kind of surprised that Kel Zin and Jia Jun got AC for “Shoes”. It only then that I was told that greedy was optimal. I was slightly disappointed that I did not notice this. As Wei Xin advised me, If you have no idea, just try something stupid – it might just work. It probably would have been wiser to spend the remaining time on “Split” instead.

Day 4 / Excursion Day 1 (August 7)

Its excursion day but we are quite tired for it (still recovering from yesterday’s competition). Just like usual, we woke up and had breakfast and went to recreation room to play with our phones. Then we got on to the bus and went to visit Icheri Sheher which was called the old city of Baku. The tour guide explained stuff to us and we took a lot of pictures.

After the tour, we went to have our lunch in Four Seasons Hotel. The hotel was so luxurious and we were told that the hotel was actually for VIP like politician from other countries. The interior design was perfect, the waiter also looked professional. Also, it was one of the team guide’s birthday and they celebrated while having lunch.

After lunch, we continued our tour to the carpet museum. The carpet museum in Baku was the first carpet museum in the world. The roof of the museum was literally a carpet. Inside, there were so many carpets and we were amazed by it.

Then, there was supposed to be a caspian boat trip. Unfortunately, it was cancelled due to strong winds. We just went back to Athele’s Village and rest. At night, the quarantine had started and we had to give our phone to our team guide. So, we got nothing left to do and wanted to return to our room. But Bakhtiyar suggested us to join their party and enjoy our time in Baku. We tried hard to convince him that we need to practice for tommorrow’s contest and finally he agreed to bring us back to our room. We practiced coding in our room and sleep at around 10 pm.

Day 5 / Contest Day 2 (August 8)

MYS-1 (Jia Jun)’s perspective : It’s the second day of the contest! Everyone gets up early and have breakfast. Each of us were both nervous and excited about the contest. Since all of us know how much points we are behind from the medal cut-off, we all knew we need to give our best in order to reach our targets. We went to the National Gymnastic Arena using the same route. We queue outside and pass the security check just like the Contest Day 1. We wish each other good luck and went to our seats preparing for the contest. “And the contest starts now…”, following the announcement is the sound of tearing through the envelope and keyboard clicks. All of us try our best to score points, but the problems are more challenging than Day 1. Five hours of intense coding has ended, everyone applaud, celebrating the end of a tiring contest. We went back to the seating area, having a brief talk and discussion about the contest problems, while enjoying our meal too. We have a group photo, and secretly snatch an IOI mousepad and a name card. After that, we went back to the Athletes’ Village, both mentally and physically worn out. We have our dinner and following that is the activity time, which is free time at the lounge. Then, we went back to our room to relax, and have a good night sleep afterwards.

MYS-2’s perspective : The tasks were Line , Vision , Walk.

There was some technical issue on Day 2. The contest then extended for 15 minutes. Learning from my previous mistakes, the first thing I do was to read every questions. My first impression for Line was no (Again wrong judgement). Vision was very creative and Walk was like some dp and shortest path. I attempted Vision first and got some trivial subtaks right. Then I looked back at Line and got 12 marks with brute force approach. I also attempted Line with a complicated dijkstra algorithm (takes me about 1 hour to implement it). Then I spent the rest of the time solving Vision. I was trying to get AC for Vision. In the end I only get 66 marks for Vision and that decided my fate to not get a medal.

After the competition, there was a slight hope in me to get bronze medal. But well I was 26 score away from the cut. I could have got 26 marks in Day 1’s Split or Day 2’s Line. Nevertheless, this was my first IOI and I hope that I could do better next time only if I manage to squeeze in the team for IOI 2020. Thanks to Zun Yan and Wei Xin for always supporting us. Also, thanks to Wei Xin for staying up late to proof check the translation by China team. I am very grateful and very much appreciate their effort in this IOI.

MYS-3’s perspective : Rainy day as we head to the National Gymnastics Arena (NGA) for the contest. There’s also very strong wind (as usual), and we make it into the contest hall safely. A technical problem delays the start of the contest for a while, and after it starts, some contestants had problems with downloaded files going to the root folder, apparently a configuration issue with the workstations. This is a problem since contestants don’t have permission to access the root folder and forcing it is a reason for disqualification. The organisers’ solution : reboot everyone’s computers after giving a 1-minute warning .-.

Other than that, the contest goes fine. Tasks today are line, vision and walk. The constraint where N+3 lines gets full marks for lines catches my interest, as does the fact that it is output-only partial scoring. A query to the PSC whether a full-mark solution is guaranteed to exist returns the reply “No comment”… okay. Still, the constraint N+3 looks very nice, and it made me believe that there has to be a nice solution wasting only 3 lines. 2N is easy to do, and will give a direct 12 points, but I’m convinced that there has to be a N+epsilon solution, given the constraints. I spend about an hour here drawing diagrams and attempting various strategies, but still don’t have one. The furthest I can get is observing that at least 1 line is wasted as we start from the origin, and also that “spiralling lines” are the most efficient when no point appears at the corner of the spiral (this will give c lines that pass through c points, but obviously, not all configurations of points will be so kind as to let you do the spiral). Moving on to vision for a while, hoping to clear my mind.

In vision : The case of a single row or a single column is easy, giving a fast 12 points. Subtask 6 where the top-left pixel is always black looks easy at first, since anything that’s distance K from a fixed point lies on some diagonal line through the rectangle. Doing OR on all these will show us whether any of these is indeed black (later on, we learn from Shih-Yu from Taiwan that this is a key idea in the solution). This is another 8 points. Then, I code a quick brute-force for subtasks 1 and 2, realising that it fails on 3. My algorithm is inserting too many instructions, doing a lot of separate OR’s when I could have just done a large single OR. Once I realise this, I optimise the brute-force and it passes subtask 3 but not 4. This gives another 32 points, and I now have 0-52-0. This is with about 3 hours left in the contest. After trying for another half hour and having no ideas, I go back to line.

It’s at this point that I realise, having a bunch of points such that any point which is higher is also to the right (so the points are all going up from left to right) is also very good, since we can then go through all the points, moving alternately right and up without wasting any lines, forming a staircase pattern. Clearly, this also works for going down from left to right… This triggers an idea. Since the spiral DOESN’T work only when there is a point in the corner of the spiral, what if I ignore that point and move further inward right away? This preserves the “c lines for c points”, but what about the left-over points? Idea : those points that were “popped” from the top-right and bottom-left corners of the spiral, can form a bunch of points that increase when going to the right; this is intuitively obvious. Then, those points “popped” from top-left and lower-right form a bunch of decreasing points. So we now have a group of points in the spiral, a group of points increasing from left to right, and a group of points decreasing from left to right.

Notice that all these three groups can satisfy “c lines for c points”, so the only lines we waste are when going from group to group… And we only do that 3 times. Origin to spiral, spiral to one staircase, one staircase to another. That’s N+3… Are we done? This looks too elegant not to be the solution, and I’m instantly convinced it is. Now for the bad part : again with the idea of how to solve the problem, I’m unable to debug my code properly, and two hours of repeatedly coding and debugging goes nowhere. In frustration, I code the brute-force 2N solution and submit it for 12 points in the final minutes, being unable to complete what I believed is a full solution for line. I never even touched walk, being too focused on vision and line.

At the end, I finish with 12-52-0. It’s better than yesterday, but not by much, and I still face the same problem as yesterday. Verifying with Zun Yuan, my solution for line apparently is the intended one, but I failed to code it and thus wasted a potential AC (note : random solution apparently gets ~50 points, and no one scored 100 for this problem). Overall, I’m disappointed with my performance at this IOI, especially since it’s my coding skill that let me down so badly.

MYS-4’s perspective : Compared to the first day the problems seemed more difficult. I started with problem “Line”, for subtask 1, I just joined the points in the obvious way. The solution requires n + 3 lines, so I should try to assign each point to exactly 1 line where possible. I didn’t figure out a good way to do this, but to save some segments, I randomized the order of points and tried to alternate horizontal and vertical for each point where possible. This wasn’t very effective and I ended up with only 26 points.

“Vision” was quite tricky to implement, since you also had to keep track of what each cell represents. Subtask 1 was just a brute force, with some optimizations I could solve up to subtask 3, but this approach would not scale well to the constraints. Subtasks 5 and 6 can be solved in essentially the same way. Subtask 6 sort of hinted at considering diagonals, I did not figure out the details at the time. For subtask 7, I considered combining cells of each row and column with an OR gate and process it that way, but I could not debug my solution.

In the final hour, I moved on to “Walk”. The graph was a little tedious to set up, but doable. Running Dijkstra’s algorithm on it would solve subtask 1. The implementation took longer than I expected, there was only around 10 minutes before the end when I submitted my solution to subtask 1. I was hoping it would pass subtask 2 as well, but apparently not. If I had more time I should have been able to optimize it, since subtask 2 didn’t seem too hard to pass.

During the analysis, I check my submission for “Walk” again. Apparently my submission only TLE’d on 1 test case. Although I didn’t expect it to pass, I didn’t expect it to fail only on a single test case either. Looking back on my scratch paper later, I found a couple of spirals that I had drawn for “Lines”. I heard that this approach would get around half the points, but I did not implement this.

Day 6 / Excursion Day 2 (August 9)

In the morning, we head to the Yanardag (literally “burning mountain”) reserve, where there is a natural gas fire that has been burning continuously for 60 years(!!).

The view at Yanardag is excellent, but the muddy ground spells trouble for all of our shoes (RIP Ming Yean’s white shoes). We get a few minutes here to take pictures and walk around, then we have to leave again, but not before getting interviewed by an Azerbaijani news network (?) about the IOI thus far. Next stop is an ethnographic reserve, where we get to see the history of Azerbaijan’s citizens and some of the preserved artifacts. The most interesting artifacts are a series of stones, on some of which are apparently carved scenes, but which look more like abstract art to us. There is also a stone of varying thickness which when struck with a smaller stone, becomes a musical instrument. Also, camels.

After this visit, we head to the Elite Events Hall at Elite Horse Club for a very fancy buffet lunch, then a very impressive horse show where various stunts are performed on horseback (or off horseback) with accompanying dancers in the middle of a field. It draws everyone’s attention for sure.

Later that evening, we have the Cultural Night. In the small square between the buildings housing all the IOI participants, a large stage along with many small standing tables are erected and the usual buffet dinner service is moved out here. Everyone stands and eats dinner while various performances are carried out in the general area of the stage. Initially, this is just dancing to random music, but as the sun goes down and the spotlights go on, the program of the night starts. It is at this point that the Malaysian team (read : Kel Zin), having been reserved a slot for performing, decides to go ahead and sing/dance. Suffice it to say, said performance was extremely entertaining, and the lead singer is praised by several friendly teams. No link to the video of the performance will be provided here, find Zun Yuan for that. The party goes on and on, with various countries bringing all sorts of performances. The Taiwanese team jokes that they will demonstrate to the world their collective excellence and mastery of… standing still. Highlights include a performance of Baby Shark, a massive human train and at the end, the entire stage turns into a disco floor, the music blasting on until midnight or perhaps later. We leave around 11pm to return to the room and sleep.

Day 7 / Closing Ceremony (August 10)

In the morning, we visited ADA University – one of the organizers of this year’s IOI, and the university our team guide was studying at, for a tour around their campus. We toured around their library, which according to them is one has the largest collection of English language books in Azerbaijan. After that we entered a new building intended CS and IT students, where we sat through a “Knowledge Fair” by Acer. They talked about their history and direction, their involvement in education, and showcased some of their products (e.g. gaming PCs and chairs).

There was another talk, somewhat of an introduction to game theory (prisoner’s dilemma), recent developments in artificial intelligence (Pluribus – some poker playing AI), touched on quantum computing, cryptocurrency, and all the usual stuff. During the Q&A session, the audience applauded as the speaker’s laptop’s battery had just died.

We had lunch back at Athletes’ Village, then we headed for Heydar Aliyev Center for our Closing Ceremony. The design of the building was very unique and modern, unlike any building we’ve seen before. Fortunately, we did not leave empty-handed, as Jia Jun won us a bronze medal. There they also launched a special edition IOI-themed stamp.

After the ceremony ended, we had a family photo outside the center, before having our dinner there. We opted out of the guided tour around the center. Instead, we went to Baku Boulevard to experience the night scene there, as previously we have only been there during the day.

We first went to the mall to buy some souvenirs, then headed down the boulevard. The scenery there was rather beautiful – the seaside, the lights, and of course the view of the iconic Flame Towers, which was lit by some animated lights. We walked along the boulevard down to Azneft Square, where we took a few moments to enjoy the view. We walked past Icharishahar station, Azerbaijan State University of Economics, Nizami Museum of Azerbaijan Literature, to name a few places. We went back to Athletes’ village via metro, by the time we reached it was already 11 pm.

Shortly after, we received our certificates of participation and went back to our room to pack our luggage.

Departure Day (August 11)

We got up early and had our last breakfast in Azerbaijan before leaving for the airport. Bakhtiyar sent us off at the airport, then we hung around the airport while waiting for the flight (but Zun Yuan had to wait till night). The return trip proceeded without incident, and everyone returned safely home on time.

It was a memorable IOI for all of us, and there are many people we have to thank. Thanks to our team leaders and guide for always helping to solve our issues while at the IOI, the organisers for making this very impressive event happen, MIPS for giving us the chance to represent Malaysia at this prestigious event, and last but not least, our parents, friends and teammates who supported us in many ways all through the journey.