CHEFMGX - Editorial

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;

}

Tell me you never used Fast IO.

He has written 10000001 viz., 1e7 + 1.

1 Like

I have already tried with FAST IO but it showed the same TLE error.

Paste a link to the submission you’re referring to.

If you’re referring to this vs this: both have out-of-bounds accesses on the sample test input:

[simon@simon-laptop][08:16:35]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh 
Compiling abheeshek-CHEFMGX-ac.cpp
Executing command:
  g++ -std=c++17 abheeshek-CHEFMGX-ac.cpp -O3 -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG    -fsanitize=undefined -ftrapv
Successful
[simon@simon-laptop][08:18:38]
[~/devel/hackerrank/otherpeoples]>echo "4
2 10
5 12
34 43
57 63
" | ./a.out
/usr/include/c++/7/debug/vector:417:
Error: attempt to subscript container with out-of-bounds index 10000001, but 
container only holds 10000001 elements.

Objects involved in the operation:
    sequence "this" @ 0x0x56034bbdcf40 {
      type = std::__debug::vector<int, std::allocator<int> >;
    }
Aborted (core dumped)

The fact that either of them got AC is a fluke.

1 Like

And there is one more thing we should notice is that every single query about \text{WA} or \text{RTE} or even \text{TLE} posted have an out-of-bounds access - because of the Setter’s solution.

@ajit123q can you please update the Setter’s solution? It has out-of-bound access in the Sieve function. If unsure, replace the Setter’s solution with the following.

Setter's Code, edited
#include<bits/stdc++.h>
using namespace std;

#define ll long long int

ll prime[10000004] = {0};


void sieve()
{
    ll n=10000004;
    prime[1]=1;
    for(ll i=2;i<n;i++) // a change is here
    {
            for(int j=2;i*j<n;j++) // another change
            {
                prime[j*i]=1;
            }
    }
}

ll prime_in_range[10000004];

// Function to count primes in range.
void count_prime()
{
    prime_in_range[0] = 0;
    prime_in_range[1] = 0;
    prime_in_range[2] = 1;
    
    for(int i=3 ; i<10000004 ; i++) // another change
    {
        if(prime[i] == 0)  // if the number if prime
        {
            prime_in_range[i] = prime_in_range[i-1] + 1;
        }
        else
        {
            prime_in_range[i] = prime_in_range[i-1];
        }
    }
}


int main()
{
    // freopen("input2.txt","r",stdin);
    // freopen("output2.txt","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll t;
    cin>>t;
    
    sieve();
    count_prime();
    
    while(t--)
    {
        ll x,y;
        cin>>x>>y;
        
        cout << y - x - (prime_in_range[y]-prime_in_range[x+1])<<"\n";
    }
}
2 Likes

you used the vector of size 1e8, and we can not complete 10^8 iteration in 1 second time and as @ramandeep8421 said, no need to compute primes in between every time, pre-compute it beforehand

1 Like

why its out-of-bounds access?

vector<int> prime(n,1);
// ... snip ...
 for(int j=2*i;j<=n;j+=i)
                prime[j]=0;
1 Like

My Python code passes one set of tests, but runs into TLE for the other. Can anyone tell me what is causing this please? - can’t seem to figure it out!

My Solution: Solution: 54048657 | CodeChef

Thanks ssjgz, but I want to post a solution that I didn’t submit during the contest- how can I do this? Because my link is to this solution.

1 Like

Please someone tell me why my code goes wrong for 2nd testcase :cry:
@ssjgz @shivyyy_21 @mexomerf @ajit123q @ramandeep8421

https://www.codechef.com/viewsolution/54054122

Completely random test input on which your solution fails:

1
3364 4888

Sorry - only just saw your edit!

You can find all your submissions to the Practice version of the Problem here:

Perfect, thank you. For future reference, how do I get to this page from the contest? Do I just look up the name of the problem?

Click “My Submissions” from the Problem page. The Practice and Contest pages are linked at the top of the first post of this thread.

1 Like