PTUPLES - Editorial

PROBLEM LINK:

Practice
Contest: Division 3
Contest: Division 2

Author: Daanish Mahajan
Tester: Rahul Dugar
Editorialist: Aman Dwivedi

DIFFICULTY:

Simple

PREREQUISITES:

Sieve of Eratosthenes

PROBLEM:

You are given an integer N, your task is to find number of good tuples that can be formed by integers from 1 to N.

A tuple (a,b,c) is considered good if it consists of three prime numbers a, b and c
such that a<b<c≤N and a+b=c.

EXPLANATION:

Since all prime numbers are odd integers except 2, and we can never represent 2 as the summation of the other two primes, as it is the smallest prime number. Hence we say that in any good tuple (a,b,c) the integer c is always an odd integer such that a+b=c.

As, we know that:

Even+Even=Even \\ Odd+Odd= Even \\ Even+Odd=Odd

Since our c is always Odd, it means either a or b needs to be Even to form a good tuple. As a and b, needs to be prime numbers too, hence there is only one valid choice left i.e a needs to be 2.

Hence b will be equal to c-2, for a tuple to be good b needs to be prime number. Now, we can slightly re-frame our task as:

Given a integer N, we need to calculate such numbers say c, such that c and c-2 are prime numbers and are less than N.

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.

TIME COMPLEXITY:

O(N*log(N)) for pre-computation and O(1) for answering every query afterwards.

SOLUTIONS:

Setter
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
long long readInt(long long l, long long r, char endd) {
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true) {
		char g=getchar();
		if(g=='-') {
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g&&g<='9') {
			x*=10;
			x+=g-'0';
			if(cnt==0) {
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd) {
			if(is_neg) {
				x=-x;
			}
			assert(l<=x&&x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l, int r, char endd) {
	string ret="";
	int cnt=0;
	while(true) {
		char g=getchar();
		assert(g!=-1);
		if(g==endd) {
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt&&cnt<=r);
	return ret;
}
long long readIntSp(long long l, long long r) {
	return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
	return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
	return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
	return readString(l,r,' ');
}
 
 
int socool[1000005];
int anser[1000005];
void solve() {
	fill(socool+2,socool+1000'005,1);
	for(int i=2; i<=1000000; i++)
		for(int j=2*i; j<=1000000; j+=i)
			socool[j]=0;
	fr(i,2,1000'000) {
		if(socool[i]&&socool[i-2])
			anser[i]=1;
		anser[i]+=anser[i-1];
	}
	int t=readIntLn(1,100000);
	while(t--) {
		int n=readIntLn(2,1000'000);
		cout<<anser[n]<<endl;
	}
}
 
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(10);
//	int t=readIntLn(1,1000000);
	int t=1;
//	cin>>t;
	fr(i,1,t)
		solve();
	assert(getchar()==EOF);
#ifdef rd
	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
 
Tester
Editorialist
#include<bits/stdc++.h>
using namespace std;
 
const int mxN=1e6+5;
int ans[mxN];
vector <int> prime(mxN);
 
void precompute(){
 
  for(int i=0;i<mxN;i++){
    prime[i]=true;
  }
 
  prime[0]=false;
  prime[1]=false;
 
  for(int p=2;p*p<mxN;p++){
    if(prime[p]){
      for(int i=p*p;i<mxN;i+=p){
        prime[i]=false;
      }
    }
  }
 
  ans[0]=0;
  ans[1]=0;
 
  for(int i=2;i<mxN;i++){
    if(prime[i] && prime[i-2]){
      ans[i]=ans[i-1]+1;
    }
    else ans[i]=ans[i-1];
  }
}
 
void solve(){
  int n; cin>>n;
  cout<<ans[n]<<"\n";
}
 
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
 
  precompute();
 
  int t; cin>>t;
  while(t--){
    solve();
  }
 
return 0;
}

VIDEO EDITORIAL:

14 Likes

Precise, to the point and well explained! Thanks man…

2 Likes

This problem says source limit is 50,000 bytes. Isn’t an array of ints 1e6 long 4,000,000 bytes? Am I misunderstanding what “source limit” really means for these contests?

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