CHEFMGX - Editorial

editorial
, , ,
21

Can anyone figure out why my code gives WA for 2nd testcase.
@suman_18733097 @ramandeep8421 @ajit123q @shivyyy_21 @mexomerf

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

22

I don’t understand many things in your code. In your previous code, the implementation of Sieve is lightning fast. What you messed up is the actual solution part.

In the other submission, Sieve is taking too much time. Optimising Sieve should be enough like you did in your previous code.

One thing you can try is to optimise just the Sieve part and submit it. This is based on the fact that your submission that was Accepted has a runtime of 1.94 \text{s}, which is pretty close to 2\text{s}. Using long long should not affect the running time of your solution.

1 Like
23

Can someone help me to optimize my solution?
https://www.codechef.com/viewsolution/52745491

25

#include <bits/stdc++.h>

using namespace std;

#define ll long long int

#define endl “\n”

const int m=1e7;

int pri[m+1];

bool isprime[m+1];

int32_t main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    isprime[1]=false;

for(int i=2;i<=m;i++)

{

   isprime[i]=true;// first assuming all are prime

}

for(int i=2;i<=sqrt(m);i++)

{

   if(isprime[i])

   {

       for(int j=i*i;j<=m;j+=i)

       {

           isprime[j]=false;

       }

   }

}

for(int i=2;i<=m;i++)

{

   if(isprime[i])

   pri[i]=pri[i-1]+1;

   else

   {

      pri[i]=pri[i-1];

   }

}

    int t;

    cin>>t;

    while(t--)

    {

    

    int x,y;

    cin>>x>>y;

    int total;

    int ans;

       

  if(x%2==0)

{ total= pri[y]-pri[x+1];

 ans=y-x-total;

}

 else

 {

    total=pri[y]-pri[x];

    ans=y-x-total;

 }

 cout<<ans<<endl;

 

    }

}

why this is getting wrong

26

You’re talking crap. There will not be any integer overflow even if he doesn’t write the line #define int long long int.

Reason: The following loop will break as soon as p * p exceeds md. So, the control will not enter the nested for loop.

for(int p = 2; p * p <= md; p++)
// md = 10000001
// Max value of p in the loop will be sqrt(md)., viz ~ 3e3

Your explanation for the code you’ve provided is absolutely correct. But,

The value of p will never exceed 1e4, so ** THERE WILL NOT BE ANY OVERFLOW**.

1 Like
27

for x odd why we need to do pri[x+1] ?
pri[x] also work??

28

@suman_18733097

29

Thanks again man. I understood my mistake, the thing is I tried out the sieve used in setter’s solution above :sweat_smile:

30

I have done the same, i.e use sieve to find primes before hand. but it is still giving TLE

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

How can I improve it ?

31

Yeah, you are right. I didn’t gave much attention to “p*p<=md”.
In this case there is not any chance for Integer overflow.

I misunderstood his code.
Thanks for the clarification.

1 Like
32

Please someone help me figure out for which testcase does my code goes wrong!!!

33

Your code’s time complexity O(Y - X) for each test case. O(1) is expected
Refer this

34

@atharvbhadange
Ohh I see,so after finding primes we need to count them too; thanks a lot👍

35

@ajit123q I tried running yours and mine code on the following sample TC:

3
1 2
1 3
2 3

Your gave output 1 1 1 while mine gave output 2 2 2, and both are AC, can you explain what’s going on here? I’m kind of surprised how CodeChef accepted my solution, which is actually wrong!

Your code submission: CodeChef: Practical coding for everyone
My own code submission: CodeChef: Practical coding for everyone

You can try running mine on the sample TC, it will give 2 2 2.

1 Like
36

can u explain whats u did in last part i mean in if-else condition

37

The main observation I used is that whenever we have a condition where x is prime or x + 1 is prime or both are prime (in case of 2,3) then the answer is always pre[y]-pre[x] +1, the additional 1 is added because the number of steps to reach x is same as the ones for x+1. the first three cases account for that, this is valid only when x is not 1 because the number of steps to reach 1 is always 0 as clear from the constraints.
I wrote the sequence used this observation and got an AC.You can verify the same by writing a short sequence and trying various endpoints :slight_smile:

1 Like
38

hey @vrintle For this paricular question the main focus was on second test file , which has 10^6 test cases with X and Y ranging from 1 to 10^7 and its not possible to include every possible test case between 1 to 10^7 within 10^6 range of cases.

39

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

This was my code

40

I have done it in O(logN) per test case.
You can check my solution here

41

here is my python accepted solution.
Link : CodeChef: Practical coding for everyone

i use the same sieve method.