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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Alex vs Fedor
  5. Discussions

Alex vs Fedor

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 8 Discussions, By:

votes

Please Login in order to post a comment

  • lvsz_
    4 years ago+ 1 comment

    I was working a solution in Racket, but suddenly that language is no longer available?

    1|
    Permalink
  • znie1
    3 years ago+ 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|
    Permalink
  • slbcr
    5 years ago+ 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?

    0|
    Permalink
  • swm_sxt
    5 years ago+ 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.

    0|
    Permalink
  • nazima_firdos
    5 years ago+ 1 comment

    did any one solve this problem ?

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature