In recent years, IOI tasks have taken a different direction. Communication, interactive, and constructive tasks have become much more common. In some of these tasks, there is no fixed optimal answer to the problem. Instead, contestants receive points depending on how small or large a certain value is.
In this blog, I want to criticize this style of task from a few different angles and express my concern that it is starting to appear too often at IOI.
My first point is about the ideas behind the solutions.
I think the solutions to these tasks can be extremely creative, and this is certainly a good thing. There may be no clear or standard path toward solving the problem. Each contestant can come up with their own idea, implement it, and possibly receive a good score. This freedom can make such tasks very interesting.
However, I often feel that these solutions do not have enough depth.
You may try a somewhat random idea and suddenly receive a very good score. Or you may start with an ordinary solution, make a small modification that improves the answer by a factor of two, and immediately gain many more points. Constant-factor improvements can play a surprisingly large role.
Because of this, these tasks sometimes start to feel more like heuristic contests. Personally, I do not think this is a good direction for OI contests.
My second criticism is about subtasks and score distribution.
In many of these problems, your score depends on how much you manage to optimize your solution. The lack of depth I mentioned above becomes even more important here. Dividing some bound by two, or even making an $$$O(1)$$$ change to the code, may suddenly give you several dozen additional points.
Sometimes the subtasks almost seem to say: do more tedious work and receive more points.
In a standard batch problem, each subtask usually represents a meaningful special case of the original problem. By solving it, you may discover an important part of the structure or get closer to the main observation. Each subtask has its own intended meaning, and the progression toward the full solution feels more natural and reliable.
I am not against the existence of communication tasks. Some of them have very beautiful and creative ideas, and having an occasional task of this kind adds variety to the contest.
My concern is simply that they are being used too often.
At least from what I see, students are becoming less interested in sitting with a problem and thinking deeply until they discover its complete structure. Instead, they look for another small optimization and another few points. I feel that the old problem-solving mindset is slowly becoming less visible, and I miss it.
I would be interested to hear what others think. Do you also feel that IOI is using too many tasks of this style, or do you think this is a good direction for the competition?
I believe that these small improvement-driven problems fit the real software development more.
However I got IOI gold by doing some weird constant optimization and changing random seed, so I might be unqualified to say this.
How does changing random seed affect your score? Isn't current time or
random_devicethe most optimal seeding?I once solved a problem with a random heuristic and it wasn't working on one seed, I tried 2-3 random seeds and it finally worked on one :) , you cant do this with current time seed
It's a random seed, but that doesn't matter since IOI doesn't have hacks. It's equally likely for any seed to be optimal.
It didn't (at least meaningfully), he just keeps talking about it. I'm happy he got a gold medal.
I disagree. In my opinion, the only truly heuristic problem in this year's IOI was Magic City. No other problem awarded a significant number of points for trivial constant optimizations, and the subtasks required ideas or observations to obtain. The largest amount of points for an improvement of $$$1$$$ was a measly $$$3$$$ points (in Classroom Game).
agreed. The way I put it is, in the so called standard batch tasks, the score you get is based on the progress you make in solving steps towards full solution. But in the heuristic tasks, your score is often simply based on how much time you spend working on the task and trying different ideas. there is no step by step path that leads you to solving the complete problem.
I believe both types of tasks are valuable in the IOI. but the main difference is the strategy a contestant needs to take to get a good score in the contest overall. standard batch tasks encourage you to think deeply and take a risk on solving the problem and its subtasks. but in heuristic problems you have to take a whole different approach in the entire 5 hours of the contest.
2-3 non-batches in a single problemset is cool and should be approached, but 5 is just too much of an overkill
That, and Partition feels like something ripped straight off the IMO shortlist as well. That problem would work way better in the IMO rather than the IOI, I'd prefer solving algorithmic tasks in the IOI and mathy-stuffs in the IMO, instead of the other way around (every Cx in the IMO shortlist as of late can be seamlessly restated to transform into something in a Div1 round, while Partition is, again, straight up just an IMO problem now with log factors)
Thank you very much for your comments. I would like to share some of my personal thoughts here. These are entirely my own views and do not represent those of any other [H/I]SC members.
I am not a professional heuristic contestant, and I rarely participate in AHCs or other heuristic contests. I did take part in one round of the Huawei Challenge (and got a decent result), and I have coordinated a few more such contests at UCup, but I will be honest: I am not particularly a fan of heuristic contests.
That said, based on my problem-solving experience, I do not feel that most of the non-batch tasks in recent IOIs require a fundamentally heuristic style of problem solving.
Taking IOI 2026 as an example, when I was solving Ball Machine, Partition, and Classroom, I approached them in essentially the same way as I would approach traditional algorithmic tasks. For Partition, you certainly need some ideas and observations, but I do not find the process fundamentally different from solving a constructive problem. I wrote solutions for almost every subtask and for the key milestones in the scoring scheme, and I believe that most of these partial solutions require genuinely new approaches, rather than merely tweaking constants or making small optimizations.
The only task that feels somewhat heuristic to me is Magic City, but that comes more from the way we wanted to use scoring for tie-breaking than from the nature of the task itself. I love this task (thank you, Yoneda brothers!), and in fact the target construction is optimal on every test case. If we presented the same task by simply asking contestants to find the optimal solution, I believe we would agree that it is a traditional algorithmic task. Contestants could indeed gain some additional points through constant-factor optimizations or incremental improvements. However, reaching substantially higher scores required making real algorithmic progress: solving the even cases optimally, solving K ≤ 5 optimally, solving the odd cases within 14K, and eventually solving the odd cases optimally as well.
On the other hand, I agree with most of the comments about the ad-hoc and constructive-ness of the contest. You may know that SC received major objections to Tiling, and you may also have heard some of the stories surrounding Mosaic in IOI 24'. Based on my experience judging at Olympiads/UCup/ICPC contests, I have found that many genuinely original tasks tend to have a constructive flavor, especially for those easier ones. It is generally not easy to find a task that is original and interesting, stays within the syllabus, and at the same time offers intuitive and approachable subtasks. I would therefore really like to encourage more people to submit their tasks to the IOI. (I loved beechtree, as well as the other problems you have authored, and I really hope to see more great proposals (ideally easy) in future IOIs )
I mean, communication tasks being more commonplace ever since the beginning of the 2020s, as well as the other non-traditionals, certainly aren't a bad thing. While I don't think that IOI26's problemset is as interesting as, say, 2022s or 2023s, as well as certainly thinking that the difficulty balancing is a bit "off" (2023's lack of "easy" tasks being so notable that the ISC had to include M*saic in IOI24, and yet the Gold cutoff is only.....6pts lower than this year, which has 100 free points in the form of Tiling), it is a good "varied" problemset in the sense that there's no full-scores, but almost everything got AC-d by several contestants, some of which coming from "weaker" backgrounds, which is good.
(Loosely speaking, call the "Split-Index" of a task "the degree of which the high-scorers in a task is distributed over the final ranking" (named after IOI19's Split, which has 3G2S1B ACs). A higher Split-Index indicates an "approachable" problem, so to speak. The fact that
the 1st AC of Ball Machine got a super clutch HM
A majority of the high-scorers in Magic City didn't get a Gold
those kinds of things indicates that the tasks were generally approachable AND a good score in a single task doesn't automatically mean a high medal like back in, say, 2017, and the scope of the problemset is wide enough).
That being said, 3.5 constructives and 1.5 communications for a single problemset (I consider Ball Machine to be closer to a communication than an interactive) is just a little bit too much of an overkill for the poor contestants. IOI16, 22 and 23 are genuinely interesting gems despite not having much "gimmicky" factors, and there have been at least a dozen IOIs filled with "interesting" tasks before the first 2-step got introduced back in 2020, so I think a problemset with.....1-2 less "gimmicky" problems would be better for the contestants. For what it's worth, I think IOI26 should be seen as an "experimental" IOI a la 2010 moving forward — so an important step in figuring out what works and what doesn't, but should NOT be repeated again.
Either way, the general quality of a problemset is largely dependant on the problems that were proposed, which is bound to be highly voliate. As long as it's not a dumpster fire like 2017 thanks to a certain problem that shall not be named, I guess
Thank you for the explanation. Regarding the IOI 2026 tasks:
Partition: Although it was a communication task, its problem-solving style was fairly standard, and overall it felt like a classical task. This task is not really included in my criticism.
Magic City: I like both the task and its main idea. However, the fact that improving your solution by almost any constant factor gives you a better score is exactly in line with my criticism.
Classroom: It has many different parameters, so during the contest, you hardly get the opportunity to explore any one direction deeply. At the same time, you can earn many subtasks by doing a large amount of implementation.
Ball Machine: I generally like the setting of the task. However, once again, almost every small improvement to your solution can give you a higher score. Of course, the scoring scheme contains several meaningful jumps, which helps mitigate this issue, but I still think the criticism applies to some extent.
Overall, I found the tasks interesting. However, I would say that three of them had the kind of scoring I was referring to: if your solution achieves a better constant factor, you receive a better score. Also, by “heuristic,” I did not mean heuristic problem solving in the strict technical sense. I used the word somewhat figuratively, because this style of scoring gives me a similar vibe.
I had a few thoughts to share:
After all, I think the setters did pretty well regarding the subtasks and partials for the 6 selected tasks. And for me personally, I liked the problems overall.
I think the contest was balanced for top contestants. But for <= silvers, the score distribution wasn't good.
I appreciate you for writing about this topic. I very much had this kind of feeling in my mind, and you gave me an opportunity to reflect about this. I wrote a long response to this for the entire day which I turned into a separate blogpost: link
I do think that the communication and interactive problems are what make IOI a remarkable contest, but I couldn’t agree more about the "optimization" thing. Basically, one spends more time on trying to optimize a solution by some constant factor instead of coming up with clever observations.
Also, I think it is noteworthy that IOI problems lack algorithmic depth. Most of the recent problem solutions can be explained to someone not that familiar with algorithms and data structures.
I think the usage of advanced algorithms should be encouraged while also keeping the communicative aspect of the contest.
btw, Multo_Tiko orz
thank you, god bless brother