AtCoder World Tour Finals 2026 in Japan was the main event of this week (
problems,
results, top 13 on the left,
commentary recording,
analysis). With the three last problems significantly harder than the first two, it all came down to choosing the hard problem that fits one's strengths the most, as there was only enough time for solving one hard problem, despite the round lasting a whopping 7 hours. Only tour1st managed to do this well, getting D accepted after 6 hours, which would be enough for the first place by itself. Congratulations on the win!
Let me highlight the easiest (puts the concept of "easy" into perspective, doesn't it?) problem of this round, problem A: you are given a tree on n vertices (n<=250000) where edges have weights. We now construct a new undirected complete graph on the same n vertices where edges have capacities: the capacity of the edge between two vertices is equal to the smallest edge weight on the path connecting those two vertices in the given tree. Finally, for each possible choice of source and sink we compute the maximum flow (=minimum cut) between them in that graph. What is the sum of all those flows, modulo 998244353?
The other important track at the AWTF was the human versus AI competition. While LLMs have previously outperformed the humans at the ICPC, and it happened almost a year ago, which is an eternity in terms of LLM development, some people, including myself and Riku (the admin of AtCoder and the problemsetter for the AWTF) were still hoping that humans can hold their own on AtCoder problems, which require much more problem solving and mathematical intuition. Well, it was now clearly demonstrated, under proper contest conditions (as opposed to solving the problems after the contest, which always raises the question of the editorials leaking into the model training data), that the LLMs can handle such problems very well, too. Well done to the OpenAI team!
I'm looking forward to discovering how this will transform the world of algorithmic programming competitions. Notwithstanding the obvious issue of cheating, I expect quite a few positives: creating and preparing problems should become more efficient now, and the same could happen with the learning/training process. What do you think will change the most?
Thanks for reading, and check back next week.
was hoping to see more of your opinions on this AI thing, but felt abruptly ended as if you feel bad discussing about it.
ReplyDeleteMaybe (or maybe not) his opinions were not "ideal" to say in a contest sponsored by OpenAI, I don't really know what he thinks (ofc), but depending on what he thinks, it would not be cool to say in that situation.
DeleteAnyways, I also would love to hear what he thinks about AI, the impact in cp, careers, etc
To be honest, on one side, I don't feel qualified to talk about general impact of AI, and on the other side, there are already way too many more qualified people doing that ;) On a high level, I expect that as with any new technology, there will be changes, but the society will adapt and be better off.
DeleteI would prefer to focus on discussing the impact of AI on the algorithmic programming competitions, as this is the area where I feel I can both meaningfully contribute and learn something directly useful.
What exactly do you mean by 'creating and preparing problems should become more efficient now, and the same could happen with the learning/training process'? Do you mean that creating problem sets for competition will be faster now since writers do not have to create super hard questions that AI possibly could not solve (since AI can already solve these super hard questions as we have seen from AWTF), or do you mean writers will use AI to generate problem sets?
ReplyDeleteFor a contest, you need to have good problem ideas. But I think most of the work is in the preparation phase of a contest: Preparing testcases, making sure the problem statements are good, and checking the strength of the testcases by thinking of intentionally wrong solutions. Another part could be writing validators, custom checkers for when multiple answers are possible, and so on. For many of these tasks, AI can help a lot already, to get from initial idea to fully ready contest problem. Also in my experience, but this may change with better models, coming up with interesting problems is a different skill from solving them, and AI is already good at solving them, but coming up with new problem ideas is a different challenge.
DeleteAs the other reply suggests, I meant that one could use LLMs to prepare reference solutions and test data faster - it used to take, I'd say, around 1-10 full working days per problem, and I could imagine at least a 2x improvement even with the current level of LLMs. Another aspect is that when coming up with new problem ideas, the LLMs can be useful to quickly estimate the difficulty, and whether the problem has appeared before.
DeleteBut I was also curious if you see less obvious ways how LLMs could help the community.
I see, thanks for clarifying that!
Delete