problem:
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 
With practice, you’ll be able to tell that your current solution will TLE before even setting fingers to keyboard
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
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?
thank you:smile: