TLE in Problem code: NFACTOR

spd_sof 2011-02-04 16:41:33 UTC #1

Can somebody optimize this code...
spoj.pl/problems/NFACTOR/

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int is_prime(int n) {
int i;  
  if (n == 1) return 0;
  if (n == 2) return 1;
  if (n%2 == 0) return 0;
  for (i=3; i*i<=n; i+=2)
    if (n%i == 0)
      return 0;
  return 1;
}
int prpdiv(int n)
{
	int count;
	int i;int rt=sqrt(n);
	int x=0;
      if(is_prime(n)) count=1;	
      else count=0;
 if(n==1){return 0;}      
       for(i=1;i<=rt;i++)
          {
		if(n % i ==0)
	       {	  
		if(is_prime(i)) count++;
	  	x=n/i;
		if((x!=i)&&(x<=n/2))
		  if(is_prime(x))count++;	
	    }
     }
return count;		
}
int main()
{
	int T;
	int a,b,n,count=0;	
	scanf("%d",&T);
	while(T--){
	  scanf("%d%d%d",&a,&b,&n);
           while(a<=b){
	     	if(n==prpdiv(a)) count++;	                     
		 a++;
                  }         	  		  	
	printf("%d\n",count);	
	count=0;	
	}
return 0;
}

leppyr64 2011-02-04 16:56:36 UTC #2

You can't use brute force.

spd_sof 2011-02-11 19:39:46 UTC #3

i provided a more efficient soln still i am getting TLe is there any more optimization possible...???

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int prime_factor[1000001];int tau[1000001];
void display(int *arr){
	int i=0;   
	for(;i<=10;i++)
          printf("%d ",arr[i]);
printf("\n");	
}
int main()
{
	 int i,j; 
 for(i = 1; i <= 1000001; i++) {
        prime_factor[i] = i;
 	//tau[i]=0;       
    }
for(i = 2; i <= 1000001; i++){
        if(prime_factor[i] == i){
         tau[i]++;   
	 for(j = i+i; j <= 1000001; j+=i)
                {prime_factor[j]=i; tau[j]++;}
          }   
}
    int T;
int a,b,n,count=0;	
scanf("%d",&T);
while(T--){
  scanf("%d%d%d",&a,&b,&n);
         while(a<=b){
            if(tau[a]==n) count++;
            a++;
	}          	
     printf("%d\n",count); 	
     count=0;	
}
return 0;
}

leppyr64 2011-02-11 19:52:38 UTC #4

O(t*b) is still a massive amount of operations. You can do better.

If a = 1 and b = 10^6 and t = 10000, that's 10^10!

spd_sof 2011-07-18 17:49:52 UTC #5

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<iostream>
#define MAX 1000001
using namespace std;
int prime_factor[MAX];int tau[MAX];
int vec_bsearcha(vector<int>v,int a){
  int mid; 
  int first=0,last=v.size()-1;
  while(first<=last){	
  mid=(first+last)/2;
  if(a==v[mid]) return mid;
  else if(a<v[mid]) last=mid-1;
  else    first=mid+1;
}
 return mid;
}
int vec_bsearchb(vector<int>v,int a){
  int first=0,last=v.size()-1;
  int mid;
  while(first<=last){	
  mid=(first+last)/2;
  if(a==v[mid]) return mid;
  else if(a<v[mid]) last=mid-1;
  else    first=mid+1;
}
 return mid-1;
}
int main()
{
	 int i,j; 
 for(i = 1; i <= MAX-1; i++) {
        prime_factor[i] = i;
 	//tau[i]=0;       
    }
for(i = 2; i <= MAX-1; i++){
        if(prime_factor[i] == i){
         tau[i]++;   
	 for(j = i+i; j <= MAX-1; j+=i)
                {prime_factor[j]=i; tau[j]++;}
          }   
}
//display(tau);
vector<int>v[11];
for(i=0;i<=MAX-1;i++){
  switch(tau[i]){
  case 0: v[0].push_back(i); break;
  case 1: v[1].push_back(i); break;
  case 2: v[2].push_back(i); break;
  case 3: v[3].push_back(i); break;
  case 4: v[4].push_back(i); break;
  case 5: v[5].push_back(i); break;
  case 6: v[6].push_back(i); break;
  case 7: v[7].push_back(i); break; 
  case 8: v[8].push_back(i); break;
  case 9: v[9].push_back(i); break;
  case 10:v[10].push_back(i); break;
 }
}
    int T;
int a,b,n,count=0;	
scanf("%d",&T);
while(T--){
  scanf("%d%d%d",&a,&b,&n);
      int x2=vec_bsearchb(v[n],b);
      int x1=vec_bsearcha(v[n],a);
 if(a==1 && n==0) printf("%d\n",1);
 else if(x2==x1)    printf("%d\n",0);
 else printf("%d\n",x2 - x1 + 1);             

     /*while(a<=b){
            if(tau[a]==n) count++;
            a++;
	}          	
     printf("%d\n",count); 	
     count=0;*/	

   }
return 0;
}

I used binary search but it is still giving TLE please help.....

leppyr64 2011-07-18 18:16:54 UTC #6

Replace the vector with an array and get rid of the binary search. The constraints are small enough that does not matter.

spd_sof 2011-07-19 13:43:49 UTC #7

I mean what will be the benefit..

Arent vectors dynamic arrays.... if i use simple static arrays how will i know how many elements would be there in the 10 arrays individually.... i think it would be better to use vectors instead.
2.wouldn't Binary search further reduce the complexity.
3.even if I use normal static array ... wouldn't it be the same mistake which i was committing in the previous code. (which involved linear searching).

leppyr64 2011-07-19 13:52:34 UTC #8

If you use the static array you can answer each test case in O(1). Binary search is logarithmic. The issue with your static array was how you were using it. Think of a better way to model it.

The constraints are small. Use that to your advantage.

spd_sof 2011-07-19 14:30:51 UTC #9

how... i am not getting it

leppyr64 2011-07-21 10:30:18 UTC #10

I really can't give any more information without solving the problem for you.

tempest_sof 2011-07-21 18:49:43 UTC #11

Hello, can someone please help me find why my code is giving TLE?..or help with some optimization or better algo...thanks

ac

spd_sof 2011-07-23 12:01:09 UTC #12

u r committing the same mistake as I was committing in my earlier codes....check out leppy's comment.

tempest_sof 2011-07-23 15:02:14 UTC #13

Thanks...sorry I did not see the above codes

spd_sof 2011-07-23 17:39:51 UTC #14

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<iostream>
#define MAX 1000001
using namespace std;
int prime_factor[MAX];int tau[MAX];
int main()
{
	 int i,j; 
 for(i = 1; i <= MAX-1; i++) {
        prime_factor[i] = i;
 	//tau[i]=0;       
    }
for(i = 2; i <= MAX-1; i++){
        if(prime_factor[i] == i){
         tau[i]++;   
	 for(j = i+i; j <= MAX-1; j+=i)
                {prime_factor[j]=i; tau[j]++;}
          }   
}
//display(tau);
vector<int>v[11];
for(i=0;i<=MAX-1;i++)
if (tau[i] <= 10)  v[tau[i]].push_back(i); 
    int T;
int a,b,n,count=0;	
int x1,x2;
    scanf("%d",&T);
while(T--){
  scanf("%d%d%d",&a,&b,&n);
   x1=0;
   while(v[n][x1]<a && x1<v[n].size()) x1++;   
   x2=v[n].size()-1;
   while(v[n][x2]>b && x2>=0) x2--;
  
 //if(x2==x1 && tau[x2]==n) printf("1\n"); 
 //else if(x2==x1 && tau[x2]!=n) printf("0\n");
 if(x2-x1+1 < 0) printf("0\n");
 else printf("%d\n",x2-x1+1);
}
return 0;
}

I removed binary search now....I am getting TLE please help..

tempest_sof 2011-07-24 06:30:12 UTC #15

Note that each query should be answered in O(1) time, while your code can't do that (runs a loop to find the no. of numbers with reqd condition).Also, we are just interested in the number of numbers, not the numbers themselves. So, u shd focus on how to answer the query directly....u may need to use more memory, but u shd have the answer ready.

Hope it helps

sarthak_sof 2011-07-24 21:22:18 UTC #16

any optimization.... i m getting TLE plz help
[code]#include

include

using namespace std;
int prime[100000],lim;
int nf[11][1000002];
int index[11]={0};
bool isprime[1000002]={false};
void primegenerator()
{ // using sieve
nf[0][0]=1;
nf[1][0]=2;
nf[1][1]=3;
nf[1][2]=4;
nf[1][3]=5;
index[0]=1;
index[1]=4;

prime[0]=2;
prime[1]=3;
prime[2]=5;
int x=2;
int n=5;
int m;
int i,j;
//int lim=2;
j=3;
bool not_prime=false;
isprime[2]=true;
isprime[3]=true;
isprime[5]=true;
int num,pd;
while(n<1000000)
{
	i=0;
	n++;
	not_prime=false;
	m=n;
	num=0,pd=0;;
	while(i<j && prime[i]*prime[i]<=n)
	{

		if(m%prime[i]==0)
		{
			m=m/prime[i];
			if(prime[i]!=pd)
			{
				num++;
				pd=prime[i];
			}
			not_prime= true;
		}
		else
		{
			i++;
		}


	}
	if(not_prime & m>1)
	{
		num++;
		nf[num][index[num]]=n;
		index[num]++;
	}
	else if(not_prime)
	{
		nf[num][index[num]]=n;
		index[num]++;
	}

	if(!not_prime)
	{
		prime[j]=n;
		isprime[n]=true;
		nf[1][index[1]]=n;
		index[1]++;
		//cout << n<< " ";
		//lim++;
		j++;
	}

	//x=6-x;
}
lim=j;

}

int main()
{
int t,q,r,n,ans;
scanf("%d",&t);
//t=0;
int i=0,j;
primegenerator();
/*for(j=0;j<100;j++)
{
cout << prime[j] << " ";
}
*/
while(t>0)
{
ans=0;int ans1=1;
int i=0;

	int m=n;
	int num1=0,num2=1;
	scanf("%d%d",&num1,&num2);
	scanf("%d",&n);
	for(i=0;i<index[n];i++)
	{
		if(nf[n][i]>=num1 && nf[n][i]<=num2)
		//printf("%d ",nf[i]);
		ans++;
	}

	//printf("\n");
		printf("%d\n",ans);
t--;
}

return 0;
}

[/code]

leppyr64 2011-07-25 04:14:46 UTC #17

Did you read any of the posts in this topic?

sarthak_sof 2011-07-25 07:46:29 UTC #18

yes i hav read them...but i m not able to make out:
can query answering process be faster than this without using binary search?
.....should i optimize my no. of factor calculator also?

leppyr64 2011-07-25 14:19:54 UTC #19

Each query should be answered in O(1).

sarthak_sof 2011-07-25 14:30:22 UTC #20

thanx for the help, i will try to do so