IOI 2025, Sucre, Bolivia - 3 Bronze 1 Gold!

After reading through the problems, I tackled problem 2, Triples, first. I figured out that there were 6 cases, one for each permutation of distances. I implemented 5 of these cases in $O(n \log n)$, with the remaining case needing quadratic time. After some debugging, this earned me 34 points, including the subtask where $N \le 50,000$, even though that shouldn’t have been able to pass in quadratic time. Removing the quadratic case, I gained 11 more points from subtask 4. I would get subtask 2, worth only 6 points, later.

I moved on to problem 3, World Map. Using a tour of the vertices, I divided the grid into vertical strips of length 3, getting a basic $R=6$ solution, giving 58 points for what I felt was for free.

I finally decided to get some points on problem 1, Souvenirs. When I first read the problem, I thought that you would get as many copies of a souvenir as possible, which would be impossible to solve. Re-reading the problem, I found that each transaction could actually only give at most one souvenir of each type. I skipped the subtasks, as they felt too easy. I made the observation that querying the average price of a group of souvenirs would never yield the highest priced souvenir, but would get one relatively low-indexed souvenir. This would get me an AC. I implemented my solution, modifying the grader to log the transactions, and submitted my solution, which immediately passed.

After solving problem 1, I had over 200 points. I wondered if I could surpass 250 points on the first day alone. I spent some time on the output only section on Problem 2, earning 8.8 points using beam search and simulated annealing.

I returned to problem 3, optimising my solution slightly, to $R=4$, though I expected it to have $R=5$ instead, so I didn’t submit it. I then explored the idea of using nested L shapes, where only one of the sides needed to be of width 3, increasing each dimension by 2 on average. Submitting my solution, I did not expect to get 86 points, my solution attaining $R=3$, instead of the 72 I had intended to get.

In the remaining time, I was unable to get any more points on Problem 2, but I implemented the 6 point subtask on problem 2, submitting my solution only 12 minutes before the contest ended.

My score for Day 1 was 100 - 59.8 - 86, a total of 245.8 points, putting me at 18th place overall, and 13 points above the gold medal cutoff for the day. I suspected that my performance for Day 1 was because all the problems were ad hoc, just like the APIO this year.

I had changed my strategy slightly compared to last year, and decided to spend 40 to 50 minutes per problem in sequential order so I wouldn’t miss any extremely easy ideas due to overcommitting on one problem. Working down the problems in the order they were listed, I wrote down as many observations as I could make and grabbed the easy subtasks. On problem 1 (souvenirs), I managed to grab 39 points with some simple casework. I had a few ideas that could potentially lead to a full solution, but at that time 50 minutes had passed so I proceeded to problem 2.

There was an obvious $O(N^3)$ brute force solution to p2 by simply iterating over every triplet. Not long after, I figured that if we fixed the leftmost and rightmost element of the triplet, there can only be $O(1)$ amount of candidates for the middle element, giving an $O(n^2)$ solution. I implemented this within 10 minutes, giving me 18 points. I also knew how to do subtask 2, but I put off the implementation as it was only worth 6 points. I then turned to the output only section of the problem, which was worth 30 points. I failed to find a construction after a while, so I wrote a simulated annealing solution giving me 7.86 points. At that point, 1 hour and 40 minutes had passed, so I moved on to p3.

First of all, I noticed that the problem never mentioned that the graph was connected, yet there was an $M = N-1$ subtask. I spent 5 minutes proving that the graph must be connected, then worked down the special case subtasks (the graph is a path, the graph is a tree, the graph is complete). I quickly figured out an Euler tour solution for the tree case, but I did not implement it yet as solving the general case (even with an inefficient solution) instantly yields 58 points, including all the special case subtasks. I figured that I could extend my solution for the tree case into the graph case in about 5 minutes. First, I implemented the tree case solution to verify my idea, giving me 15 points. I took another 13 minutes to implement my general solution, which was worth 72 points. At this point, half the contest time had elapsed, and unbeknownst to me at the time, I was above the gold cutoff.

For the second half of the contest, my strategy was to work on the subtasks/full solutions that seemed the most doable. Since I had a few unfinished ideas from p1 earlier, I decided to revisit them and see if they got anywhere. I implemented a solution to the second last subtask that seemed correct and realised it got WA on my hand written test case. I realised the solution was completely wrong, and after a few more failed ideas, I gave up and turned to p2. I quickly finished off the 6 point subtask from p2 in 2 minutes by modifying my $O(N^2)$ solution. Subtask 4 hinted at doing some casework based on the relative ordering of the elements of the triplets, so I began systematically figuring out each of the cases. There were 6 cases in total, and I had already figured out the $O(N)$ solution to 4 of them while solving the early subtasks. After about 10 minutes of thinking, I managed to come up with a solution to the 5th case, giving me the illusion that I was really close to a full solution. The 6th case seemed perfectly symmetrical to the 5th case, so I spent 30 minutes trying to find the symmetry. I then wrote out a few equations representing the cases, and I realised the 6th case was special because there was no overlap in variables. I spent another 30 minutes drowning in algebra, desperately trying to find an invariant that would result in an $O(N)$ solution (turns out I was constantly trying to run through a brick wall, since the number of solutions to the last case was bounded by $O(N \sqrt{N}))$. I quickly ran a few more runs of simulated annealing, modifying various parameters, increasing my score by about 2 more points.

Since only 50 minutes of contest time remained, I decided to go back to p3 and p1 to ensure that I didn’t miss any easy ideas. I spent 10 minutes on each problem, making no significant progress. I did think of rotating the square 45 degrees for p3 (which was the solution to 86 points!), but due to time pressure and p2 constantly on the back of my mind, I did not figure out the details, and concluded that rotating the square would not result in a better solution.

I ran my simulated annealing code for p2 a few more times, but no better solutions were generated. I spent 15 more minutes thinking of the full solution to p2, and finally, in the last 7 minutes of the contest, I decided to implement a solution that would probably TLE but maybe pass the $N \le 50000$ subtask as a last resort. I made two submissions, but both had bugs due to double counting. I ended the day with a score of $39+45.14+72=156.14$, feeling quite disappointed as I couldn’t make any significant progress for the second half of the contest. I finished day 1 in 115th place, in mid-high bronze.

During the analysis session, I talked to a member of the Thai team, and found we had really similar scores and experiences (both of us gained no points in the second half). I got comical reactions from him and Jerome from the Filipino team when I explained the 86 point solution to p3, which seemed extremely obvious once mentioned. I also learnt from them that a lot of $O(N^2)$ solutions passed the $N \le 50000$ subtask for p2, which made me regret not coding my last resort solution sooner.

Before the contest started, I was very nervous since it was my first time at an International Olympiad. Once the contest started, I read through all the problems statements and started with problem 2 where I solved 2 of the easy subtasks worth 18 points with an $O(N^2)$ solution and tried the output only section but I didn’t find any construction so I just used beam search, which got me 8.21 points.

I moved on to problem 1 where I did the easy subtasks which got me 39 points. I made the observation that the average price of a group of souvenirs is less than the most expensive souvenir in the group but I didn’t think it’d work since it would skip souvenirs which are more expensive than the average price but less expensive than the most expensive souvenir.

I then moved on to problem 3, where I did subtasks 1, 3 and 4 which got me 20 points. I returned to problem 2 and ran my beam search code again but it only got me 1.15 more points so I returned to problem 3 and solved subtask 2 worth 10 points by making a world map that looks like the tree and I only realised later in the contest that this was equivalent to an Euler tour which I could have implemented much faster.

I returned again to problem 2 to solve subtask 2 worth 6 points and ran my beam search code again which got me 0.16 more points.

I returned to problem 3, where I thought of an R=4 solution worth 72 points which involved modifying my solution to subtask 2 but because of my bad implementation for subtask 2, it took me a long time to debug and by the time I had finished debugging, I only had half an hour left.

I then solved subtask 4 for problem 2 worth 11 points, which was also an easy subtask. After this, I only had 7 minutes left so I just ran my beam search code again but didn’t get any more points.

I ended the day with $39+44.52+72=155.52$ points, putting me in 118th place and 15 points above the bronze cutoff which I was quite happy with. I think I should have spent less time on the output only section of problem 2 since it was only worth 30 points and I got 9.52 points from it.

To start, I focused on problem 1 of the contest day, Festival. I started implementing a 27 point $O(n^3)$ DP solution, sorting each type of coupon in increasing order of price. However, when I submitted my program, it was already 50 minutes into the contest. I read problems 2 and 3, problem 3 seeming to be easy enough to get all but the final subtask. I used DSU and segment tree, eventually getting my 83 points halfway through the contest.

I went back to problem 1, observing that for subtask 6, you can buy very few coupons not of type 1 without running out of tokens. I modified my subtask 4 solution to work with subtask 6, and got 16 more points.

This late into the contest, I had to make sure I kept up my score, so I moved to problem 2, unable to think of any solution for the main subtask, so I did subtask 1, gaining 30 more points.

For the rest of the contest, I tried to claim the remaining subtasks of problem 1. Using a few equations, I observed that there was an order for which coupons to buy. I only realised much later that this order was the fixed point of the number of tokens for each coupon, such that buying it would not change the number of tokens you had. Hoping I would AC, I instead just solved subtask 6, 12 minutes before the end of the contest. Remembering that my DP solution could stop after any number of coupons not of type 1, type 1s always being the last, I copy and pasted the section of code in, submitting it with only 3 minutes left. I refreshed the page, the timer ticking down, until I saw my score increase by 12, my submission passing subtask 3.

My score for day 2 was 82 - 30 - 83, or 195 points. My overall score was 440.8 points, placing me at rank 27, within the gold medal range by only 4 points and 2 places. I feared that I would lose my medal, just like in 2022, but Shao Qian assured me that I was safe. It turned out that I was very close to losing my gold medal, my last submission 3 minutes before the end of the contest boosting me from 29th to 27th place.

During the closing ceremony, I would learn that Heng Liao, the gold medallist exactly on the cutoff, also barely made it to gold, gaining 12 points slightly earlier than me, This in turn pushed me into 29th place, leading to my gold medal clutch.

Knowing that I was 25 points below the silver cutoff for day 1, I decided to take a risk for day 2’s strategy by spending most of my time on the communication problem which I expect to perform better on than the batch problems, maximising my chance to end up with a silver. Even if this strategy failed, I would still be able to secure a bronze by grabbing subtasks.

Since the first problem was a batch problem, I decided to spend 50 minutes on it as per my usual strategy. I grabbed the 24 point greedy subtask within 30 minutes, then started thinking of some simple greedy strategies that could potentially work for an AC/partial solution. I spent 20 minutes implementing and submitting them, but all of them got WA.

The second problem was a really fun communication problem, and it was clearly a problem that I could do well on. I first spent 30 minutes thinking of and implementing the solution for subtask 1, giving me 30 points. Soon after, I found that extending the solution to subtask 1 works for subtask 2 as well, and spent 30 minutes planning out a three-phase solution using ternary and binary encoding, worth 77 points. However, there was an overwhelming amount of implementation and casework going into this solution, and having to pay attention to so many details caused me to get WA 11 times over the next hour. In the process, I had to generate many different test cases that broke my code, as it was impossible to test the complicated casework covered in my code with a single test case. Since there were less than 2 hours remaining in the contest, I decided to put the problem off and grab some subtasks on problem 3.

I quickly identified 3 doable subtasks for problem 3, gaining 23 points by constructing the graph and doing a bfs, then another 14 points using a prefix sum. This took a total of 20 minutes. I spent 10 more minutes on the problem making no useful observations, so I went back to debugging my code for problem 2.

After 10 more minutes of debugging, I found a test case which I mistakenly thought that my solution couldn’t solve at all (turns out I just didn’t handle the casework properly and I fixed the bug within 10 minutes of the analysis session). I found a quick fix by converting to full binary encoding, a solution worth 72 points which I implemented in 20 minutes by modifying my initial code. I was surprised that a much simpler solution like this one with significantly less casework was worth so many points, and realised I shouldn’t have time sinked on a much more complex solution.

For the last 20 minutes of the contest, I tried to hopefully grab a subtask or two on p1. I quickly realised that an exchange argument could be probably used, but I somehow didn’t think of simply writing a comparator (solving the N=2 case) and sorting for an easy 27 points for the subtask where the answer is a permutation. Reading the condition for subtask 6, I also quickly realised by working on some cases by hand that there can only be at most $\log(\max A)$ decreases in $A$ before it reaches 0. Despite making all the observations required for the full solution, I didn’t have enough time to implement anything, and I also did not realise DP could be used to grab subtask 4 as well as the AC solution.

I ended day 2 with a score of $24+72.89+37$, totalling to 133.89 points. I knew I would place quite low for this contest day as problem 1 wasn’t too hard, and there are relatively simple solutions for above 60 points on problem 2. I should have analysed the scoring function for problem 2 more carefully before implementing my best solution, as that would’ve saved me a lot of time. Thankfully, I was able to secure a bronze medal overall.

Before the start of the contest, I was again nervous because I wanted to get at least a bronze medal. I started with problem 3, where I implemented a simple $O(MN)$ solution using DSU to solve subtasks 1 and 3 which got me 23 points.

I then moved on to problem 2, but I didn’t realise that subtask 1 had partial scoring so I submitted a solution which I thought would get 30 points but only got me 10 points.

I moved on to problem 1, where I did the first 3 subtasks which got me 24 points and should have been easy but I took a long time to debug because I forgot about overflow errors.

I moved back to problem 3 to solve subtask 2 using DSU which got me 14 more points.

I then returned to problem 2, where I noticed that I could just not send any messages until near the very end and then just send the answer in binary which got me the 30 points which I had expected earlier. I realised that this would also work for subtask 2, just by sending the 2 nodes in binary one after the other, and after implementing, it got me 72.89 points. I then noticed that when sending the first node I could use quaternary instead of binary which got me 6.22 more points.

I returned to problem 1, where I implemented an $O(N^4)$ solution for subtask 4 using DP which got me 15 more points. I then tried some greedy solutions for subtask 5 but they didn’t work.

I then spent a lot of time thinking of a solution to subtask 5 or 6 for problem 1 but I couldn’t think of any so I moved back to problem 2 and added some randomness to my solution, since sending 0 doesn’t count as a message, which got me 1.06 more points. I spent the rest of my time thinking of a solution to subtask 5 or 6 for problem 1 but I couldn’t think of any and while I was thinking, I was also repeatedly submitting my RNG solution for problem 2 which got me 2.28 more points.

I ended the contest with $39+44.52+72+39+82.45+37=313.97$ points over both days which put me in 106th place, in high bronze, 24.04 points below the silver cutoff. Later when I heard the solution for problem 1 subtask 5 worth 27 points, I thought it was very obvious and was frustrated that I didn’t find it during the contest since it would have put me just above the silver cutoff. Overall, I was happy since I didn’t expect to be anywhere near silver.