isn't the time limit too tight for non-C program ?

I’m a Java programmer. I have been practicing questions from the archived problems page (EASY) from top.

I feel that I got TLE for almost 30% of the questions, EVEN THOUGH I implemented a solution that has the same asymptotic bound as the suggested solutions (i.e. the editorial)

If you checked the successful submissions on the right, almost all of them are written in C/ C++, with usually less than 5 written in Java. for some questions, I guess solutions written in other languages (say Python) are basically impossible to pass the time limit, even if they are perfectly optimized.

I’m not new to this community, and I understand there is always disadvantages programming in non-C languages. This happens too for other coding platforms, say codeforces or topcoder. but I feel that this problem is much much more severe here.

1 Like

i normally code in python and have never faced much of a problem except in 1 or 2 problems.infact i sometimes feel time limit for python is too lenient. i do not know much about Java but i would suggest faster I/O makes a lot of difference in time. other optimizations depend on you

2 Likes

@hiukim : Just getting the time complexity right , does not ensure that you will not get TLE . You should also optimize the number of steps you do in each iteration .

I also program in Java and I have always managed to get rid of TLE by optimizing my code , like reducing a heavy operation like division or modulus in each iteration .

A code requiring 10 * N steps may not pass , while a code requiring 2 * N steps may pass .

This happens time and again and you have to resolve this by optimizing your code .

Let me give two examples (I can definitely give more)


both of these have no successful submission written other than C/C++ languages

and my solutions:
http://www.codechef.com/viewsolution/2321837
http://www.codechef.com/viewsolution/2338585

I believe both of them have the same time complexity as those suggested in the editorial. I even checked some of the successful submission are implemented with the same idea. It’s not perfect, but I believe they’re reasonably optimized.

I mean… the bottomline is, if I implemented a solution using the same logic as the one in editorial (which is kind of the expected solution), then the solution shouldn’t get TLE with reasonable optimization, right?

I actually think you shouldn’t get TLE even if the code isn’t optimized as long as it’s using the correct algorithm, because it probably won’t deviate from the perfect one too far, say O(N) vs O(3N). but if the solution is optimized to O(N) vs O(1.1N) and still get TLE, that would be very discouraging.

Hello @hiukim,

Time limit is not equal to all languages due to the nature and usage of some versus others and due to the consequent differences in speed. A Python code can never compete with the same (non) optimized code in C/C++.

So, in order to make it a relatively fair game, in the online judge, multipliers were defined.

A multiplier is simply a factor that multiplies the TL, so that the actual time limit is extended only on some languages. What does this means in pratical terms?

Well, it means that if you have a problem with the Time Limit set for X seconds, the Python code you ran to solve that problem will actually have a real Time Limit of X*multiplier seconds.

For the case of Python this multiplier is 3 and for case of Java, multiplier is 2.

Time Limit for Java
Time Limit for the other languages

I hope this cleared your doubt, but, as you see, the game is kept fair :slight_smile:

Best regards,

Bruno

2 Likes

@hiukim : Oh , you didn’t know this . The time limit is twice for all Java submissions irrespective of the problem

interesting to know.

so is the multiplier apply to all problems automatically, or the question’s author set it manually per each question. if it’s the second one, is there any way I can check the multiplier?

That’s automatic for all problems.

I didn’t know. is it mentioning somewhere in FAQ?

@hiukim : http://www.codechef.com/wiki/faq#How_does_the_time_limit_work

2 Likes

cool. thank you.

But are multipliers also enabled on old problems available in the practice section?

@karan173 : Yes multipliers are enabled for all problems in practice / competition etc , hosted on code chef .