KadiyalaSaiManoj's blog

By KadiyalaSaiManoj, history, 8 years ago, In English

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.

  • Vote: I like it
  • -41
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

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

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.