TLE with an O(n sqrt(n)) n <= 200000. C++ optimizations needed.

Правка en3, от proofbycontradiction, 2018-12-06 11:06:47

I was solving this interesting number-theory + trees problem. And I came up with an solution where n ≤ 200000.

My idea is that the answer for every node will either be a factor of the root or be a factor of the number itself, and only these about values need to be tested.

However, this submission am getting TLE with this idea. The solution in the editorial is a slight optimization of my idea -
(a) either the answer is a factor of the root (because root is NOT marked as 0)
(b) or it's the GCD of all the ancestors except the root (because the root IS marked as 0).

This has the complexity of O(n * k) where k =  number of factors of the root value, and . Thus the editorial solution and my solution have the same (theoretical) complexity.

Could you suggest was that are C++ implementation optimizations that I could use to improve my solution and avoid the TLE even though I am testing out both factors of root and factors of the node? I did try to cache the values of the root and the node, but that leads to a stack overflow.

I am not looking for the obvious optimizations of implementing the editorial solution.

Теги c++, number theory, trees, optimization

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский proofbycontradiction 2018-12-06 11:06:47 214 (published)
en2 Английский proofbycontradiction 2018-12-06 10:57:24 814
en1 Английский proofbycontradiction 2018-12-06 10:50:51 411 Initial revision (saved to drafts)