PTUPLES - Editorial

Source limit means the size of the code that you will submit and not the memory used by the program

2 Likes

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.

4 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

Can any one help me with this :

Solution: 41877917 | CodeChef

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 :smile:

2 Likes

the code isn’t showing any output over ide, please help me with this, thanks in advance

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?

Here is my solution. It’s showing wrong.Thanks!
link: Solution: 41909776 | CodeChef

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.

Thanks @cubercoder

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

1 Like

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.

You can get complete information about memory limits here

1 Like

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.