Jul 2012
1 / 21
Jul 2012
Dec 2012
Marcus_Stuhr
Jul '12

Here is the relevant loop:

numTestCases = int(raw_input())
for numCase in range(numTestCases):
    line = raw_input().split(' ')
    lower=int(line[0])
    upper=int(line[1])+1
    primes=primes_below(upper)
    for prime in primes:
        if prime>=lower:
            print prime
    print

I am also trying:

inputs = sys.stdin.read().split('\n')
numTestCases = int(inputs[0])
for numCase in range(numTestCases):
    line = inputs[numCase+1].split(' ')
    lower=int(line[0])
    upper=int(line[1])+1
    primes=primes_below(upper)
    for prime in primes:
        if prime>=lower:
            print prime
    print

Am I misunderstanding how input is handled on SPOJ? I've already completed ID1 but it does not really deal with input formatting of the same nature. I can verify that the algorithm works, but for whatever reason, SPOJ isn't liking the submission. Any advice would be helpful -- thanks!

Marcus_Stuhr
Jul '12

I should also mention that the full code works on ideone.com with the same input formatting as designated in the program statement

francky
Jul '12

Hi Marcus, welcome.
I'm Francky (from Project Euler, as you I guess)

I don't see any problem in your pieces of code.
Just I can tell some Python 'tricks', as you're new at SPOJ.

Python2.5 label is mostly true.
I'm sure you're using Python2.7 at home, there's some little differences, so be careful, NZEC (an error can be raised).
But on SPOJ, there's many servers, and most of them provides Python2.5(+psyco if you want).
There's too some servers with Python2.7 inside, (without psyco). (You can recognize them after submitting, the memory print is greater than Py2.5 ; often it's 3.8MB vs 4.0MB as a base, + your data if consequent)
I prefer using Python3, but sometimes I use Py2 witch is faster on I/O.
But You can't choose Py2.5 or Py2.7, it's the luck at each submission.

You can try a Py3 translation, it could solve your problem.
Example given : bit_length() is not available with Py2.5 !!! Only P2.7 and Py3+

I don't know how is working your primes-below, but an offset sieve is the key for a fast Python AC (ACcepted) solution.
I think a sieve on the whole range will get TLE (Time Limit Exceeded).

IDEOne is with Py2.7, remember that.
More, hardware is much faster on IDEOne, SPOJ is a slow PIII.

Have fun.

Francky

PS : here is a link9 to my first post here (it was on prime1 too), there's some useful answers of numerix (the best Python Guru here).

Marcus_Stuhr
Jul '12

Hey Francky -- yes I recognize you from PE as well. smiley Good to see you.

I'm using the same prime sieve algorithm I've used for most of the PE problems, actually (it is a sort of wheel sieve) -- returns all primes under 10^6 in about 50 milliseconds without psyco, etc. I assume we can re-submit faster solutions at any time, so for now I'm just trying to get the solution running without runtime errors on the SPOJ servers. I don't see anything that would fail in Python 2.5 but I could be wrong (I am indeed using Python 2.7).

EDIT: Just to test if something about my sieve is incompatible, I tried out the basic sieve located here (it doesn't use anything crazy in terms of syntax): hobershort.wordpress.com/2008/04 ... in-python/3 and got the same error, which makes me think the issue lies in the code snippets I've posted above.

francky
Jul '12

Further, will be the time of optimization, no problem for that.
I'm sure you'll find plenty of good problems for that. PRIME1 is one of them. wink

But let M=10**9, d=10**5
did you try the worst case ?
10
M-d M
M-2d M-d
...
M-10d M-9d

With my hardware at home, I use a 'rule' : SPOJ is ×20 slower.

To sieve a whole range, if your sieve is fast enough you can try this one.

=====
You can try using

import sys
sys.stdin.readline()
for line in sys.stdin:
  n,m=map(int,line.split())

I use that form in my solution.

You should know that split(' ') and split() are slightly different.
If the input is badly formatted it can make a difference.
(It rare but there's some problem with difficult input, see comments of each problem can help)

francky
Jul '12

As I said there's some server with Python2.7 and psyco is not available on them.
You can't choose, it's the luck or not.

I'm very bad user of psyco, and very rarely use it.
The way you use is the correct one I think.
I try a Py2.5+psyco submission, but I have NZEC (and I don't kno why) I really don't know how psyco work and what are the corners of that 'thing'. numerix is an excellent user of psyco. I guess he will help you with that ; I can't.

Edit :
If you felt with a Py2.5 server:
- you can use psyco and old style python
- new functions will get NZEC

If you felt with a Py2.7 server:
- trying to use psyco will get NZEC (unless in try block)
- you can use new functions.

As I said memory usage is a 'sign' of what you used :
33MB + data : Py2.5+psyco
3.7MB+data : Py2.5 without psyco
5.8MB+data : Py3.1

francky
Jul '12

That's true, it would be too easy ...
We have yet the bigint included in Python, ...

If you want a harder problem for your whole sieve, you can try this one2. Be careful it's not easy. (and possibly impossible in Python)

Edit : for TDPRIMES, there's a very relevant comment : "try first to have a fast PRIME1 solution, after it's an easy task", with that remark, I went from 9s to 1s !!!! Don't forget SPOJ server is an antic hardware with a cache size verrrry small, so counting each byte of data is helpful for some tough problems.

daft_wullie
Jul '12

It is not necessary to use sophisticated sieve implementations, you can get ACC using standard sieve of Eratosthenes. Mine was accepted with and without using psyco. Only sort of a trick was the use of a precalculated prime table.
Of course you won't beat the highscore without further optimization smile

Marcus_Stuhr
Jul '12

Managed to get PRIME1, CPRIME, TDPRIMES, etc... but it's going to be a challenge making a dent in some of these best times.

francky
Jul '12

I know your are one of the best Eulerians, I give you a list of number theory problem, as I see your interest, I too think it's an excellent start for work its speed.

I recommend to do them in Python, it's slow so you can better find bottleneck in algo.
first : PRIME1 with an offset sieve (6-wheel is possible but not easy)
SPRIME (you ever did it)
PRIMEZUC
--
If you want to check your is_prime function(s):
first : PON (easy)
AU12
PAGAIN (very hard in Python)
PRIC as a challenge !
-- and also
CPRIME is a special problem and I don't want to spoil, it's hard in Python.
NDIVPHI (too easy for you)
NDIVPHI2 (hard, seems impossible in Python)
--
If you want to test your factorization algos:
FACT0
FACT1
FACT2 is a real challenge !!!!
FACTSUM (good problem, time is very cool to get AC)
DIV
DIV2
DIVSUM
DIVSUM2
HOMEW <- very instructive.
NUMTRY (hard, but there's a tutorial edition)
Edit : there's other one, like medium factorization, ...
FACT0 and FACT1 are THE bases.

There's a lot of good problem on recursive sequence, but you could need fast IO to enter in the best score.
I appreciate lot of Fibonacci like problems, if you want a list of my favourites, just ask.

There's a big variety of problems, ...
Have fun.

Marcus_Stuhr
Jul '12

Sure, I'd like to hear of some of your favorites when you have the time -- thanks!

I did solve SPRIME yesterday (C++ 0.79s) but do not see it anywhere on my profile -- I imagine because it's a Challenge problem and not a Classic?

francky
Jul '12

I had 6 month ago (when I came here) a reading problem (like you ?), you can find some interesting answers : http://www.spoj.pl/forum/viewtopic.php?f=20&t=103355

2] SPRIME is in tutorial, so it will not appear, it's true, but I think it's a good problem for python, ...
For your information, tutorial problem don't give any points. Classical problem give points : 2 pts if you're the only one to solve it, less if many people could solve it. It's not relevant to begin here, just now you know that. Challenge problem give points in function of your score for the problem. (see details in rank page if you want).

edit : AMR10C, LEGRENDS (yes, there's a typo)
are good number theory problems for you !!!

1] You can see all user's solved problem with the link on it's name, my solved problem are here4
In the recursive sequence problems, you can do (from approx. easy to hard)
Without fast IO you can't be in fast chrono in the first problems, but the last one are less IO related as they're harder.

IWGBS
AP2
GNY07H
M3TILE
MAIN74
MAIN12A (easy for you)
FIBOSUM
FIBTWIST
OPC3A
GP1
AGS
SEQAGAIN
PUCMM210
BUILDTOW
NUMPLAY
SNAKYNUM
TETRAHRD
FLIB ( <- one of my favourites ; many tricks to be found ; warning, maybe impossible in Python)
REC
SPP ( <- one of my favourites ; very instructive ; keep it for near the end, after REC)
ITRIX2E
NACCI
STONE2 (not for python)
PIBO
BTCODE_J
PIB ( not yet AC, maybe the hardest fib-like problem )

All those problems don't require complex data structure, that's why I did them...
I will learn after how to use efficiently others structures.

There's many other interesting themes too.

Marcus_Stuhr
Jul '12

Yikes, what on earth is up with FACT2? Current algorithm got around 0.35s on FACT0 (5s limit) and 4.78s on FACT1 (20s limit) -- but TLE's on FACT2 (20s limit). Craziness. Looks like only one person so far pulled it off in Python + Psyco, haha.

17 days later
tjandra_sof
Jul '12

@francky: Thanks for your information. It's hard to find good recursive problems... 8)

francky
Jul '12

Now, you should try new methods to solve them much much faster.
As you're an eulerian (unlike me ; only 172 solved PE pbs), you should be able to solve them faster than me, smiley
The key for that is definitively not the IO. wink