Sardar & GCD runtime error

1

I can’t figure out any reason for runtime error in my solution: CodeChef: Practical coding for everyone

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!

2

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

1 Like
3

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

4

You are most likely correct, got TLE with recursion limit on the same code. CodeChef: Practical coding for everyone

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

1 Like
5

… or maybe it’s this :slight_smile:

1 Like
6

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

7

If you say so :slight_smile:

8

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