- Prepare
- Algorithms
- Graph Theory
- Alex vs Fedor
- Discussions
Alex vs Fedor
Alex vs Fedor
+ 1 comment I was working a solution in Racket, but suddenly that language is no longer available?
+ 0 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.
+ 0 comments I have been working to implement Kirchhoff's theorem to determine the number of all potential spanning trees. I'm not trying to hard to get the count of minimum spanning trees until I have the total count working. My code produces minors and recursively finds determinants for these minors. I have the code working and getting good test results for 3x3 matrices and 4x4 matrices. I bought the input and expected output for test 01. For this test case there are 10 nodes and 20 edges. I create the initial 10x10 Laplacian matrix, arbitrarily strip the first row and column and send the resulting submatrix to my recursive routine to find the determinant based on all the subsidiary matrices and determinants. For test case 01, my result is 14183. The expected count is 9247. So I'm almost the right order of magnitude. (Any prizes for that?)
Does anyone have any suggestions on how to breakdown and analyze this problem?
+ 1 comment This problem is strict about accuracy.I used "long double" in c++14 at first and got wrong answer.When I changed it into "__float128",I got accept.
+ 1 comment did any one solve this problem ?
Sort 8 Discussions, By:
Please Login in order to post a comment