The online round for the India’s ICPC was held on 23rd. And also a week before that. The first time around, the organisers tried debuting a self-hosted DOMjudge instance. That didn’t go too well, so a recontest was scheduled on CodeChef.

If you’re not too familiar with the Indian ICPC system — this online prelims is used to select teams that can participate in the offline regionals. From a single university, usually approx. 2 teams (for the top unis) or 1 (for almost all unis that aren’t in top-15) qualify.

As you could guess, it’s quite easy for good teams to miss a spot. Looking at the first contest’s rankings, teams from rank 2 to 100+ all had 4 solves. Owing to severe system issues in the first contest, the time penalties weren’t too reliable differentiators, leading to the recontest this Saturday.

In hindsight, we forgot to be grateful for the problemset and reliable testcases the first time. I’m sure everyone agrees that the basic requirements (ignoring all other stuff like problem quality, balance, …) from an online contest would be:

1. A functioning judge
2. Correct, validated testcases
3. Testcases sufficient enough to weed out obviously wrong solutions. (Notice the obviously: as we’ll soon see, the official solution shared by the contest admin isn’t even in polynomial time. Of course, it passes all cases with $$$N=3000$$$)
4. Problems that can’t be easily Googled or insta-GPTed.

The first contest lacked (1), while the re-contest failed at (2), (3), and (4).

However, the organisers seem to believe that the re-contest was a fair metric just because CodeChef didn’t break, so here’s a compilation of what went wrong. Maybe they re-evaluate their decisions, maybe they realise that we deserve better. Regardless, even as part of a team that qualifies for both regionals from either version of the prelims, the experience was too bad to pass as a standard for ICPC.

Disclaimer: This is just a list of issues that I sourced by talking to the handful of teams at my university. Since the official Telegram group was blocked by the organisers following the re-contest (with a final message requesting to ‘trust the process’), there wasn’t an avenue to discuss the details. Hopefully this blog becomes one, because I’m sure that I’ve just discovered a small subset of issues. Additionally, all submissions are still hidden so we can’t figure out any more issues by looking at accepted code.

The re-contest

It had 5 problems, available here.

4, for all practical purposes, since the first was a cakewalk (and insta-GPTable). And also easily Googleable, because it is the exact same as another CodeChef problem. Also, as will be a recurring theme here, the official solution is easily hacked. Just to point out the obvious, whenever this happens, it means that the in-contest testcases don’t account for this, because the solution written by the contest admin would agree with / be the model solution.

Now for the remaining problems.

Small Indices

Here’s a summary of (a subset of) what ACs for this problem. A reminder that $$$N=3000$$$.

• GPT writes an obvious $$$O(N^3)$$$ DP. Works.
• $$$O(N)$$$ greedy. Wrong, ofc. But works.
• $$$O(N)$$$ DP. Wrong, ofc. Also works.
• $$$O(2 ^ {\log^2 N}) \approx 2^{121}$$$ brute force, written by the contest admin, finalised as the official solution.

Let’s talk more about this last one.

This video shows the original problem had $$$N=10^5$$$, presumably with some incorrect model solution. The admin then ACed with a recursive brute-force, with the above non-polynomial complexity. They probably discussed this and realised that the earlier faster solution was wrong, and also (wrongly) agreed that the brute-force works in $$$O(N^2)$$$. So they reduced the problem constraints to intend $$$O(N^2)$$$ solutions to pass.

Somehow, the end result → neither does the model brute-force solution work in time, nor do the test-cases enforce any time complexity (given that the model solution was itself guilty of being the slowest).

To add to that, the solution is presented in a way that pretends that the complexity is obviously correct.

The claim basically is: ‘if the recursion depth is $$$N$$$ and any single chain branches off atmost $$$K$$$ times, the tree has atmost $$$N2^K$$$ nodes’. There is no attempt to justify this. In fact, it is not even stated anywhere explicitly. Just assumed. The video goes: ‘maybe there are not too many states, let’s try’. It passes their own bad testcases (remember, still for $$$N=10^5$$$), and it was thus finalised as a problem. I’m surprised that this was not a huge red flag for the setting team.

We quite easily hacked it, and Igen reported it in detail. The response? A band-aid of caching on top, and a prompt ‘can you now find a counter-case’? Come on :\ Can we now get an acknowledgement of how much was messed up in this problem? Can setters now admit that a contest needs a provably correct solution? (On a side-note, our team ACed with a DP with $$$N^2 \log N$$$ states. It seems correct to us, but given that the test-cases apparently let anything slide, our word is as good as anyone’s. Can detail our solution later if needed.)

Yet Another GCD Problem

Constraints mention $$$K \geq 1$$$. Testcases don’t agree with this :(

No clarification regarding this was made during the contest. Now in a 2.5h ICPC-style penalty contest… you get the idea of all that can go wrong due to this. In all the contests that I’ve heard or been a part of, the organising team monitors for any such obvious validator mess-ups that lead to failing submissions. They announce the issue ASAP (and fix it or call it off, depending on the severity). This didn’t happen here. This was addressed after being pointed out by participants in CF comments of the official editorial.

Equations

After the contest, we pasted the statement into ChatGPT. Without any prompting, it quickly wrote a DSU which maintains a bi-colouring with other required info. Great.

This is not surprising at all. All of our immedate reactions on reading this problem — why does this library-checker problem exist? Just a thin veil of ‘observation’ (which is itself very standard — make a graph when pairwise constraints on sum, XOR, or whatever). As is well known, LLMs excel at these.

Okay, maybe I should have been more careful while calling the ‘observations’ lacking. Because among the only novelties in the problem was realising the $$$w=0$$$ case, and it was apparently enough to mess up the testcases. The official solution gets hacked... again.

As a sidenote, I appreciate the commitment from the organisers to hold a re-contest after the judge broke. Unfortunately, even after the re-contest, it doesn’t look like we’re in a better situation. You don’t expect the most awaited annual competition [with guesstimated upwards of 3M INR collected just as registration fees, along with sponsorships and stuff] to be far worse then online contests held every week throughout the year on every OJ.

My submission to today's problem F apparently uses 0KB memory, and I was able to find a few other similar cases as well. Even if you ignore every other obvious factor, the submission stores atleast 4e5 integers, so nowhere near 0KB even if rounded off to a reasonable amount.

Probably a bug (or Kotlin sponsorship perks? :p) worth looking into.

Welcome to my first blog!

I recently came across problem E of Round #646, and solved it using an approach that didn't seem to be mentioned in the tags. And I felt it would be good idea to share it! Let's just jump straight into the solution.

I'll refer to nodes which are initially marked 1 and need to become 0 as of type $$$OZ$$$, and the nodes which need to change to 1 from 0 as of type $$$ZO$$$.

An intuitive idea that is guaranteed to work is to greedily select the node which has the lowest cost, and make all possible exchanges in its subtree first. So, we sort the nodes in a non-decreasing sequence of their costs, and process them in that order.

To achieve that, we need to efficiently query on the number of nodes of types $$$ZO$$$ and $$$OZ$$$ in a subtree, and update the counts every time we shuffle. We can use a Euler tour to flatten the tree down to an array. To keep track of the subtree of any node, we store the in and out times of each of the nodes during the DFS (say, in $$$tin$$$ and $$$tout$$$ respectively). The subtree of any node $$$P$$$ includes all the nodes $$$I$$$ such that $$$tin[I] >= tin[P]$$$ and $$$tout[I] <= tout[P]$$$.

We can maintain a two cumulative frequency arrays to count the number of nodes of both types $$$AZ$$$ and $$$ZO$$$ in any subtree. When we are processing any node $$$P$$$’s subtree, we count the number of nodes of both types. Let’s name them $$$C_{AZ}$$$ and $$$C_{ZO}$$$. The maximum number of exchanges we can make in this subtree is $$$k = min(C_{AZ}, C_{ZO})$$$, thereby incurring a cost of $$$2 * cost[P] * k$$$, which we add to the answer.

However, we need to update the counts when we perform any exchange. An important observation here is that if we process a node $$$P$$$ before $$$Q$$$ (if it had a lower cost), and $$$Q$$$ lies in the subtree of $$$P$$$, then we can just ignore $$$Q$$$ when we encounter it. This is because all the exchanges possible in its subtree have already been processed for a lower cost. How do we keep efficiently check if any node’s ancestor has already been processed before it? We create another Fenwick tree, and mark the segment of any subtree once we process it using range updates and point queries. In my implementation, this tree is named $$$color$$$.

This makes it very easy to now update the counts after each shuffle. We first convert our cumulative frequency arrays for storing counts of $$$OZ$$$ and $$$ZO$$$ to Fenwick trees. Next, once we perform an exchange of $$$k$$$ nodes in node $$$P$$$ ’s subtree, we add value $$$-k$$$ to both $$$ZO$$$ and $$$OZ$$$ on node $$$P$$$’s position in the Euler tour. This will work because if any segment of $$$P$$$’s subtree is queried for the count of $$$ZO$$$ or $$$OZ$$$ nodes, it will also include $$$P$$$ itself. Remember that we have ruled out nodes in the subtree of $$$P$$$ from our processing, so we won’t need the detailed information of exactly where or how the shuffling has occurred. If any node now cares about any segment of $$$P$$$’s subtree, it will also care about $$$P$$$, because it can only be an ancestor or $$$P$$$. The negative value added in $P$’s position will then prevent overcounting by negating the count of exchanges that have already occurred.

The complexity does get an additional coefficient of $$$log(n)$$$, but it performs pretty close the solution mentioned in the editorial, at least for the given constraints.

And that’s it! Here’s my implementation. Let me know if there’s anything I can improve, or if you have any doubts.