Блог пользователя KadiyalaSaiManoj

Автор KadiyalaSaiManoj, история, 8 лет назад, По-английски

In some of the problems i have done in codeforces, some algorithms which pass in c are not passing in python. As most of you know python is slower, but this should not be a problem, sometimes pypy2 is fast enough to pass the time limit, but pypy3 is still weak and is sometimes slower than python3 , so for users using python3 this is becoming a problem.

This can be solved by creating a list of factors for each language which you multiply to the time limit to make the python3 codes pass.

Eg: if time limit is 2 sec

LanguageFactorTime Limit
C/C++1.02 sec
java2.04 sec
python2/3/pypy34.08 sec
pypy22.04 sec

These factors are just my opinion and can be decided by the CF team, I am not asking for the exact time limits as above but just asking to consider language wise time limits.
What do you people think?

I think hackerrank uses extended time limits, do any other site use it?
Hackerrank time limits

Have anyone faced similar problems like this.

  • Проголосовать: нравится
  • -41
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

People giving DownVotes can give their reasons in the comments Below, Which will enable us to discuss the topic. Thank you.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why did you write Java here? It works almost as fast as cpp after JVM start.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think it's a good idea, at least with very small factors. Let's say x1.5 for Java and x2 for Python. I would like to hear disadvantages, maybe from someone from CF team. Slower judging? Too hard/dangerous to introduce this feature?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Yeah the factors can be decided , thats what i am saying.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +39 Проголосовать: не нравится

    Would you think it is a good idea to add such multiplier at World Finals as well?

    At Petrozavodsk it is funny to hear stories like "we implemented some trash, it wasn't fast enough to pass in required 4 seconds with C++, so we had to rewrite it in Java, because TL for Java was 6 seconds".

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится -10 Проголосовать: не нравится

      Can C++ and Java be that close? (Can they have almost equal running times?)

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится -9 Проголосовать: не нравится

      I thought (and still think) that the following is true in most of cases:

      The difference between [intended in Java] and [brute in C++] is smaller than the difference between [intended in C++] and [brute in Java]/1.5.

      I don't say multipliers are perfect but I think the situation would be often better with them.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Hackerearth and codechef have the perfect multipliers for each language. I think they are ideal

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

    As long as you deal with problems where fast and slow approaches in reference language (usually C++) are separated by 10x or 100x running time, this may be fine. However, most of the time, it is also fine then to just have a single time limit for all languages.

    When you live dangerously and create problems where the gap between fast and slow is closer to 4x or even 2x, it turns out that there is no single constant for comparing different languages. It is not true that "Python is 9.81x slower than C++ in all circumstances". Its I/O is X times slower than C++, its two-dimensional lists of integers are Y times slower than two-dimensional integer arrays in C++, its calculations modulo 232 are Z times slower, and so on. I'd guess the numbers are on the order of X ≈ 1, Y ≈ 100 and Z ≈ 10, but I won't bet on that without some testing. The general idea is that the spread between X, Y and Z (as well as maybe other things to compare) is huge.

    The same is true for Java, though of course the magnitude of numbers will be a lot smaller. But even if, say, X ≈ 1, Y ≈ 1.5 (for multidimensional arrays) and Z ≈ 1, we will have XP to XJ a lot different than YP to YJ. All this doesn't exactly help in choosing one universal constant and saying something like "Java is 1.133333 times slower than C++, and Python is 3.41519 times slower than Java".

    On the bright side, for each given problem, the part of X, Y, Z etc. in the total time is more or less known, so it could indeed be possible to set per-language time limits. Unfortunately, this would require additional effort by problem setters: in time-critical problems, they would have to write reference solutions in quite a few languages to ensure good time limits. It is generally agreed that this extra effort is usually not worth the gain.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      For sure I agree that in this topic we don't care about problems with slower solution being many times slower.

      My experience is small — limited to comparing times in maybe 10 problems, where running times were important and there were two identical solutions (one Java, one C++). Yeah, it's a very small sample. I don't remember a single time when Java was as fast as C++. I think each time Java was strictly slower and sometimes it was much slower. In all those cases multiplier would only help me (I was a setter or tester each time). I understand that there are no nice constant factors and still I say: often Java is slower so the situation would be better with multiplier bigger than 1. And I know it would be worse sometimes.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

There are not many people who are using Python (not as many as C++ and Java) and even less people use less popular (in competitive programming) languages like Ruby, PHP, etc. If you want to make fair individual time limits for each of these languages, you'd want to write solution in each of them, and it would require knowledge of each of these languages. And I'm sure that not many authors here know most of languages Codeforces support well enough to write solutions for complex problems in them. And even if they know, it still would be quite unreasonable, because like 90% of competitors use C++ and Java.

P.S. Sorry for really bad English, my lexicon sucks :c

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Has this been implemented yet? Faced a problem today and wasted my 1hour during live contest because of it !

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The issue remains even after 2 years have passes since this blog !

Read this : https://mirror.codeforces.com/blog/entry/61298

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I agree, it is frustrating to solve a problem correctly and to get TLE just because it's not written in C++.

What if it was allowed to use a JustInTime Compiler library like numba? A simple numba decorator would make Python code run much faster (comparable to C++). Numba accelerates Python running times without giving any unfair advantage in a competitive programming contest since the algorithms in the library are just compilers.

Since the spirit of competitive programming is to think of the appropriate algorithm for solving a problem, the language shouldn't be determinant. But sadly, we are often forced to stick to C++ in the end, not because it is "the best" language, but because online judge rules themselves (not just codeforces) encourage indirectly to do so by setting the same limit for compiled and interpreted languages and restricting JIT compilation libraries like numba.

It would be very nice if Codeforces takes into account any of our suggestions to allow Python users to participate fairly.