Page 2 of 2
Posted: Sun Jan 15, 2006 12:47 am
by Darko
I did *almost* the same thing, but I generated sums at the same time I generated almost odd primes (AOPs). Every sum depends on AOP and the previous sum.
I am not sure why you are sorting numbers, mine are sorted when I'm done with the generating part. I basically went through all even numbers, counted the number of shifts needed to get an odd number out of them and checked if the remaining odd number is prime.
That resulted in <1sec.. in Java!
Darko
10914
Posted: Tue Feb 06, 2007 2:06 pm
by Sedefcho
Darko, I just managed to get ACC in Java but my
program runs on the Judge for about 5.500 secs.
I don't see anyone with an ACC solution in Java
faster than mine
It's probably because you
also have a C++ solution which is faster so the
Judge ranks you using that solution.
Do you mean 1 sec in Java on the Judge machine ?
Or do you mean 1 sec in Java on some other machine ?
If you have < 1 sec on the Judge I am quite curious how
you achieved that. It should be some quite good and
quite optimized Java code.
This one ( 10914 ) is a really nice problem.
Posted: Tue Feb 06, 2007 8:42 pm
by Darko
Yes, 1 sec on UVa:
http://acm.uva.es/problemset/statusjudge.php?u=19882
Java is not important there, I think the rest of it is. I recoded it in C and it ran in 0.8 secs. I will send you the code in PM.
Posted: Wed Feb 07, 2007 5:10 am
by rio
Solaris wrote:I got AC in about 2 seconds, but in the ranklist I saw quite a few ppl solving it in less than 1 sec. Can anyone give me a hint on the better solutions? I am unable to find a trick myself
My approach to the problem is as follows:
1. Generate all primes upto 5000000
2. Getting the almost prime numbers. (Each almost prime no is of the form 2^n * primeNumber)
3. Sort the numbers
4. Run a loop through the array to precalculate the abundance value.
5. Binary search to get abun(n) for any given n
I will be very happy if anyone gives me a hint about his/her better solution. Thanks in advance.
I tried time attack, and got 0.287 sec.
In my approach, I didn't precalculate the abundance value and calculate theabundance value for each input.
Precalculating the hole abundance value takes too much time.
Posted: Wed Feb 07, 2007 10:57 am
by Sedefcho
I precalculate the abundance values
OK, thank you all for the replies.
Posted: Tue May 01, 2007 3:00 pm
by Grazyna
I follow the strategy that it was written above.
1.calculate all primes till 5000000 and at the same time filling a sieve with almost odd numbers,
2 when reading from the input n, calculating the sum till n
I received about 10-20 times TLE.
I have no idea how to make it faster.
Thanks in advance for any suggestions.
here is the code of my precalculations:
Code: Select all
bool abud[10000100] = {0} ;
long maxn=10000100 , prime[350000] ;
long long sum ;
bool primeQ ;
long np , n , k , i , m ;
m=6 ; while(m<maxn) { abud[m]=1 ; m=2*m ; }
prime[0]=3 ; np=1 ;
for(n=5 ; 2*n<maxn ; n+=2) {
primeQ=true ;
for(i=0 ; prime[i]*prime[i]<=n ; i++)
if (n%prime[i]==0) { primeQ=false ; break ; }
if (primeQ) {
prime[np++]=n ;
m=2*n ; while(m<maxn) { abud[m]=1 ; m=2*m ; } } }