Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

MERTENS - Mertens function

Calculate the Mertens function from 1 to 10000.





Added by:HWK
Time limit:11.79s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: SCM qobi

hide comments
2011-04-11 17:42:46 HWK
@hallvabo: Very impressive. But I think you don't really want to get the time limit increased. :-)
2011-04-11 15:56:15 Hallvard Norheim Bø
@HWK: finally managed to find a simpler and slower solution! I think the time limit might be a bit too tight, I had to replace ~-n with n>1 to sneak in under the limit :-)
2011-04-09 14:09:21 HWK
@Nabb: Great job.
BENCHI and DECFRAC are solvable with Bash too. ;-)
2011-03-18 06:15:41 :(){ :|: & };:

@HWK: You got me,I was keeping that optimization in hand in case you beat my speed ;-)

@hallvabo: I used the same idea,but this is not a good task to test sieve you may like to try in TDPRIMES :-)

And on the size of the solution I was using my standard template which is partially removed now,I haven't tried to shorten it but my best attempt will be around 200 bytes in C,considering that the time limit allows a naive prime checker instead of sieve.

Last edit: 2011-03-18 06:24:41
2011-03-17 15:05:16 Hallvard Norheim Bø
@HWK: I just wanted to see how far I could push the fast-sieve approach :)
Now I will try some other approaches, maybe I can get under a 100 bytes...
2011-03-17 12:54:50 HWK
@hallvabo: I belief you think too complicatedly. My Python-solution is still slower and now 100 Bytes.
2011-03-15 19:14:54 HWK
@hallvabo: Very impressive, but you forgot to shorten. My much slower Python-2.5-solution before publishing the problem needs only 102 bytes. I'm sure you'll beat it.
Sadly Python won't be faster than C++. (See my last comment.)

Last edit: 2011-03-15 19:16:42
2011-03-15 13:19:50 Hallvard Norheim Bø
@Debanjan: my first Python solution almost beat you for speed, and it's less than 1/24 of the size of your C++ solution ;-)

Btw, I use a sieve to generate the Moebius function up to 10000 and print the partial sums.

Last edit: 2011-03-15 13:23:58
2011-03-13 07:43:37 HWK
No, it can't. :-(
Now try to shorten it. :-)

PS: You really could accelerate your solution. By deleting an unnecessary step you'll easily reach 0.01 secs. ;-)

Last edit: 2011-03-13 15:26:14
2011-03-13 01:58:17 :(){ :|: & };:
Could your algorithm beat my current speed?It is possible to make it more fast though ;-)
© All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.