I have noticed that the time multiplier for PyPy 2 has been reduced to 2X recently (it was done during the contest MOSCWJ19 but was in fact not only for that contest, but for all contests to come). When and why was this decision taken (I understand it might have something to do with the previous long challenge question BINSTR having brute force solutions passed in PyPy due to a generous TL of 1.5 s)?
I think that even 2X for PyPy 2 is not good enough sometimes. Python is very slow with recursion and large 2D (or multidimensional) lists (same for PyPy), so much so that most of the PyPy solutions for problem TWOFL from June 2018 Long Challenge were running above 8s. My own solution to that problem ran in 10.81 s (gorre_morre’s solution ran in 14.14s and algmyr’s ran in 9.04 s). I know that those solutions might not have been the best and optimum ones (as there exist much faster PyPy solutions) but then having a 2X for PyPy in these kinds of problems would certainly be problematic (because then you don’t know if your solution is intended to pass but isn’t passing due to tight TL for PyPy or otherwise), especially if such problems happen to be in short contests.
I think a 3.5-4 X time multiplier should be good enough for most of the purposes (please note that I don’t the scaling of many other algorithms and methods like FFT and all so even this might be too slow?).
PS: I do understand that it is not possible to set a universal time multiplier that’d work for all problems all the time, that’s why I also want to know what do you guys think?
PS2: Asymptotically, these two solutions of mine Solution 1 (TLE) (during contest) and Solution 2 (AC) (after contest) are the same, yet one gets TLE while the other gets AC, whereas an equivalent of Solution 1 in C++ passes well under the TL (I know there is a very small optimization in Solution 2, but it seems unnecessary when an equivalent of Solution 1 in C++ passes well under the TL). This is what makes me think that 2X for PyPy 2 is not enough.
I’m glad PyPy’s multiplier has been reduced from the ridiculous x5 it seemed to have accidentally been left with. That was a brute-force coding loophole. 2x seems fair, even a little generous.
Asymptotically, these two solutions of mine Solution 1 (TLE) (during contest) and Solution 2 (AC) (after contest) are the same, yet one gets TLE while the other gets AC (I know there is a small optimization in Solution 2, but it seems unnecessary when an equivalent of Solution 1 in C++ passes well under the TL).
This is what made me think that 2X for PyPy 2 is not enough.
@vipin1407 yes - that seems OK most of the time. Certainly it was enough for me when I was using PyPy3 to optimize for a straight Python answer under the time limit for ANGLE - the time ratio between those was over 13 which makes a joke of only giving Python x5 and argues strongly against a large multiplier for PyPy (2)
This is a good change. The 5x time multiplier was just silly. Hackerrank does 1.5-2x multiplier for pypy/pypy3, so having something like a 2x multiplier seems pretty reasonable imo. Keep in mind that my solution (and probably others) is optimized only enough to clear the limit for the question at hand. I’m confident I could have lowered the time if I had needed to (or switched language).
About TWOFL, during the competition my first slow version of the code got under the timelimit, so I didn’t think more about that. Tried to do some optimizations now and pretty much the same code got AC under the new timelimit (also noticed that they’ve added 2 additional testcases after the competition).
About timelimits in general, I don’t really know what is right or wrong. I’m really not a fan of problems with timelimits made so that only C++ can be used to solve them. This I feel is my biggest gripe with sites like codeforces. They can even have super easy problems that just aren’t solveable in pypy because of tight timelimits (codeforces doesn’t have any multipliers). I really dislike having to helplessly optimize my pypy code because the problem was only meant to be solved in C++.
At the same time I understand that it really isn’t fair to give pypy a huge advantage, it is slower than C++ and that shouldn’t be changed by simply giving it a 5x multiplier.
However note that there are many times when pypy is noticeably slower than even 5x C++. Even with a factor of 5 some problems just aren’t viable to solve in pypy, especially most FFT problems. And with a multiplier of 2x pypy will feel noticeable slower than C++ and many times will not be viable to use. It makes me a bit sad that I will need to switch to using C++ in the future but I do understand that large multipliers can feel unfair.
So what multipliers should be used? I actually feel that 5x is a huge multiplier, and a multiplier of 2 might not be that bad. I used to compete a lot on hackerrank and they have 1.5x on pypy2 and 2x on pypy3. Even with those multipliers I felt that it was really balanced and most of the time I could compete with pypy, only having to use C++ on the most difficult problems.
I also think that 2X is not good enough. The right multiplier would be 1X, just like it is done at most of the serious competitions and contest platforms - including Codeforces, ICPC, GCJ, FHC, AtCoder, TopCoder etc. That multiplier things is among the reasons why CodeChef isn’t taken seriously by a lot of strong contestants.
Another point to consider is that part of the purpose (as I understand it) of CodeChef is to be educational. If there is a decent multiplier for Python or PyPy, say 5x, then this will incentivise people to write readable solutions in Python, which will ultimately be a benefit to everyone who can learn by these example programs.
If there is a low multiplier, say 2x or 1x, then that will tend to force people to write in C++, with special cases written out etc., which will result in less readable solutions.
I think about 3-4x is usually fair for PyPy, and maybe 10x for Python.