Prime Tuples Codechef div 3 January Cookoff

I found all the prime numbers till n and then stored it in arraylist and then checked the given conditions. The answer was coming right but approach gave TLE. What could be the possible reason?
Pls help
Question
Solution

  1. T <= 10^6
  2. You are recalculating all primes in every testcase, just do it once outside.
    Try fixing these first.
2 Likes

You generate the primes for each test, so it takes O(t \times n \times log log (n)).

You can precalculate the primes in O(n log log (n)) and then answer queries in O(1) per query for a total of O(t + n \times log log (n))

7 Likes

You can simply check the conditions globally and just print the answer in O(1). You are getting TLE as you are precomputing seive for each test case

1 Like

you can think of dp here
after storing primes in arraylist
example n=5and 6
primes {2,3,5}
dp[5]=1;
dp[6]=1;
again for n=7
primes{2,3,5,7}
dp[7]=dp[6]+1;

2 Likes

can u plz tell me why my sol is giving tle?

In your solve function ,to search the numbers the time complexity is n^2 which will not pass the constraints .You could improve your sieve function instead of pushing p in the vector check if p-2 is prime and if true push that into the vector and then in the solve function just use binary search for n and print the value.
https://www.codechef.com/viewsolution/41870699

time complexity of solve fn is O(n).

Can anyone please suggest me edits for not getting TLE, even though I have precomputed the sieve.
But applying binary_search for checking the no c. Please have a look at my code.

This is my code here Solution: 41888728 | CodeChef

yes sry…but still calculating the ans in O(nt +nloglog(n)) will fail the constraints .You could modify it to answer queries in O(1) but answering in O(logn ) should also suffice.

You are building the list of primes for every test case and applying binary search in a loop which will increase your time complexity. See my reply above Prime Tuples Codechef div 3 January Cookoff - #10 by new_coder_12

Yes got my mistake…Thanks

// between a given interval 
#include <bits/stdc++.h> 
using namespace std; 
vector<int  > v;

// Function for print prime 
// number in given range 
void primeInRange(int L, int R) 
{ 
	int flag; 

	// Traverse each number in the 
	// interval with the help of for loop 
	for (int i = L; i <= R; i++) { 

		// Skip 0 and 1 as they are 
		// niether prime nor composite 
		if (i == 1 || i == 0) 
			continue; 

		// flag variable to tell 
		// if i is prime or not 
		flag = 1; 

		// Iterate to check if i is prime 
		// or not 
		for (int j = 2; j <= i / 2; ++j) { 
			if (i % j == 0) { 
				flag = 0; 
				break; 
			} 
		} 

		// flag = 1 means i is prime 
		// and flag = 0 means i is not prime 
		if (flag == 1) 
			v.push_back(i); 
	} 
} 

// Driver Code 
int main() 
{ 
	// Given Range 
  int t;

  cin>>t;
  while(t--)
  {
	int L=1;
  int R;
	cin>>R; 

	// Function Call 
	primeInRange(L, R); 

int c=0;
//for(auto x: v)
//cout<<x<<" ";
for(int i=0; i<v.size(); i++)
if(v[i+1]-v[i]==2)
c++;
  
cout<<c<<endl;

v.clear();
  }

	return 0; 
}

can anybody tell why i am getting TLE

Let me walk you through the thought process of this problem, It is given that there are 105 test cases and per test n could be as large as 106 at this point you should be alarmed that it’s not wise to do anything in O(n) per test case. Now I am currently not thinking about prime generation but I see that a<b<c for a tuple ( a, b, c ) that is defined as prime tuple, also given that a+b = c now, realize that if a+b=c has to be true for primes a,b,c the only way this happens for a = 2 because it’s the only even prime, had this not been true, then a+b would be even ( as all primes greater than 2 are odd and any of them would sum to an even number ) and there is no even prime greater than 2 so it’s absolutely certain that a = 2, now we need to look for b and c, so do this b = c-2, so I need all tuples of ( 2, c-2, c ) such that c-2 and c should be primes as well, Now All need to know is if c-2 and c are primes are as quickly as possible, and the best I can do is pre-compute them and do O(1) check if c-2 and c are both primes. Now I know for each c is if c-2 and c are both primes so something like primes[c] and primes[c-2] could tell me in constant time if I have a prime tuple ( 2, c-2, c ) and I mark it as true that yes I have a prime tuple ending at c and now I just look how many such tuples I had before this one, all I need to do is add this one to those and I have my answer, that is why I pre-process using sieve that will give me O(nlog(log(n)) before query answer, and to be able to know the number of pairs upto certain n I do prefix sums, ie. prefix[n] gives be number of tuples upto n, So my query time is just O(1) and It makes sense as I have 105 queries or test cases. Hence the solution of sieve + prefix array.


void PrimeTuples(){
  ll n = 1000005;
  vector<bool>primes(1000005,1);
  primes[0] = primes[1] = 0;
  for(int i =2;i*i<=n;i++){
    if(primes[i]){
      for(int j = i*i;j<=n;j+=i){
        primes[j] = 0;
      }
    }
  }
  vector<ll>prefix(n,0);
  for(int i = 5;i<=n;i++){
    if(primes[i] and primes[i-2]){
      prefix[i] = 1;
    }
    prefix[i] =prefix[i]+prefix[i-1];
  }
  int t;
  cin>>t;
  while(t--){
    ll x;
    cin>>x;
    cout<<prefix[x]<<'\n';
  }
}
2 Likes
  1. Initialize a precompute array of size 1e6 (10^6) to all zeroes.

  2. Generate the primes before processing all test cases using sieve of eratosthenes.

  3. Now simply check if numbers i and i-2 are prime for all 1<=i<=1e6. if so, increment preCompute[i] by copying the previous value and incrementing that by 1. Else, simply copy preCompute[i-1] to preCompute[i].

Note that this should be done before processing all test cases.
A small hint: you can start your precomputation process from the number 5, since it is the smallest prime number that can be represented as the sum of two primes.

My Solution:

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
int preComp[(int) 1e6 + 1] = {0};
void sieve(int n){
   bool prime[n+1];
   memset(prime,true,sizeof(prime));
   
   for(int p=2;p*p<=n;p++){
       
       if(prime[p] == true){
           
           for(int i=p*p;i<=n;i+=p)
               prime[i] = false;
       
       }
   }
   int c = 5;
   preComp[c] = 1;
   for(int i=c+1;i<=n;i++){
       if(prime[i] && prime[i-2]){
           preComp[i] = preComp[i-1] + 1;
       }
       else{
           preComp[i] = preComp[i-1];
       }
   }
   
}
int main() {
   sieve(1e6);
   int t;
   cin >> t;
   while(t>0){
       int n;
       cin >> n;
       cout<<preComp[n];
       cout<<endl;
       t--;
   }
   
   return 0;
}

@akshay_012 You are doing O(n) check for a prime and for each test case, you do realize that t is as large as 105 so it will blow up to O(t*n) and see that will not pass no matter what.
I gave the thought process below, that should help.

thk dude

see (to all) , u must have to print the each test case in O(1) , so for precomputation there will be two scenarios -

  1. in N(root(n)) -
bool isPrime(ll x){

    for(ll j=2;j<=sqrt(x)+1;j++) {
        if(x%j==0) return 0;
    }

    return  1;
}

vector <ll> answers(2e6+10);
void calcPrime(){
    ll cnt = 0;

    for(ll i= 3;i<=1e6+10;i++){
        if(isPrime(i) &&  isPrime(i+2)){
            cnt++;
        }
        answers[i+2] = cnt;
    }



}


void solve(){
 ll n;
 cin>>n;
 cout<<answers[n]<<endl;
}

int main(){
    fastIO
    ll t=1;
    cin>>t;
    calcPrime();
    while(t--) {
        solve();
    }
    return 0;
}

2-(using sieve(Nloglogn))

bool prime[MAX+1];
void sieve1(){ //prime or not
    for(int i=0;i<=MAX;i++) prime[i]=1;
    prime[0]=prime[1]=0;
    for(lli i=4;i<=MAX;i+=2) prime[i]=0;
    for (int p=3; p<=MAX; p+=2){
        if (prime[p] == 1){
            for (int i=p*2; i<=MAX; i += p){
                prime[i] = 0;
            }
        }
    }
}

int main(){
fastio
sieve1();
lli t=1;
cin>>t;
lli dp[1000001]={0};
FOR(i,2,1000001)
{
    if(prime[i+2]and prime[i])
        dp[i+2] = 1;
}
FOR(i,1,1000001)
{
        dp[i] += dp[i-1];
}
while(t--)
{
    
    lli n;
    cin>>n;
    print(dp[n]);
}

return 0;
}

what about my approach dude it is able to pass all test case if there t=5,n=10^4
becoz(tle) i don’t know whether it’s correct or not

I have a very nice trick for you suppose we have to calculate tuples till 6 then we have (2,3,5) and if we have 20 we have [(2,3,5),(2,5,7),(2,11,13),(2,17,19)] and now if you look closely you’ll see that for the condition a+b=c to be satisfied one of the a or b must be even prime which is two because " sum of two primes can never be a prime " now you just have to fix 2 and calculate (2+i)th and check it with +2 and find the next number is prime or not , you can do this with Seive of Eratosthenes.