Increasing time limits

Adrian_Kosowski 2004-06-12 00:25:54 UTC #1

If you have written a program in a functional language (or Python, or Java) and received TLE, if you are convinced that you are using the best possible approach (in particular, that an equivalent program in C would have been accepted), please inform us about it in this thread. We will try to adjust timelimits or create a seperate version of the problem dedicated to functional programming.

overwise1 2004-06-13 21:30:07 UTC #2

I'm sure, I'm using an optimal approach with my O(S^2 + S * C) solution in python.
But this problem seems to be very time-critical, as I've heard, that O(S^3 + S * C) written in C did time out, although limit for the input is S <= 100.

I would be happy, if the input could generally be reduced for most of the problems, checking only if a solution produces correct output, not if it's optimal.
There would be many problems, for which a relatively bad performing algrithm could solve the test cases if written in a fast language, but that's the price if you would like to give haskell / python (probably even Java) programmers a chance.
Or if it would be possible to give different time / memory limits depending on the language used...

cu,
robin

noix 2004-06-13 22:27:09 UTC #3

I tested your Python program (sumbission 1220) with an extended time limit and it gave a correct answer after almost 6 minutes, where it took the best C programs only 3.01s. Time limit is 20s and we thought it would allow it to be solvable in slower languages..

We're considering multiplying time limit by a factor arbitrally set for a given language or providing more than one versions of a problem with changed limits and allowed languages.. We will most certainly do something about it, eventually.

kfas 2004-06-14 08:34:12 UTC #4

You should probably ask for the input to be increased. The bigger data is, more is the time complexity of the algorithm and the constant given by using a different language tends to be less important.
Best regards,
Adam

Adrian_Kuegel 2004-06-14 09:42:46 UTC #5

I agree if you mean the limit on the size of a test case.
Like in the problem "Complete the sequence", if limit would be n<=1000, but only a few test cases, the O(n^3) will still time out, whereas a program with O(n^2) in python would have the chance to pass.

mima_sof 2004-06-15 21:54:00 UTC #6

It's not a challange, when you produce only correct output. Many NP-hard problems have exponential time solutions, does it mean that we should accept them?? Time complexity is very important, and the way to force an appropriate complexity of the solution (via online judge) is to limit the execution time....

Yes, you are right, that's the price!
If only we get faster computers (next academic year), we'll try to overcome this problem.

Another solution: the problemsetter duplicates a selected problem with only a few languages, any suggestions?

Of course, this is a bit unfair towards users not programming in such languages like Haskell or Python, but on the other hand, if you wanted to solve it in such a language, you could do it!

Multiplying execution time, or using different time limits depending on the language is, in my opinion, unfair and impartial...

Finally, it's worth noting, that some problems support functional solutions, but others do not...

best regards,
mima

Kannan_Goundan 2004-07-26 20:52:31 UTC #7

The difference between languages is usually a constant factor, not merely a constant amount. So increasing the input size wouldn't change anything.

Adrian_Kosowski 2004-07-26 22:51:04 UTC #8

The idea is as follows: suppose that a functional solution is always 10 times slower than one in a fast language. To allow both languages to be used, the time limit should be set at a little more than 10x the time necessary to solve the problem for the given data in a fast language. This guarantees that (regardless of the size of input data) optimal solutions in both languages have a fair chance. But the only possible way of ascertaining that a non-optimal solution in a fast language doesn't slip through the time limit is increasing the size of the input data.

grzegorz 2005-09-12 14:03:19 UTC #9

My solution to the KAMIL problem (spoj.sphere.pl/files/src/241974/) runs in about 0.01 s on my system so I was surprised to get a Time Limit Exceeded from the judge.
Maybe the time limit should be a bit higher.

noix 2005-09-12 20:58:35 UTC #10

I don't know Prolog too well, so I'll just paste what your program (241983) spits out to standard error stream:

%  library(readutil) compiled into read_util 0.01 sec, 6,728 bytes
ERROR: (/solutions/solution:11):
Out of global stack
Warning: (/solutions/solution:11):
Goal (directive) failed: user:p(0)
% /solutions/solution compiled 1.52 sec, 13,428,092 bytes
ERROR: Undefined procedure: program/0
ERROR: Undefined procedure: program/0
ERROR: Undefined procedure: program/0
...

(..lots of those)

So -- it seems to me it's rather some programming error.

grzegorz 2005-09-13 10:23:29 UTC #11

Thanks for posting the error message.
Could you also say how prolog programs are run (i.e. what options are passed to the interpreter) so I can try to run it the same way on my machine,
as now I cannot reproduce this error.
Cheers

emilian 2005-09-13 11:48:18 UTC #12

Hy,

I'm trying to use only LISP for the problems here but TLE is making it really hard.

For example, SUMITR has both a low char and time limit. Making the small chars solution was ok but I have no way to make it fit into that time limit. (Needless to say that due to size restrictions I can't even declare some optimizations ).

I also have troubles with PLONK, FCTRL and INTEST.

Some of them could be my fault (INTEST should be optimized somehow with (declare)'s but this is some kind of black art) but overall I think the time limit isn't realistic for some LISP problems.

My SPOJ user is the same (emilian).

noix 2005-09-13 15:18:37 UTC #13

I'm afraid I won't help you much, but I noticed SUMITR and PLONK have "large Input/Output data, be careful with certain languages" warning (at the bottom of problem description.
In theory it means your I/O have to be fast enough to pass INTEST. If it doesn't pass INTEST, it probably is too slow even to read the input data and/or output the answers alone - no point in optimizing the algorithm itself.

As for strict source size limit.. one solution would be to give less/no size restrictions and make it an optimization problem, where the shortest code wins.. but it's a matter of taste and it's up to problemsetters.

P.S. You can always browse through the list of accepted solutions (like spoj.sphere.pl/ranks/PLONK/). If there are accepted solutions in languages you think are slower than Lisp, it should be possible

emilian 2005-09-13 19:03:00 UTC #14

Indeed this didn't help alot

Could you at least provide something like this for LISP/other?: TLE but program finished (correctly/not) in 1 minute with an extended time limit for some languages/problems.

I really want to see how slow it is.

noix 2005-09-13 20:43:46 UTC #15

In my opinion that's what tutorial problems are for. AFAIK there are some problems from the main problemset cloned with extended time limit in "tutorial" category.

emilian 2005-09-14 12:39:38 UTC #16

As far as I see the Sums in Triangle problem is with the same time limit and an extended char-size limit. Not quite the case.

But, there are only a handfull of problems in tutorial.

I have to say that this is getting quite frustrating for me. I think I have about 5 problems with TLE and quite fast algoritms (meaning stuff that shouldn't take long) but just because lisp seems to be slower I just keep them arround in my TODO list. It's getting quite tiresome.

hidden_sof 2006-05-30 12:28:28 UTC #17

The server of SPOJ have slow down very much , so accept solution before will get TLE now .

I alway get TLE of this problem (INUMBER , time limit=7s) with algorithm 10*N^2 (N<=1000). And i borrow an accepted solution of my friend , and surprisingly , it got TLE too .

Admin please rejudge submissions from rank 30 to 39 of this problem , i am sure they will get TLE .

PS: I have post this in ProblemSet Archive but no one answere me .

smoke_sof 2006-08-17 19:23:52 UTC #18

I have tried to solve FCTRL using gcl and clisp.
Unfortunately, I get time limit exceeded for gcl, which is strange, because GCL is natively compiled and is typically faster than clisp.

I have tried this locally with a relatively large input set (100000 times the number 8735373)

Results are as follows:
gcl 2.6.7 takes 6.8 seconds
clisp 2.38 takes 29.7 seconds

I am aware that I am using different versions locally, but still it feels strange.
Any idea how this can be?

(problem submitted has ID 491973)

jonathan_sof 2006-08-31 13:17:44 UTC #19

This is really frustrating ... I'm really not interested in the time issue but am constrained by time limits that apply to assembler like languages. You get a really nice and elegant solution that, ok may not be optimal, but who cares, my laptop is like 4 times as fast as the server that's imposing time limits ... sheesh!

The core of my Factorial (11) solution ID 496507 is just 21 lines, and I know it's correct, and I could probably get it to accept by caching previously calculated values, but that doesn't have anything to do with the solution to the problem, apart from the time limit problem, so what's the point??

Sorry for the rant, but it really burns my wick.

How about an option for no points and no arbitrary time limit for people who just want to enjoy themselves applying their minds to tricky programming problems, and leave the time limits for those who want to get to the top of some list.

Jonathan.

jonathan_sof 2006-09-01 02:47:24 UTC #20

Hmm ... ok then maybe I have missed the boat ... cacheing didn't help at all ... how do they do that in tiny fractions of a second without precalculating?? OCaml isn't that inefficient ...