TLE in CHEFMGX

help
1

Can someone please point out why my solution for CHEFMGX isn’t working? It keeps giving TLE.

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

1 Like
2

No need to compute the sieve portion every time,it will cause TLE.

do it before all test cases.

2 Likes
3

the optimal way is
it1 = upper_bound of Y on prime numbers
it2 = upper_bound of X+1 on prime numbers.
ans = Y-X-distance(it1,it2).

1 Like
4

There are 3 cases .
vectorans, primes
calculate before hand by simple dp formula…
if(x%2)
cout<<ans[y]-ans[x]<<endl;
else {
if(prime[x+1])
cout<<ans[y]-ans[x]+1<<endl;
else
cout<<ans[y]-ans[x]<<endl;
}

5

Making a sieve was the right move. But you are using a loop from the initial step to the last step. You yourself must have noticed that this is unnecessary.
You can optimize it by making a prefix array PREFIX whose PREFIX[i] will store the number of prime numbers encountered up till now. You need to pre-compute these things i.e., before entering the test cases.

Now that you have the PREFIX array with yourself, you can find number of steps in O(1) for each test case.
You can calculate it by the formula: total number of steps from x to y minus prime numbers between them. (y-x - (PREFIX[y] - PREFIX[x+1]))

6

oopss , now I get why I was getting TLE.

7

you have to use sieve of eratosthenes and pre computation. answer to each query is to be given in consant time and most important use fast io. I did everything right but forget fast io and was getting tle, after using fast io solution got accepted in 0.22sec.

You can see my solution it may help you:
https://www.codechef.com/viewsolution/52758057

Thank You

8

I also did the same.
Why am I getting TLE?
https://www.codechef.com/viewsolution/52760623

9

we can also use binary search in each tc to find number of primes btw.

10

Thanks a lot! I got it now.

11

Thanks

12

Sounds interesting. I cannot understand how to apply binary search in this, though.
Could you please share your approach using binary search? Getting to know how to solve the problem in a different way will help a lot.
Thanks in advance!

13

i have calculated all prime btw 1 to 1e7 and stored them in a array( they are in sorted order)
now using upper_bound we can find index where first prime is greater or equal to x .
same goes for y
Now, number of Primes bt index say ix and iy is simply iy-ix (with handling edge cases ofc)
link to my code:-CodeChef: Practical coding for everyone
feel free to ask any doubt!! :slight_smile:

14

You have used Pyhton. Its a slow language. I dont know much about Python, I prefer using C++ for CP. In C++ we had to use fast io to get AC. I think you should start practicing in C++, because in questions having very tight time constraints, C++ will help you.

15

This was nice!
Thankyou for sharing your solution :slight_smile:

1 Like
16

I am getting TLE too, even after following everything.
Please help.
https://www.codechef.com/viewsolution/53286071