CHEFMGX - Editorial

The setter solution in itself giving an RE do check it.

Hey, Setter’s solution is misleading. It says linear Sieve but it’s not.

Nope. I just submitted and it is accepted.
https://www.codechef.com/viewsolution/52778679

ig the solution might have been updated you can see RE here
https://www.codechef.com/viewsolution/52761056

Ohk . Thanks dude

Can anyone help!!
Giving TLE on second Task

This is my code:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define int long long int
#define double long double
#define pb push_back
#define fi first
#define se second
#define ins insert
#define endl ‘\n’
#define pbds tree<int,null_type,less,rb_tree_tag,tree_order_statistics_node_update>

const int MOD = 1e9 + 7;

int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);
}

int lcm(int a,int b){
return ((a/gcd(a,b))*b);
}

int PowExpo(int a, int b){
int res = 1;
while(b){
if(b%2!=0){
res = (resa)%MOD;
}
a = (a
a)%MOD;
b/=2;
}
return res;
}

bool IsPrime(int a){
if(a==1) return false;
bool ans = true;
for(int i=2;i<=sqrt((double)a);i++){
if(a%i==0){
ans = false;
break;
}
}
return ans;
}

bool IsPow2(int n){
if(n==0) return false;
return (n&(n-1) ? false:true) ;
}

int fact(int n){
if(n==0 || n==1){
return 1;
}
return n*fact(n-1);
}

int highestPowerof2(int n){
int p = (int)log2(n);
return (int)pow(2, p);
}

void reverse(string& s){
int i=0;
int j = s.size()-1;
while(i<=j){
swap(s[i],s[j]);
i++;j–;
}
}
const int MAX = 1e7+1;
vector sieve(MAX, true);
vector primeInRange(MAX,0);

void sieveOfEratosthenes(){
sieve[0] = sieve[1] = false;
for(int i=2;ii<MAX;i++){
if(sieve[i]){
for(int j = i
i; j<=MAX ; j+=i){
sieve[j] = false;
}
}
}
primeInRange[2] = 1;
for(int i=3;i<MAX;i++){
if(sieve[i]){
primeInRange[i] = primeInRange[i-1]+1;
} else {
primeInRange[i] = primeInRange[i-1];
}
}
// for(int i=0;i<20;i++){
// cout << primeInRange[i] << " ";
// }
}

void solve(){
int l,r; cin >> l >> r;
int count = primeInRange[r]-primeInRange[l+1];
// cout << "count = " << count << endl;
cout << r-l-count << endl;
}

int32_t main(){
sieveOfEratosthenes();
int t=1;
cin >> t;
while(t–){
solve();
}
return 0;
}

Could somebody please help me find out where I am going wrong, My second test case does not seem to pass. Here is the link to the code: Solution: 52843667 | CodeChef. Any help will be appreciated

Welcome :grin:

1.Firstly, always define the upper bound for the global arrays , so instead of 1e7 , use 1e7 + 7 to avoid memory errors.
2.You are computing the prefix array while precomputing the seive in the outer loop which runs for sqrt(MAXN) , hence only up to sqrt(MAXN) the prefix array is evaluated , and we can assume that the second test case contains input files greater than sqrt(MAXN) which fails , to rectify this you need to compute the prefix array after marking the seive array.
Here is your AC code https://www.codechef.com/viewsolution/52856555

1 Like

I understand that it’s not always possible to include every test cases, but this case (in my opinion) was a strong edge case and a basic one, which should have been included.

1 Like

I removed those comments from setters solution. Thanks.

1 Like

Please help me find the error in this solution.
it always passes the first testset , but gives wrong answer in the second testset.
sample testcases are running well too.

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

const int maxx = 1e7;
bool prime[maxx + 5];
ll tot_prime[maxx + 5];

void pre() {
    
    // fill(begin(prime), end(prime), true);
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false;
    
    for (ll p = 2; p * p <= maxx; p++)
    {   
        tot_prime[p] = tot_prime[p-1];
        
        if(!prime[p]) continue;
        
        tot_prime[p]++;
        
        for(ll i = 2 * p; i<= maxx; i += p) {
            prime[i] = false;
        }
    }
}

int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
	int t; 
    cin>>t;
	
	pre();
	
	while(t--) {
	    ll x,y;
	    cin>>x>>y;
	    cout<<(y - x - (tot_prime[y] - tot_prime[x + 1]))<<"\n";
	}
	
	return 0;
}

Exactly same problem i addressed here https://discuss.codechef.com/t/chefmgx-editorial/95496/51?u=ramandeep8421

Your AC code https://www.codechef.com/viewsolution/52896630

Thanks alot mate !
I got it :v:

You are welcome :grin:

in editorials solution, in the first iteration for example
“tot_primes_till[i] = tot_primes_till[i - 1]” how the value of tot_primes_till[1] will be assigned to tot_primes_till[2] as we haven’t assigned anything in that array so it should contain garbage value.

All elements are initialised to 0 if the array is declared globally. Even a Primary School kid knows this fact.

FYI: initial value of int array in C - Stack Overflow

2 Likes

Thanks bro

Someone kindly help!
JAVA is not able to cross the TLE error in Subtask 2.
I don’t know how to improve this.

import java.util.*;

class Codechef
{
final static int MAX = (int)1e7;
static boolean prime[] = new boolean[MAX+5];
static int total_primes_till[] = new int[MAX+2];

public static void sieve(){
    int n = MAX;
    
    Arrays.fill(prime, true);
    
    for(int i = 2; i <= n; i++)
    {
        total_primes_till[i] = total_primes_till[i - 1];
        
        if (!prime[i])
           continue;
           
        total_primes_till[i]++;

        for(int j = 2 * i; j <= n; j += i)
            prime[j] = false;
    }
}

public static void main (String args[])
{
    try 
    {
        Scanner Sc = new Scanner(System.in);
		int T = Sc.nextInt();
		sieve();
		while(T-- > 0)
		{
		    int X = Sc.nextInt();
		    int Y = Sc.nextInt();
		    int ans = Y - X - (total_primes_till[Y] - total_primes_till[X+1]);
		    System.out.println(ans);
		}
    } 
    catch (Exception e) 
    {
        return;
    }
}

}

Same problem : CHEFMGX - Editorial - #51 by ramandeep8421