Sardar & GCD runtime error

I can’t figure out any reason for runtime error in my solution: Solution: 53456590 | CodeChef

Pretty sure algorithm is correct, using DP (memoization) to compute gcd of the two subtrees split up by deleting edge (a, b)

Would also love it if I can reproduce the error in a custom test case, but so far not successful. Any help would be much appreciated!

Stack overflow, perhaps (Python is not my language :)) ? Have you tried setting the recursion limit to something high?

1 Like

Look like recursion limit error. Set “sys.setrecursionlimit” to 10**5 or more.

You are most likely correct, got TLE with recursion limit on the same code. Solution: 53456806 | CodeChef

I’ll try doing the DP without function calls, maybe python function calls have too much overhead.

1 Like

… or maybe it’s this :slight_smile:

1 Like

It is definitely O(N) due to memoization. The number of calls to the recursive function get_gcd() is linear in number of edges.

If you say so :slight_smile:

Never mind, for star graphs there is an issue. Basically nodes with lots of neighbors. The algorithm maybe O(sum degree**2) complexity. Which is O(N) only if degrees are small.

1 Like