A rant on contest rejudging and constraints

Hi. I would like to share my thoughts about the format of Leetcode contests from the perspective of a former contest tester and top Leetcoder (in fact, I would be ranked #1 in the world by rating now if not for the last biweekly contest being unrated.)

First, let's talk about rejudging solutions. I am of the strong belief that rejudging contest solutions is wrong. Why? Imagine passing your graduation exams, and a month after you graduate, you find out that your grades have been retroactively changed to a fail, and your diploma is rescinded. Perhaps this analogy is a little extreme, but my views are similar - it's unfair to mislead participants into thinking they have AC'd a problem, and 'betray' them later. It means that even once all problems have been solved in a contest, we are always left with a fear of 'what if my solution is rejudged later'? There's no way to know whether I should spend extra time doing additional constant optimisation just in case 100 extra cases are added to the problem and it now TLE's due to the sum of execution time across all testcases. Some additional things:

  • A problem's time limit being compared to sum of execution time across all testcases doesn't work well with rejudging. The majority of the time when my submisions are rejudged to TLE, it's not that my algorithm has a bad time complexity, it's that there are too many cases. Nearly always my program wouldn't fail on any individual case; it just fails now because the number of test cases has doubled, and all of these added cases were max-sized inputs. It's especially bad as the number of test cases is hidden (more on this later).
  • Sometimes cases are added to hack solutions which would WA on some testcases. There are definitely arguments for this approach, but again, I don't think this is the user's fault; it's the problem writer's fault, and the user shouldn't be punished. This is especially because we only find out after the contest whether our solution has failed - meaning that we don't have any opportunities to fix these bugs in our code, even if it's a very small typo which could've been easily fixed during contest time.
  • Sites like Codeforces have hacks integrated into their entire contest system. There's hacks during the competition, submissions which are hacked during the competition allow users to fix their code and resubmit, and more importantly, it's transparent what the process is. When I do a Codeforces round, I know that my submissions will be judged on system tests, so I know to take extra care testing my code. Here on Leetcode, it's a huge gamble whether a problem will even be rejudged; if I AC a problem, should I assume my code is correct, or should I spend extra time looking for bugs or constant optimising? Hacking just doesn't fit into the current Leetcode contest structure.

And now a special note about the recent Weekly Contest 383. I was asleep during this contest, so forgive me if I get any details wrong, but from my understanding, the constraints retroactively raised the word length from 10^5 to 10^6, submissions were rejudged, and the contest was rated. This is a HORRIBLE decision and I think no argument can justify it. As I've seen other users describe it, you can't promise a constraint to a user and break your promise afterwards. For example, solutions that create a static array of size 10^5 would now be rejudged as incorrect with out of bounds indexing under the new test data. There's absolutely no way for a user to know that they should've declared this array with size 10^6 and so it's completely unfair. This also sets a very dangerous precedent for the future. Say a problem has N = 10^5 and I implement a O(NlogN) solution. I no longer have the guarantee that the Leetcode staff can't change N to 10^6 and TLE my solution. I absolutely think the constraints should be reverted. My understanding is that O(N^2) solutions were attempted to be hacked under the original constraints, and no such hacking case could be found. So what? Just because the solution doesn't fit into your arbitrary ideal time complexity doesn't mean it should fail. Maybe the worst case input for N = 10^5 has an extremely good constant factor, or inbuilt string comparisons and slices are very fast, and so I should expect such solutions to pass. Solutions should pass based on their raw execution time on worst case inputs - not whatever arbitrary time complexity is decided by contest staff.

Now lets discuss constraints. A lot of the problems described are exacerbated by the 'sum of execution time' format combined with arbitrarily many test cases. If I have a O(N^2logN) solution with N = 10^3 (as in the last biweekly contest), how am I supposed to know whether this will AC or not? I'm pretty sure that no single input would individually TLE such a solution, but if I have 50 max-sized test cases retroactively added after the contest, then it probably will TLE. So it seems that whether something like this passes depends almost entirely on the number of test cases or the number of max-sized test cases. Another example? In Weekly Contest 377, I lost a lot of rating because the O(N^3) Floyd Warshall TLE'd with N = 100 (Note 100^3 = 10^6), while just two weeks ago in Biweekly 119, one intended solution had complexity O(2^N * N^3) floyd warshall with N = 10 (note 2^10 * 10^3 > 10^6). It's pretty clear to me that there's no real way to predict whether an solution will pass or not under the current format, as it's so dependent on the number of testcases.

Two years ago, Leetcode stated that they were planning to tell users the number of test cases and the sum of constraints over all test cases. This is perfect because we now have some confidence whether a solution will pass, even with the sum of execution times model. I can't understand why this hasn't been implemented yet; there's no change to the platform needed, just adding two additional constraints to the bottom of each problem. Perhaps it's because of testcases being added after contest, but again I think testcases shouldn't be added; or even if hacking cases must be added, limit the number of such test cases. (E.g. if the problem guarantees that there are at most 100 testcases, then set 90 testcases in the original contest, and add at most 10 hacking testcases).

There's definitely more issues with contests, but I think this is enough for now. From speaking to other top competitors, I can definitely say that the quirks of the system certainly deter many of us from competing. Mainly I want Leetcode to revert / unrate the last Weekly Contest and update / clarify their policies for the future. Hope to get a response from @Leetcode admins soon.

Comments (20)