Adding to this, the source limit is in place so someone does not get bad ideas like they can precompute the big array beforehand and insert it in the program to escape TLE.
5 Likes
Can someone tell me why did i get TLE, when i did totally similar way? Solution: 41883169 | CodeChef
Please read this part from editorial:
Rest is implementation which can be done by finding all prime numbers before hand and then checking for every integer, say c. If we found c and c−2 to be prime number then we increment our answer. We also need to pre-calculate all answers for every N before hand as not doing so will result in TLE since T∗N is large enough.
What you are doing right now is that for each N, you are computing the count from scratch. It would be fine if there was only 1 test case. But as there can be a lot of test cases, it’s better to calculate this for all N from 1 to M in O(M) (M=10^6 here) and then just use this lookup table to answer each test case in O(1)
1 Like
You are almost there. You just went till 999999 instead of 1000000.
https://www.codechef.com/viewsolution/41892739
1 Like
I DID LIKE THIS , AFTER VARIOUS ATTEMPTS ON ONE LOGIC THAT ALL PRIMENO ARE ODD EXCEPT 2 AND SUM OF ODD+EVEN IS ODD , NOT ODD+ODD
https://www.codechef.com/viewsolution/41863096
#include<iostream>
#include<set>
#include<vector>
using namespace std;
int main(){
int t;cin>>t;
bool arr[1000001]={false};
for(int i=2;i<1000001;i++){
if(arr[i]==false){
for(int j=2*i ; j<=1000001 ; j+=i){
arr[j]=true;
}
}
}
vector<int>tejus;
for(int i=2;i<1000001;i++){
if(arr[i]==false){
tejus.push_back(i);
}
}
long long int answers[10000000]={0};
for(int i=1;i<tejus.size() ; i++){
int sum=2+tejus[i];
if(arr[sum]==false){
answers[sum]+=1;
}
}
for(int i=1;i<10000000;i++){
answers[i] += answers[i-1];
}
while(t--){
int n;cin>>n;
cout<<answers[n]<<endl;
}
}
perfect editorial
logic was explained in good way 
2 Likes
Your solution checks ‘n’ and computes ‘count’ for each testcase. However, since the constraints for N and T are large, it is returning you TLE. The problem expects you to pre-compute all values of N and then read each test case and simply fetch the count from the precomputed values data structure which is O(1) time complexity.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int const N = 1000001;
bool prime[N];
memset(prime,true,sizeof(prime));
for(int i=2;i*i<=N;i++)
{
if(prime[i])
for(int j=i*i;j<=N;j+=i)
prime[j]=false;
}
int ans[N] = {0} ;
int cnt=0;
for(int i=5;i<=N;i++)
{
if(prime[i] && prime[i-2])
{cnt++;}
ans[i]=cnt;
}
ios_base::sync_with_stdio(0),cin.tie(0);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
cout<<ans[n];
}
return 0;
}
// I wrote this code and its getting accepted on when i submit but when i try to run it on codeblock ide in my desktop it just open cmd and not even takes values just says
return -17123…(some -ve value) , so why is this so that its working fine on codechef and not on my ide codeblock when i run on my desktop
I also used the same code in Python, but don’t know why time limit exceeded. Is that due to the language?
No.
It must be due to your implementation. A lot of people got AC using Python. Easy problems are never language specific and should clear on all languages.
Hi @cubercoder, I read in the past that we should declare large arrays globally (on heap) as they can cause memory errors if defined locally (on stack). In the above solution arrays “prime” and “arr” are defined locally even though they don’t give any error but is there any situation when it can lead to errors?
What would be the differences had it been declared globally? What would be the memory consumption for both the variants?
Thanks for tagging me.
Things won’t lead to errors if you are being sane and making arrays of size 10^6 or 10^7.
That is the maximum size you will never need to assign to in competitive programming.
As for general knowledge about heap and stack sizes, I am sorry to say that I am not experienced on this topic and just learnt c++ last month. You are welcome to try out different sized arrays and see what runs out of memory
2 Likes
As I see, both of your approaches are not efficient. In your first solution, you are dynamically checking if the number is prime. The solution is fairly inefficient. In your 2nd solution, you did sieve for every test case. You are supposed to pre-Compute, and store them globally or in a static variable, only once. Then access the required thing in O(1) for every test case.
Because your stack cant take this big array. Just decrease the array size to 10^2 something. Your code will run on local machine. As different machine got a different stack size. Or you can just declare your globally. That will store your array in heap.
what wrong with my code it is printing correct output upto 5
after onwards it is printing output as 1
#include<bits/stdc++.h>
using namespace std;
vector<bool> prime(1000005,true),add(1000005);
void prim()
{
prime[0]=prime[1]=false;
for (int i = 2; i*i <=1000005; i++) {
if(prime[i]and prime[i-2])
{
add[i]=1;
add[i]= add[i]+add[i-1];
}
else
add[i]=add[i-1];
if(prime[i])
{
for (int j = i*i;j<=1000005;j+=i)
{
prime[j]=false;
}
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
prim();
int t;cin>>t;
while(t--)
{
int n;cin>>n;
cout<<add[n]<<"\n";
}
}