Jun 2004
29 / 46
Oct 2007
Jun 2023
Adrian_Kosowski
Aug '07

A problem admittedly exists, but perhaps it affects you differently than you believe. It goes more or less like this:

  1. A problem is comfortably solvable using a time-optimal algorithm in, say, 0.10-0.30s, when implemented in C.
  2. But: there exist slower languages.
  3. So: the time limit is set at a much higher level, say 6s.
  4. Side effect: solutions which were never intended to be correct (i.e. are too slow) get accepted if written in C. The same solutions are not accepted in slower languages.
  5. Users who write in other languages still feel they are being "unfairly treated".
  6. We either accept this or return to Step 3.

A general rule of thumb: if you wish to be confident that a problem is solvable in a given language, take a look at the ranks (e.g. https://www.spoj.pl/ranks/PRIME1/lang=HASK7). If several of the solutions are well within the limit, you should be OK, as long as you find the correct solution.

25 days later
mpr_sof
Sep '07

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.

1 month later
lannyripple
Oct '07

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

lannyripple
Oct '07

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

Adrian_Kosowski
Oct '07

Right, thanks for the suggestion.

mpr_sof
Oct '07

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.

lannyripple
Oct '07

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

Adrian_Kosowski
Oct '07

Well, not all the SPOJ problems are fit for all purposes. At least you can't say we didn't warn you wink (at the bottom of the problem text).

4 months later
imre
Feb '08

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.

1 month later
tical
Apr '08

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.

2 years later
SKYDOS_sof
Dec '10

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.

gorlum0_sof
Dec '10

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.

2 months later
3 months later
5 months later
skladak95
Dec '11

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;
}
gong911
Dec '11

Widze tu dodatkowe spacje i endl'y, które powodują, raczej na pewno, WA.

Jak masz wczytane 3 liczby np. "1 2 3", to po wczytaniu kazdej nie musisz dawać spacji...
wystarczy:

cin>>a>>b>>c;
//lub
cin>>a;
cin>>b;
cin>>c;
// lub scanfem

i tutaj:

cout <<endl<<  round( z ) << endl;

ten pierwszy endl też jest chyba zbędny

sebastian_mroz
Dec '11

Witam, generalnie kod mam podobny do kolegi wyżej ale bez wszystkich spacji i endli. Wyniki dla przykładu ze spoja mam dobre, a biorąc pod uwagę małą liczbę rozwiązań jest tu jakiś haczyk/kruczek. Oto mójkod
[bbone=text,641]AC[/bbone]
Podpowie ktoś co mogę zrobić?
@edit
Dziękuję smile Przeszło.

2 months later
solverka
Mar '12

Nie mam pojęcia co jest źle. Może mi ktoś podsunąć pomysł na poprawkę?

AC
1 year later
robrawr
Jan '14

Hej!
Program zwraca dobre wyniki dla przykładowych danych ze SPOJ'a, ale np. dla testu kokoska zwraca 119... Nie wiem, w czym tkwi błąd. Czy moglibyście mi pomóc? wink

Niezawodna pomoc użytkowników forum! :D
3 years later
shimilrahmanm
Dec '17

I have this issue with my python submission for LAZYPROG. Iam using the best approach, its c ++ version is working. python version is getting tle.
pls check the code