CHEFMGX - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Div1
Div2
Div3

Setter: Shivansh Kaushal
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

EASY

PREREQUISITES:

Sieve of Eratosthenes

PROBLEM:

Chef needs to go from X to Y. For this he can consider the following two operations:

Suppose chef is at location C. Now he can

  • Go from C to C+1 in one step

  • Go from C to C+2 in one step if C+2 is prime.

We need to find the minimum number of steps to go from X to Y.

EXPLANATION:

  • If the move C to C+2 is possible, we must always prefer this rather than going from C \rightarrow C+1 \rightarrow C+2 because it always saves us one step.

  • Let us find the number of prime numbers P \leq Y for which P-2 \geq X. Let this value be tot.

  • Whenever we want to go to such P we will prefer the second operation, i.e going from P-2 to P directly using one step.

  • Therefore, our final answer will be Y-X-tot .

  • We can precompute the number of primes from 1 to N using the sieve method. From this information, we can easily calculate the number of primes in a range in O(1) time.

TIME COMPLEXITY:

O(N \log \log N) where N =10^7 for performing sieve.

SOLUTION:

Editorialist's solution 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e7;
bool prime[MAXN + 5];
int tot_primes_till[MAXN + 5];

void sieve()
{
     int n = MAXN;
     fill(begin(prime), end(prime), true);
     prime[0] = prime[1] = false;

     for (int i = 2; i <= n; i++)
     {
          tot_primes_till[i] = tot_primes_till[i - 1];

          if (!prime[i])
               continue;

          tot_primes_till[i]++;

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

int main()
{
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     cout.tie(NULL);

     sieve();
     int tests;
     cin >> tests;

     while (tests--)
     {
          int X, Y;
          cin >> X >> Y;

          int ans = Y - X - (tot_primes_till[Y] - tot_primes_till[X + 1]);

          cout << ans << "\n";
     }
}
Setter's solution 
#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++)
    {
            for(int j=2;i*j<=n;j++)
            {
                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++)
    {
        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";
    }
}
Tester's solution 
#include <bits/stdc++.h>
using namespace std;
#define N 10000001
int main()
{
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     cout.tie(NULL);
     vector<int> p(N);
     for (int i = 2; i < N; i++)
     {
          p[i] = 1 - p[i];
          if (p[i])
          {
               for (int j = 2 * i; j < N; j += i)
               {
                    p[j] = 1;
               }
          }
          p[i] += p[i - 1];
     }
     int t;
     cin >> t;
     while (t--)
     {
          int x, y;
          cin >> x >> y;
          cout << y - x - p[y] + p[x + 1] << "\n";
     }
     return 0;
}

Please comment below if you have any questions, alternate solutions, or suggestions. :slight_smile:

4 Likes
2

Need python solution.

2 Likes
3

Why My Solution Giving TLE In Second Testcase :frowning:

Here is my code:

#include<bits/stdc++.h>
#define flash ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long int
#define md 10000001
using namespace std;

bool prime[md];
void SieveOfEratosthenes()
{
memset(prime, true, sizeof(prime));
for (int p=2;p*p<=md;p++)
{
if (prime[p] == true)
{
for (int i = p * p; i <= md; i += p)
prime[i] = false;
}
}
}

int rec(int x,int y){
if(x>=y)
return 0;
if(prime[x+2])
return 1+rec(x+2,y);
else
return 1+rec(x+1,y);
}

void solve(){
int x,y;
cin>>x>>y;
int cnt=rec(x,y);
cout<<cnt<<"\n";
}

int32_t main(){
flash;
SieveOfEratosthenes();
int tc;
cin>>tc;
while(tc–)
{
solve();
}
}

4

Try using “long long” instead of “int” in the for loops in the function “SieveOfEratosthenes()”.
For large value of p (like 1e5), storing p*p as integer will cause integer overflow.

5

Can Anyone help me to optimize my logic

Solution Link : CodeChef: Practical coding for everyone

6

That’s a baseless advice. He has written p * p <= md, where md = 10000001. This will not cause overflow in any case.

1 Like
7

Yours is an O(T\times (Y - X)) Solution which will timeout for given Constraints. You can go through the editorial for a better understanding.

1 Like
8

Declaring a global array of size 1e7 was causing some runtime error in my PC. What can be the reasons and how to correct that . I am using c++.

9

In the Setter’s solution, the size of Array is around 10^6, but the constraints mentioned were N\le10^7. Is it that the setter’s solution was provided for a reference, or the tests were generated based on this solution?

10

If you’re using Linux, you can refer to this.

Edit: There’s a Codeforces topic on this.

11

I have already defined int as long long globally (see code line number 3).

12

Ok thanks .
Is this approach correct for smaller constraints?

13

It would pass for the following constraints.

1\le (T\times (Y - X))\le10^7.

Like this: 1\le T\le10^4 and 1\le X\lt Y\le10^3
or this: 1\le T\le10^6 and 1\le X\lt Y\le10
or even this: 1\le T\le 10 and 1\le M\lt N \le 10^6.

1 Like
14

Can someone clear my doubt? Is the while loop giving me TLE or the sieve? :thinking:

Solution: 52710238 | CodeChef

15

The time Complexity of your code is O(Y - X) per test case. You should do it in O(1) per test case.

1 Like
16

Hey previously the contraints were 10^6 but later increased to 10^7. Thanks for pointing this out. I have updated the setter’s solution.

1 Like
17

Consider the following lines of code.

int INF = 1000000007;

int a = 999999;
int b = 999999;

int product = a*b;

if(product <= INF){
    cout << "a*b is less than or equal to INF";
}else{
    cout << "a*b is greater than INF";
}

If we calculate a*b with a calculator, it will be 999998000001.

So, we can expect the program to print “a*b is greater than INF”, as with no doubt 999998000001 is greater than 1000000007.

But the above program actually prints “a*b is less than or equal to INF”.

It is because, “a” and “b” are declared as integers, so “a*b”, will also be stored as an integer but their product “999998000001” exceeds the limit of integers, and therefore cause integer overflow.

So instead of “999998000001”, product will store “-729379967”.

This is what I meant, when I said “storing p*p as integer will cause integer overflow”.

But he has defined “int” as “long long int” in his code, so, this integer overflow is out of question.

1 Like
18

Thanks for your help.
I had one doubt if you could help with that.
Difference between this code and this one is just ll ans =
Why is one giving TLE and other doesn’t? Do we have to be this cautious everytime??

1 Like
19

You do not need to compute the dp fr every test case, just precompute it along with the sieve for the upper bound like 100001 ,you can refer my solution https://www.codechef.com/viewsolution/52737884

20

Yes, its the while loop that is giving you TLE , you need to precompute the number of minimum steps upto 10000011 in an prefix array such that prefix[N] is the minimum steps to reach N from 1 , then rest is case work , here is my implementation https://www.codechef.com/viewsolution/52737884

1 Like