Somehow, I managed to make the 2025 iteration of this thing, despite not planning for one last year. I wrote two problems this year. One has been on my mind since 2023, while the other one came up after Prabowo asked for additional problems for INC or ICPC Jakarta. As usual, I would talk about the problems as I remember them.

INC 2025 - Construct BFS Graph

Problem link: Here
Editorial: Same as above

I was hanging out with Prabowo at a friend's home when he said not many people have submitted to INC and ICPC Jakarta. To be fair, I thought it wasn't a problem since people tend to submit close to the deadline anyway. But since I had nothing better to do at that time (we were waiting for our friend to finish cooking), I tried to think of a simple problem. Well, a simple way to make a problem is to modify an existing problem. I remembered I wrote a counting problem related to BFS ordering (this), so let's go from there. What if instead of counting, we construct the corresponding graph? It took me a while, then I realized that the observation used in the original problem can be used to construct the graph whenever one exists. Basically, the greedy solution that simulates the BFS will work. Though now I feel concerned since solving the original problem really helps in solving this one. Anyway, I told the problem to Prabowo, and he said to just submit it. And well, this problem got accepted to INC.

I thought that this problem wasn't that hard, but surprisingly, only a few teams managed to solve it (scoreboard). Though, I suspect it's because of how the contest went (see the rant near the end of this post).

ICPC Jakarta 2025 - Count DFS Graph

Problem link: Here
Editorial: Same as above

Note: the story might be a bit controversial due to the use of AI in some parts of the problem development.

As I mentioned before, this has been on my mind since 2023. In fact, I was thinking about this before coming up with the Count BFS Graph. Since I noticed this problem has been gathering dust in my problem notes, I figured that this would be a good time to resolve it.

Though I still cannot solve it in a time complexity that I like. I kept getting stuck at exponential-time solution (something like $O(n^2 2^n)$ time). The idea is to do DP, where the state keeps track of the nodes that form the path in the DFS tree to the current path. Then, each time we insert a new node, we can insert it as a child of some node in the path, and since we track the path, we know the number of ways we can add the back edges. But since time is running out and I want to work on other stuff (say, my thesis), I decided to just submit this version. I am a bit okay with exponential-time solution since the current trend shows that, Indonesian contestants nowadays are not good with problems with exponential-time solution (e.g., DP with bitmask and DP with broken profile).

Not long after that, while taking a break, I thought it would be funny to let GPT try solving this problem. So I just put the problem to GPT, which gave a polynomial-time solution that looks cool, but wrong. Being bored, I gave a counter-example to its proposed solution, and told it to fix the solution. This goes on for quite some time. Until eventually, it gives me an $O(n^3)$ solution that correctly solved all the testcases I had given. This kinda surprises me, so I decided to look at its explanation.

Surprisingly, it makes sense. Rather than keeping track of the path, it uses the fact that a subtree corresponds to a subarray of the DFS visitation order. Then, rather than counting the number of back edges "upward", it counts the back edges "downward", by fixing the subtree. For the details, please check the editorial, but this eventually gives a solution with $O(n^3)$ time.

On one hand, I was amazed that AI can came up with a good solution. In particular, before this, I was always disappointed ever time I used AI (I guess this was due to my use case). On the other hand, I felt stupid since me from 5 years ago would have come up with this solution. Though this might have happened because I rarely do competitive programming nowadays.

So anyway, after that, I sent a follow-up email to the committee saying that there is a polynomial-time solution and AI can solve the problem, and I don't mind if they reject the problem. Knowing that the problem can be solved in polynomial time is already enough for me. In the end, this problem got accepted to ICPC Jakarta 2025.

Okay, that's all for the problems I wrote this year. Now, a bit of ranting about how INC went.

INC Rant

Context: INC (Indonesia National Contest) is the preliminary stage for Indonesian contestants before ICPC Jakarta. There are a lot of ways to qualify for ICPC Jakarta, but the most common way is through INC. Due to the scale, the contest is fully online.

People who were watching INC scoreboard during the contest would know that the final scoreboard removes lots of teams. Mostly due to cheating.

For me, the easiest sign to spot a cheater was problem L (here). Its difficulty is mainly from the techniques involved (FFT and primitive root), but beyond that, the problem is not that hard. It's mostly just a combination of advanced team notebook stuff. In some sense, this is a problem that's quite easy for AI. Note that, while I say it's not that hard, it will still take some time for humans to solve it. And, I dare say that for INC, only very few can solve this in under 30 minutes. Yet, when I peek at the scoreboard during the contest, a bunch of teams solved it in around 10 minutes. I am pretty confident that those teams must be cheating.

As a spectator, I felt a bit amused because this is like a "trap" for cheaters. However, I already know the expected difficulty for the problems (context: I tested the problemset). Meanwhile, for the contestants, they may think that the problem might be easy since some can solve it pretty fast. Hence, I guess now, for online contests like INC, the scoreboard is mostly useless. Which is kinda annoying, as making strategy from the scoreboard is an exciting aspect of ICPC contests. I don't participate in contests anymore, but this still piss me off. Can't have good things anymore, eh.

Now, on the first problem I talked about in this post. I don't think the problem is hard, and if you are preparing for ICPC Jakarta, then naturally, you would have practiced using past ICPC Jakarta problems. Hence, you would have come across the counting version of the problem, which observation hints a lot for this problem. However, given how "chaotic" and "useless" the scoreboard was, I suspect that not many teams tried this problem because they were looking at the greener side of the scoreboard, which was influenced by AI use.

Afterwords

Surprisingly, I still managed to pump out a few problems this year. Though they are mostly a rehash of my old problems or a leftover in my problem notes. Now, I only have one problem left in my notes. Hopefully, it will get out soon. So there might be Problems I wrote in 2026, but as usual, I am not actively trying to write a new problem.

Also, I am very happy with the author lineup in the INC and ICPC Jakarta this year. From skimming, it looks like most of the problem authors are on the younger side. I hope this will be the norm for the upcoming years.