shiven's blog

A summary of what passes for an Indian ICPC Contest, apparently
By shiven, history, 4 hours ago, In English

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.

  • Vote: I like it
  • +232
  • Vote: I do not like it

»
2 hours ago, # |
  Vote: I like it +12 Vote: I do not like it

Is your n^2 logn dp based on there being 20 Fibonacci numbers under 6000?

→ Reply
»
2 hours ago, # |
  Vote: I like it +32 Vote: I do not like it

I really want whatever the problem setters are smoking.

→ Reply
»
2 hours ago, # |
← Rev. 2   Vote: I like it -44 Vote: I do not like it

I understand but you have to understand doing a recontest in a week was a very big challenge.

→ Reply
  • »
    »
    2 hours ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    what does your argument justify? Okay recontest in a week was tough, so mistakes could be there, but what is the significance of you pulling his leg, related to AIR 1?

    → Reply
    • »
      »
      »
      108 minutes ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      I am not trying to demean him. I am just saying that I understand he is disappointed. However, he has to understand that they tried to organize a recontest within a week, which could have been better but didn't go perfectly well. I am sure there must have been some reason why they didn’t delay it. Unfortunately, nothing can be done about it now.

      → Reply
      • »
        »
        »
        »
        99 minutes ago, # ^ |
          Vote: I like it +19 Vote: I do not like it
        1. He is not disappointed, he is still going to both the regionals he signed up for (read the blog).
        2. You say that Nothing can be done now. This situation would not have happened if it weren't for gross negligence.
        3. Things can always be done, but that conversation needs to start in the first place. The blog serves as a means for the community to talk about this.
        → Reply
  • »
    »
    117 minutes ago, # ^ |
    ← Rev. 2   Vote: I like it +28 Vote: I do not like it

    Unless they proposed the statements in a week, it is more than enough to:

    1. Prepare strong testcases
    2. Validate the testcases
    3. Check if the problems can be ACed using GPT

    Given the funds ICPC Prelims have from the registration, these are the very basic requirements.

    → Reply
  • »
    »
    112 minutes ago, # ^ |
    ← Rev. 2   Vote: I like it +18 Vote: I do not like it

    The decision to conduct a recontest was in the hands of the problemsetting team. It is a hard task, but it is also something that thousands of teams care about — and have paid good money for. Many teams have put in well over a year of consistent effort to do well in the online round.

    The contest's fairness is not a "good-to-have", and it is the problemsetting team's responsibility to conduct the online round properly. If it was not feasible to do a contest in a week, they should have taken more time to verify everything. Negligence is not okay.

    → Reply
»
2 hours ago, # |
  Vote: I like it +37 Vote: I do not like it

and because of this, i can see a lot of cheater teams, comprising of atmax specialists in top 100. and vice versa have seen all CM teams failing to qualify, I don't mean ki high rated should qualify, but this much gap in ratings and not qualifying is very suspicious.

This is just going to decrease the quality of teams reaching regionals, and nothing else.

→ Reply
»
2 hours ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

I believe everyone is still trying to make sense out of the problem Small Indices, if you could take some time for the sake of it, please write an editorial that clears out this problem once and for all addressing why caching works (if it does) for the $$$N^{3}$$$ dp and stating the correct $$$O(N^{2} \log N)$$$ approach. Thanks in advance!

→ Reply
  • »
    »
    2 hours ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    Let dp[i][j] be a tuple (number of maximum small indices of subarray from [1 .. i], maximum element in [1...i], second maximum element in [1..i]). Now from dp[i][j] you have some cases on how large/small A[i+1], B[i+1] are compared to largest, second largest elements in [1..i](stored in the tuple dp[i][j]). Accounting all the transitions gives you a N^2 solution.

    → Reply
  • »
    »
    99 minutes ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    An $$$O(n^2)$$$ solution, that is correct, exists. We just need to maintain for each sum

    1. The number of smaller indices encountered so far.
    2. The largest element corresponding to that sum, and number of indices.

    Now, Why would a sum not prefer fewer smaller indices with a larger element?

    Consider the following scenario:
    Let $$$ a + b = c + d $$$, where $$$ c > a \geq b > d$$$.

    Given

    1. $$$a + b = { ( \text{mx}, a })$$$
    2. $$$c + d = {( \text{mx} - 1, c})$$$

    You can achieve a greater sum by forming $$$(c + a)$$$ or $$$(c + b)$$$, which will include at least $$$(\text{mx} - 1)$$$ smaller numbers. This, in turn, is better than $$$(\text{mx} - 1, c)$$$ with the sum $$$(c + d)$$$.

    → Reply
    • »
      »
      »
      69 minutes ago, # ^ |
      ← Rev. 3   Vote: I like it +15 Vote: I do not like it

      Edit: don't read this shit

      Idk if this is the same as what you have done, but I also had an $$$O(n^2)$$$ soln which I am pretty sure is correct:

      Let $$$dp[i][p][x]$$$ be the maximum number of good indices we can have in the prefix of length $$$i$$$, if:

      1. We set $$$c_i = a_i$$$ if $$$p = 0$$$ and $$$c_i = b_i$$$ otherwise.
      2. Position $$$i$$$ is a prefix maximum in $$$c$$$.
      3. The last prefix maximum had value $$$x$$$.

      Transitions are trivial. I have stress tested it, just to be sure, and you can do so too if you wish:

      Code
      → Reply
      • »
        »
        »
        »
        48 minutes ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Here is a testcase from the editorial blog, ans should be 7, you're giving 6.

        1
10
1 1 5 5 5 11 17 1 1 1
1 1 2 7 5 11 17 1 1 1
        → Reply
        • »
          »
          »
          »
          »
          30 minutes ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          There was a stupid (?) bug (?)

          Corrected code

          Edit: Actually, on second thought, I am pretty sure my solution is incorrect. Stress-testing doesn't seem to be helpful here though.

          Edit 2:

          1
10
9 5 6 3 2 19 19 16 19 15 
8 2 5 7 16 5 18 14 3 7

          :clown:

          → Reply
    • »
      »
      »
      69 minutes ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      During the contest, we did come up with a similar idea but dismissed it quickly, assuming a simpler one existed due to the high number of accepted submissions. Unfortunately, this decision led to us not solving the problem. Looking back, it would have been wiser to proceed with this approach regardless.

      → Reply
»
2 hours ago, # |
  Vote: I like it +10 Vote: I do not like it

I fr need that drug these people smoking!

→ Reply
»
2 hours ago, # |
  Vote: I like it +48 Vote: I do not like it

also why not conduct separate prelims for every site? good teams won't be bothered as much by the stupid preparation of one contest if they get another chance. we are anyways paying for all the sites separately.

→ Reply
»
2 hours ago, # |
← Rev. 2   Vote: I like it +36 Vote: I do not like it

Just to mention, every team paid 2200 INR (assuming they participated for two regionals, 1100 if one) for this "ICPC prelims". I could have used it to buy whatever they were high on.

→ Reply
»
119 minutes ago, # |
  Vote: I like it +45 Vote: I do not like it

Update: They muted the telegram group, after someone shared this blog there.

→ Reply
»
117 minutes ago, # |
  Vote: I like it +33 Vote: I do not like it

Gym contest problems with their statements altered are less GPTable than these "original" problems

→ Reply
»
97 minutes ago, # |
← Rev. 5   Vote: I like it +37 Vote: I do not like it

I don't think people realize how bad the situation with small indices is, there were over 200 solves on the problem, ignoring the obviously wrong greedy and $$$O(N^3)$$$ solutions, Most of the teams that didn't use these sols, Used a $$$O(N^2)$$$ one. I have looked at 2 solutions of 2 top 15 teams and multiple others from higher teams that are $$$O(N^2)$$$ and found an edgecase for all of them, currently there is only one $$$O(N^2)$$$ sol that i have found to be correct with a rough proof. We were rank 3 and used an $$$O(N^2log)$$$ sol ourselves, i bet if they open the submissions and people tried to look for edgecases, then there would be very less teams that actually solved the problem.

Edit: the correct $$$O(N^2)$$$ sol i mentioned has been mentioned here.

→ Reply
»
39 minutes ago, # |
  Vote: I like it +3 Vote: I do not like it

Ideally, there should be a re-contest again.

→ Reply
»
33 minutes ago, # |
  Vote: I like it +3 Vote: I do not like it

And they think rejudging the submissions will solve all the issues as mentioned here

→ Reply