10990 - Another New Function

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Tue Feb 14, 2006 5:18 am

A simple one :

input

Code: Select all

25
2 3
2 4
2 5
2 7
4 73
5 29
6 329
1230 3728
23529 55444
50000 60000
90888 90888
2 100000
100001 200000
1000000 2000000
1999999 2000000
2000000 2000000
2 2000000
182 298149
16871 199290
34 28711
6163 6163
7777 7777
12345 12345
1725777 1725777
10 10
output

Code: Select all

3
5
8
13
325
94
2063
24762
424814
137488
13
1325890
1495090
17760797
38
19
33829803
4349639
2623043
336858
11
12
13
18
3
Sorry For My Poor English.. :)

mrahman
New poster
Posts: 25
Joined: Mon Oct 24, 2005 9:45 am
Location: Bangladesh
Contact:

Recursion+DP to solve this Problem

Post by mrahman » Thu Feb 16, 2006 9:08 am

I use Recursion to generate all the PHI value. Then DP to store the summation. My Timing is: 0:00.865(2nd in Ranklist). What is the approach of Krzysztof Dul
Practice Makes a man perfect

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Thu Feb 16, 2006 10:08 am

No recursion, just a well coded sieve (but there's still plenty of room for improvements :-) ).
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Thu Feb 23, 2006 1:20 pm

Do you know how to factor the numbers from 1 to N in O(NlogN) time? It's a simple modification to the standard Sieve of Erastosthenes. That's a start.

The next step is to look at the formula for phi(n) that uses the factorization of n.
The Memory complexity of modified-sieve-algorithm (for factorization of integers) should be O(N), not O(N lgN).
(I used just 4 arrays of size 2000000, and used memory is almost 30000.
You shouldn't use more than 4 linear-arrays, or you'll get MLE.)

for each integer v ∈ [1...N],
store the prime factor factor[v] that divides v.

And, another hint :
factorization of 72 can refer factorization of 9, if factor[72] is 2.
The formula for phi(n) that uses the factorization of n is this if I am not mistaken: phi(n) = n*(1 - 1/p1)*....*(1- 1/pr) if the prime factors of n are p1, ... to pr. This can be rewritten as (n/p1...pr)*phi(p1)*...*phi(pr)

However my approach modifying the sieve and using this formula is still slow (about 1.2s on the OJ without I/O operations - I used 1 submission to time it and about 1.3s on my PC) as I am running the "full" sieve compared to those whose code run is < 1s :o

By "full" sieve I mean that I let the sieve continue after sqrt(2000000) which is about 1414 rather than let the sieve stop at 1414 so that all primes are handled. So my code is actually O(n^2) rather than O(n log n). It was mentioned in the above quote that it is possible to compute all phi(n) where n = 2000000 in O(n log n).

I used 3 arrays - 1 to store phi(n) for each n, one to store depthphi(n) fpr each n, and one to store sum(depthphi(i)) for i from 2 to n. the sum and depthphi are computed using DP and the bottleneck in my code is the code for computing phi(i).

I don't quite get the hints mentioned. Could someone give me a push in the right direction as to how to speed up my code? Thanks.

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Thu Feb 23, 2006 5:28 pm

Do you know how it becomes O(N lgN)? Where the notation "lgN" comes from ?

For every integer K,
the number of prime factor(may same) that divides K is less than O(lgK).

More clearly,
e1 + e2 + e3 + .... < lgK, where integer factorization K = p1 ^ e1 + p2 ^ e2 + p3 ^ e3 + ....


Because, for example, the maximum number of prime factor is when K is power of 2.
Almost cases it is far less than lgK, so we gets O(NlgN).
Sorry For My Poor English.. :)

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Fri Feb 24, 2006 2:58 am

I understand. It seems that I am doing 2 log k operations for each prime. For i = 1 and 2, phi = 1. Initializing for i >= 3, phi = i, I then use the sieve, if phi = i, then it's a prime, and I do a phi-- and then for each mutiple of i, I mutiply by phi(i)/i = (i - 1)/i = (1 - 1/i). This requires 1 multiplication and 1 division, which is why I have 2 log k. Is there a way to remove this constant 2?

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Fri Feb 24, 2006 8:17 am

That's enough. The constant 2 is not so important.

If your implementation of this algorithms into source code is right, you will get accepted.


But when you want to make it faster, you need some optimizations.
The operation phi <- phi * (i - 1) / i takes 2 operations, one multiplication and one division,
which seems to be not able to reduced in just one operation, but there will be some other ways to improve your speed.

Good Luck.
Sorry For My Poor English.. :)

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Mon Feb 27, 2006 4:20 am

Thanks. I already got AC in 1.201s and I don't think I can optimise it further.

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ » Sat Mar 04, 2006 1:54 pm

Can someone help me why I got RE :'( It's ok with DevC++

Code: Select all

Aced
Last edited by FAQ on Sat Mar 04, 2006 5:01 pm, edited 1 time in total.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Sat Mar 04, 2006 2:59 pm

FAQ wrote:

Code: Select all

[...] scanf("%d\n", t);
should've been

Code: Select all

scanf( "%d\n", &t );

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ » Sat Mar 04, 2006 5:02 pm

Thank sumankar a lot, I got AC now
It's such a stupid mistake. I'm still a beginner with C++ :-?

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

Getting TLE

Post by Ankur Jaiswal » Sat May 20, 2006 7:23 am

Smbd plz help me optimize my code.
Here it is

Code: Select all

#include<stdio.h>
#include<math.h>
int prime[1414],pr_nums[300],cnt;
int dep[2000001],sodf[2000001];
void find_prime(){
	int i,j,k;
	for(i=0;i<1414;i++){
		if(i%2==1)
			prime[i]=1;
		else
			prime[i]=0;
	}
	pr_nums[0]=2;
	for(i=3;i<38;i+=2){
		if(prime[i]){
			k=i*2;
			for(j=i*i;j<1414;j+=k)
				prime[j]=0;
		}
	}
	pr_nums[1]=3;
	cnt=1;
	for(i=5;i<1414;){
		if(prime[i]){
			cnt++;
			pr_nums[cnt]=i;
		}
		i+=2;
		if(prime[i]){
			cnt++;
			pr_nums[cnt]=i;
		}
		i+=4;
	}
}
void relatives(){
	int i=0,ans,n,num;
	long long srt;
	for(n=2;n<=2000000;n++){
		ans=num=n;
		srt=(long long)sqrt(num);
		for(i=0;pr_nums[i]<=srt && num!=1 && i<cnt;i++){
			if(num%pr_nums[i]==0){
				ans=(ans/pr_nums[i])*(pr_nums[i]-1);
				while(num%pr_nums[i]==0)
					num/=pr_nums[i];
			}
		}
		if(num!=1)
			ans=(ans/num)*(num-1);
		if(ans==1)
			dep[n]=1;
		else
			dep[n]=dep[ans]+1;
		sodf[n]=sodf[n-1]+dep[n];
	}
	sodf[1]=0;
}
int main(){
	find_prime();
	relatives();
	int n1,n2,t;
	scanf("%d",&t);
	while(t>0){
		t--;
		scanf("%d%d",&n1,&n2);
		printf("%d\n",sodf[n2]-sodf[n1-1]);
	}
	return 0;
}

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Sat May 20, 2006 10:33 am

Read other posts. Forget about prime genearation. Try to use this method to find phi for all i.
chunyi81 wrote:I understand. It seems that I am doing 2 log k operations for each prime. For i = 1 and 2, phi = 1. Initializing for i >= 3, phi = i, I then use the sieve, if phi = i, then it's a prime, and I do a phi-- and then for each mutiple of i, I mutiply by phi(i)/i = (i - 1)/i = (1 - 1/i). This requires 1 multiplication and 1 division, which is why I have 2 log k. Is there a way to remove this constant 2?

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

Post by Ankur Jaiswal » Sat May 20, 2006 12:36 pm

thats a great algorithm... going to implement it and i hope it wont give TLE.
thanx mamun (and ofcourse chunyi81).

Edited:
Got it accepted in around 2.1 secs.!!!
thanx a lot again.

Ankur Jaiswal
New poster
Posts: 31
Joined: Sat Apr 01, 2006 6:24 am
Contact:

Post by Ankur Jaiswal » Fri May 26, 2006 7:40 pm

I modified my code a bit and wow!!! got accepted in little over 1 sec. Now i am ranked 9th in this problem.

Post Reply

Return to “Volume 109 (10900-10999)”