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 = (aa)%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 = ii; 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: CodeChef: Practical coding for everyone. Any help will be appreciated
Welcome
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
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.
I removed those comments from setters solution. Thanks.
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
You are welcome
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.
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;
}
}
}
why my code is giving error if i am using n=10000001 instead of n=1e7+1(by this code has been submitted successfully).
Here’s my code:
#include
#include <bits/stdc++.h>
#define ll long long
#define loopi(s,n) for(int i=s;i<n;i++)
#define loopd(s,n) for(int i=n-1;i>=s;i–)
#define pi pair<int,int>
#define vi vector
#define n 10000001 // giving error on using this but submitted successfully if n=1e7+1 is taken.
using namespace std;
vector prime(n,1);
vector arr(n,1);
void sieve()
{
for(int i=2;i<=n;i++)
{
if(prime[i])
{
for(int j=2*i;j<=n;j+=i)
prime[j]=0;
}
}
int curr=0;
arr[0]=arr[1]=0;
for(int i=2;i<=n;i++)
{
curr+=prime[i];
arr[i]=curr;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
sieve();
while(t--)
{
int x,y;
cin>>x>>y;
cout<<(y-x)-(arr[y]-arr[x+1])<<endl;
}
return 0;
}
He has written 10000001 viz., 1e7 + 1.