10738 - Riemann vs Mertens

[Michael Goldshteyn]

I thought this was a very interesting problem to solve. Also, it seems like the number of approaches to this one is huge, judging from the enormous contiguous range of times and the large number of entries.

Michael Goldshteyn
(10738 - 0.020 s)

[Quantris]

Indeed, I'm quite interested in how you solved it with such a fast time. I guess you found a pattern I overlooked.

(Of course, one major thing to speed up my program which I'm too lazy to do at the moment is to not test all the even numbers, or even leave out multiples of three - well not exactly this but something like that, I'd have to explain the whole algorithm for this to make sense. but it is like when finding primes, you can just start by only considering the odd numbers or even odd numbers which aren't multiples of three, reducing the size of your sieve array by a constant factor)

(my time was 0.00.465)

[Michael Goldshteyn]

Indeed, I'm quite interested in how you solved it with such a fast time. I guess you found a pattern I overlooked.

(Of course, one major thing to speed up my program which I'm too lazy to do at the moment is to not test all the even numbers, or even leave out multiples of three - well not exactly this but something like that, I'd have to explain the whole algorithm for this to make sense. but it is like when finding primes, you can just start by only considering the odd numbers or even odd numbers which aren't multiples of three, reducing the size of your sieve array by a constant factor)

(my time was 0.00.465)

Well, giving twos a special consideration is certainly a good optimization. I am also going to give the hint that there is a research paper published around 1996 about Mertens' function. There are apparently even ways to calculate M without calculating all of the values in between, if you are very math inclined. In any case, using some of the techniques in that paper alone, it is possible to get times in the 0.3's or so.

You may also want to consider the Sieve of Eratosthenes, if you are not already using it in your program.

Just to set the matter straight, I don't use any of the techniques in that paper I mentioned above. In fact, I discovered it after having already reached a final time of 0.020 s. The techniques in the paper didn't help me at all, at this level. However, people with times greater than half a second should certainly consider at least glimpsing at the techniques mentioned there. It is, in a weird sort of way, quite interesting. As for me, I'm done with this problem, not being able to find any way of making it any faster. I am now trying to do my best on 10745 (Dominant Strings), where, as of today, I also hold a distant 1st place.

If you or anyone else have specific questions to help your program do better, I will be happy to chime in.

Thanks,

Michael Goldshteyn

[CDiMa]

Hi Michael!

Just to set the matter straight, I don't use any of the techniques in that paper I mentioned above. In fact, I discovered it after having already reached a final time of 0.020 s. The techniques in the paper didn't help me at all, at this level. However, people with times greater than half a second should certainly consider at least glimpsing at the techniques mentioned there. It is, in a weird sort of way, quite interesting.

[...]

If you or anyone else have specific questions to help your program do better, I will be happy to chime in.

I've tried for a while to improve my running time but my program still runs six times slower than yours, so I'm interested in some hint...
My latest algorithm uses some precompiled values for the tables M and mu. For each input I sieve from the nearest known value to fill a slice of the tables. This is faster than precomputing the entire table, but I don't think that this line of work allows for much improvement.
I'm thinking to another approach right now, precomputing the values of mu for small primes. Since this accounts for a lot of the looping this may lead to a substantial saving. What do you think about it? Otherwise, what other trick may be used that I'm overlooking?

Thank in advance for any suggestion!

Ciao!!!

Claudio

[OnErr0r]

Hi Guys,
I'm currently in second place, but with a sizable lookup table too. I've just submitted a new method which contains absolutely NO precalculated table, and timed in at .187 with the judge. I am going to ask that my current (.062) submission be removed.

This current submission runs at .052 on my own P3 1GHZ. It is unfortunate that we are not allowed to use -O3 or at very least -O for our code. In briefly looking at an ASM listing without any optimization it is ugly, to say the least. Here are the listing sizes:

No Optimization: 128K
(-O) Some Optimization: 56K
(-O3) Full? Optimization: 48K

Of course smaller code size doesn't necessarily mean faster execution speed. But I think a minimum of -O would be a good idea, to at least be somewhat comparable to the output of industry compilers.

My main question is: Why are optimization switches not used by the judge?

[CDiMa]

Hi Guys,
I'm currently in second place, but with a sizable lookup table too. I've just submitted a new method which contains absolutely NO precalculated table, and timed in at .187 with the judge.

Well, my precalculated table isn't that big and I've too a nil-precomputed solution that's timed like yours.

My main question is: Why are optimization switches not used by the judge?

Presumably this has to make with the resources needed to compile submissions by the OJ. Without optimization the judge sometimes crawls, figure how it could behave if optimizations were enabled.
Apart from that I think that pascal and java submitters would have something to say too...

Ciao!!!

Claudio

[OnErr0r]

I suppose we can make conjectures about the reasoning for lack of optimization, but I'd really like to hear the reason someone running the judge.

Btw, I'm currently at .076 from the judge with absolutely NO lookup table. Hopefully I can squeeze a bit more out of this algo, so I can eclipse my .062 time.

[cytmike]

Hi, guys
How can you make it<1s?

Because I'm really too stupid to do this.

[Tanu]

Hi guys I found a interesting thing from....
http://acm.uva.es/p/v107/10738.html
Here is two Accepted code but outputs different....
If anyone (also its a question to the judge) can say why it happens...
First one

Code: Select all

#include<stdio.h>
#include<math.h>
#define MAX 1000001


struct st
{
	long fact;
	long mu;
	long M;
}
arr[MAX+5];
void make()
{
	long i,j,k,count=0;
	for(i=2;i<MAX;i++)
	{
		if(arr[i].fact==0)
		{
			for(j=i;j<MAX;j+=i)
			{
				k=j;
				count=0;
				while(k%i==0)
				{
					arr[j].fact++;
					k/=i;
					count++;
				}
				if(count>1)
					arr[j].mu = -2;
			}
		}
	}
	arr[1].fact=0;
	for(i=1;i<MAX;i++)
	{
		if(arr[i].mu==-2)
			arr[i].mu=0;
		else if(arr[i].fact%2==0)
			arr[i].mu=1;
		else
			arr[i].mu=-1;
	}
	for(i=1;i<MAX;i++)
		arr[i].M=arr[i-1].M+arr[i].mu;
}
main()
{
	long input;

	make();
	while(1)
	{
		scanf("%ld",&input);
		if(input==0)
			break;
		printf("%8ld%8ld%8ld\n",input,arr[input].mu,arr[input].M);
	}
	return 0;
}

The second one(from my freind) ...

Code: Select all

#include <stdio.h>
#include <math.h>

#define  MAX           1000000

long Factor[MAX + 1] = {0};
bool SqureFree[MAX + 1] = {false};
long mu[MAX + 1]={0,1,-1,-1,0},M[MAX + 1]={0,1,0,-1,0};
long prime[ MAX ] = {0};

int main()
{
	long i,t,n,j,s;
	//seeving
	s =(long) sqrt(MAX) + 1;
	for(i=2;i<s;i++)
		if(prime[i]==0)
			for(j=2;i*j<=MAX;j++)
				prime[i*j] = 1;
	prime[0]=2;  //took prime serialy
	n=1;
	for(i=3;i<MAX;i=i+2)
		if(prime[i]==0)
			prime[n++]=i;
	prime[n] = 0;

	for(i=0;i<n;i++)
	{
		t = prime[i];
		for(j=1;t<=MAX;j++)
		{
			t = prime[i]*j;
			Factor[t] += 1;
		}
	}

	for(i=0;i<=s;i++)
	{		
		t = prime[i]*prime[i];

		for(j=t;j<=MAX;j+=t)
			SqureFree[j] = true;
	}
	
	for(i=4;i<=MAX;i++)
	{
		if(SqureFree[i]==true)
			mu[i] = 0;
		else if( Factor[i]%2 )
			mu[i] = -1;
		else
			mu[i] = 1;
		M[i] = M[i-1] + mu[i];
	}
	
	while( scanf("%ld",&n),n )
		printf("%8ld%8ld%8ld\n",n,mu[n],M[n]);
	return 0;
}

But anyone compile above codes will get two different output for higher input....

Now here is an post about it
http://acm.uva.es/board/viewtopic.php?t ... e9af1d45fa
If anyone can answer why these two type of answer both accepted...


Everything in the earth can make fun...,isn't it?
Thanx in advance...
...Tanu

[Rocky]

I solve 10738 and get acc and my other freind also get acc..
but it is not matter the matter i get wrong output with some data with my freind

i want to know what is correct output for this input:

50000
100000
1000000

can one acc person help me...

i think the data for this problem is so weak.

THANK's IN ADVANCE
Rocky

[Cho]

My output:

Code: Select all

   50000       0      23
  100000       0     -48
 1000000       0     212

[Rocky]

Thank's For Reply

But You Know It is a Strange Matter that my freind get same output like you...but not me.i get different output for the following input.
How It Possible To Get acc.. with different output for same input...

what you think...the problem should rejudge...????

Thank's In Advance
Rocky

[Cho]

The problem has specified that there are only 1000 input with values not more than 1000000. So the data definitely cannot cover all possible input values. I don't think there is problem in the data. It's sometimes possible for an incorrect solution to produce correct output for the judge's data. I have this expreience three times already.

[Tanu]

visit
http://acm.uva.es/board/viewtopic.php?t ... 91b883862c

can U say the other problems with this trouble...

[Rocky]

Thank's For Reply to Cho & tanu(my freind that i talk about)
But how it possible that some incorrect solution produce correct answer for judge data.... & plsss can you test the wrong solution which already accepted... by the link that tanu post.

can you explain your experience(three time).....

Thank's In Advance
Rocky