Need help with optimization (PRMRANGE)

problem:
https://www.codechef.com/problems/PRMRANGE

mysolution:
https://www.codechef.com/viewsolution/27433034

exceeds time limit
can anyone tell me where i can optimize?
also list in python isnt the same as an array in C
so i have to initialize the entire list with None (ensuring that it obeys the constraints i.e. a list of 10^5 Nones). So does this initialization cause the time limit to exceed?
any help would be appreciated

Unlikely. What’s the worst case computation complexity of your solution (in terms of, say, Q and the number of elements in the array)?

Some large number might cause the problem imo, most likely in the prime factor determining section? if that’s the case, how do i optimize that? i dont understand the time complexity stuff very well.

Have a play with this testcase and see how long it takes to run, and try to figure out where it’s spending all its time, and why. As a warning, though: this Problem has only a 7% Accuracy Rating, making it one of the harder “Easy” problems.

Edit:

Definitely work on this - it’s absolutely crucial to CP stuff :slight_smile: With practice, you’ll be able to tell that your current solution will TLE before even setting fingers to keyboard :slight_smile:

2 Likes

im not a comp sci student can u recommend any text?

Hmmm … I’m not the best person to offer recommendations, I’m afraid, as I learnt this stuff in my youth which was aeons ago :slight_smile:

It’s been a while since I’ve read Introduction To Algorithms, but I remember it as being very good.

Does anyone else have good recommendations for learning about big-O and how to evaluate it?

2 Likes

thank you:smile:

1 Like