We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The time limit is very tight for Python. When calculating the determinant, there is a dilemma between accuracy and speed. One way to optimize is to solve an mod p solution for small values of p. (p=1000003, 1000033,1000037 for example) Then we use the Chinese Remainder Theorem to find the actual value. The correctness is given by the constraint (#spanning trees < 10^18). This method is much faster than using the fraction module or mod a prime > 10^18.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Alex vs Fedor
You are viewing a single comment's thread. Return to all comments →
The time limit is very tight for Python. When calculating the determinant, there is a dilemma between accuracy and speed. One way to optimize is to solve an mod p solution for small values of p. (p=1000003, 1000033,1000037 for example) Then we use the Chinese Remainder Theorem to find the actual value. The correctness is given by the constraint (#spanning trees < 10^18). This method is much faster than using the fraction module or mod a prime > 10^18.