Increasing time limits

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.

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 ...

Oh. There's a formula to calculate the zeros in n! ... like I bet all those people with accepted answers derived it from first principles too! ... and what's that got to do with a time limit?

If the time limit were valid, why isn't it 1 sec because the solution would only have like 13 iterations for the maximum value ...

I am a recent arrival to spoj, and am enjoying it very much. However, I'm a little disappointed that the run time limits for some problems prevent one producing a solution in python, simply because python has such slow IO and scanning.

For example, I have a solution to HMRO which takes about 1.5 seconds to run on my laptop (1.6GHz P4M). This is with a dataset that I generate with size as specified on the problem description.

I get TLE on spoj.

I can strip it down so it just scans the input and produces canned output. Then it runs in 1.26 s and gets Wrong Answer (of course) after 4.38s.

So IO takes 4.38s out of the 5s available, and my algorithm, which is O(n) and runs in less than 1s cannot even be tested. I mean, it could be that it produces wrong answers, but I can't even test it.

It is a similar story for CISTFILL.

Yes, C has fast IO, and I would like to have fast IO in python too. But maybe just a little longer time limit would add to the fun while still preventing dumb and lazy O(n!) solutions from passing?

I'm using SPOJ for gaining experience with Haskell. PRIME1 shut me down though. On my box I can generate primes for 10 non-overlapping, non-contiguous 10k ranges in about 2.3 seconds. Kept getting TLE on submission so rewrote in Perl. Haha! Even slower so rewrote in C. I'm using the exact same algorithms (and checked the C output against the Haskell output) and the C code was accepted with a runtime of 1.2 seconds. (On my box it took 0.15!) Using a factor of 8 for this problem my Haskell code should finish in 18.7 seconds. Obviously that's not going to make the problem's 6 second time limit.

I've read through this thread and agree that time limits are a good thing in a point system to favor well written and efficient code. However big a disparity between languages folks are still trying to complete the contests (if for nothing more than for the challenge and entertainment value). My suggestion would be to use a system of natural selection. At the start of a problem, set some high time limit tracked per language. As you get submissions keep a log of the time successful programs took. Take the median of those values and call it the expected runtime for a solution in the given language. It seems a program isn't halted until about 2*T so if someone finishes within that time but not below T then offer the knowledge that their solution was correct but don't offer points.

$0.02,
-ljr

(edit) PS - Rewrote the Haskell version to use the first 6542 pre-calced primes (from all my other programs finding primes) covering the solution space. When tested on the same 10 non-overlapping, non-contiguous 10k ranges as above runtime on my box was 0.33 secs. Result on SPOJ... TLE!

I got a solution accepted for PRIMES1 in Scheme, with Guile. While fast Scheme interpreters and compilers do exist, the only (usable) Scheme interpreter at SPOJ is Guile, which is pretty slow (its intented use is as an embedded interpreter in other programs, which forced the authors to make compromises).

My C solution for that problem runs in 0.03s at SPOJ. If your C code is 40 times slower, then sorry to say this, but you're probably using the wrong algorithm.

I'm using a straight-forward implementation of miller-rabin with preset values that guarantee primality discovery for the range of values allowed in the problem. (I wrote my own pow_mod() which is probably where I'm missing out on time. Don't care enough to figure out the library call's name.) Alternately in Haskell I pre-calced the primes needed to cover the solution space. Perhaps I'm behind the state of the art in primality testing but I'd be really surprised if either of those could be labeled the 'wrong algorithm'.

-ljr

Please edit the very first post of this forum then. I wrote a Haskell program which received TLE. I am convinced I wrote the equivalent program in C which was accepted.

-ljr

A primality test such as Miller-Rabin (or Solovay-Strassen, or Fermat, or AKS, or whatever) is the wrong approach for this problem. You want a variation of the Sieve of Eratosthenes. Search the forum for suggestions, some of the posts practically spell out the answer.

The sieve is nice and fast in a... was going to say non-FP but I haven't tested them all so I'll say not-Haskell. If you look at my previous posts I pointed out that I built a source file that hard-coded all primes needed to cover the problem space. It still hit TLE. That's SoE with all the legwork pre-calculated so I'll admit the solution needed is beyond me.

Now I don't really care. I tried SoE. I tried Miller-Rabin. I tried pre-calc and all hit TLE. I won't argue that the problem isn't with me because obviously other folks have used haskell and are well below the limit. My original post was following up on the first post in this thread. I had an algorithm which hit TLE in a functional language. Same alg in C was accepted. I posted. Got told, 'What I really meant is "just make your program faster"'.

Nice system. Not useful as a learning tool for trying a new language. My bad.

-ljr

Would it be possible to run the problems for let's say double time, and then indicate the time with the TLE if available? Then it would give some indication whether one is near or not.

CANDY 1 can't be done in Guile afaik. Just ran 2 bogus scripts with dummy output, and the best result I got was 0.99 sec out of the 1s limit on reading the input.

having TLE using F# but solved these problems using C++ (C#):

(1) Problem http://www.spoj.pl/problems/LEXISORT/1
Statistic for F#: http://www.spoj.pl/ranks/LEXISORT/lang=FS (0)
my code: http://www.spoj.pl/files/src/4509752/

(2) Problem http://www.spoj.pl/problems/INTEST/
Statistic for F#: http://www.spoj.pl/ranks/INTEST/lang=FS (0)
my code: http://www.spoj.pl/files/src/4509704/

(3) Problem http://www.spoj.pl/problems/TSORT/
Statistic for F#: http://www.spoj.pl/ranks/TSORT/lang=FS (0)
my code: http://www.spoj.pl/files/src/4509667/ (O(n) algo - TLE)

why not to do for example such a think for F# ad other slow langs:
if functional_language then TLE = TLE * 2 (or mult by 3)

its really very sad not to have an opportunity to solve problems using your fav language.

You're stepping on shaky ground here I guess. Haskell and Ocaml have a bunch of solutions for mentioned problems.
So not "functional languages", but just F# mono.
Also zero solutions may not really mean something - F# was added not so long time ago.

Tried to solve above mentioned problems in F#:

LEXISORT: OK.
spoj.pl/status/LEXISORT,rulikkk/1

TSORT, INTEST: TLE (don't know how to speed up)
spoj.pl/status/TSORT,rulikkk/
spoj.pl/status/INTEST,rulikkk/

MUL: TLE (F# bigint probably too slow)
spoj.pl/status/MUL,rulikkk/

Just to appove that F# seems to be TOO slow on the server.

... Nic nie zrobiłeś, pole trójkąta ma być double

Co tu jest nie tak?

#include <cstdlib>
#include <iostream>
#include <math.h>
using namespace std;
int main(int argc, char *argv[])
{
	double t,a,b,c,k,n,p=0,h=0,s=0, z=0;
	cin>>t;
	cout<<endl;
	while(t--)
	{
		cin>>n;
		cout<<" ";
		cin>>k;
		cout<<endl;
		while(n--)
		{
		cin>>a;
		cout<<" ";
		cin>>b;
		cout<<" ";
		cin>>c;
		cout<<endl;
		p=(a+b+c)/2;
		h=sqrt(p*(p-a)*(p-b)*(p-c));
		s+=h;
		p=0;
		h=0;
	    }
	  if(a<b+c && b<c+a && c<a+b)
		{  
s/=10000;	
    
z=(s*k)*1000;	    
	    cout <<endl<<  round( z ) << endl;
			}
     	else
     	cout<<"0"<<endl;
		z=0;
		s=0;
		cout<<endl;
}
	system("pause");
	return 0;
}