Why I am getting TLE in O(n.sqrt(maxA)) approach in Python.

problem link:

https://www.codechef.com/OCT19B/problems/MSV

my solution:

(https://www.codechef.com/viewsolution/27169662)

Why I am getting TLE in O(n.sqrt(maxA)) approach in Python.

problem link:

https://www.codechef.com/OCT19B/problems/MSV

my solution:

(https://www.codechef.com/viewsolution/27169662)

I have not seen your code but If you are pretty sure that there is no other error and time complexity is tolerable then I suggest you to try some other programming language with same algorithm. Like C++, C or JAVA.

I once submitted solution on hacker rank in python which was giving TLE (taking around 13 seconds locally) and then I analysed my algorithm once again which I thought should be executed within time limit.

So I rewrote the same in C++ and it got excepted in time much lower than required time limit.

I think you should calculate sqrt out of the loop…

Because you are calculating sqrt for each iteration.

Yeah i know, these things happens with my friend too. … . .so i suggest please use c++ or java as much as possible , (python ka kuch nhi kah skte) ,tomorrow is icpc , so i suggest use java / c++

TRY your code in pypy3

https://www.codechef.com/viewsolution/27137279 (MY FRIEND’s CODE)

Try once list instead of dictionary as you do in java.

may be its because heavy data structure.

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

here u go i copied your code and paste in lang pypy i accepted

sometimes , instead of python we have to submit in pypy

Yes bro it is better but it depends on constraints that’s why i use dictionary

look at this just submitted same code in pypy got AC

Link

Read your solution but did’t got it.

Here is is my solution.

Initialize factors_cnt as 0, this will keep track of the number of elements divisible by the index at which the number is located. Factors_cnt is going to store the star value of cur element. How, I will answer that part later.

Iterate through input list and first check how many elements before cur element is divisible by cur element.

How would you that? For that we have factors_cnt, factors_cnt[cur_element] is the number of elements which are divisible by cur element.

Now once we have found cur element star value, the cur element is also divisible by it’s factors. Now find it’s factors and increase their count at factor_cnt[factor]++

Go through the solution and you will understand.