Sort 5 Discussions, By:
Please Login in order to post a comment
Can anyone explain what the deep_sum array does in the problem setter's code
Editorial solution gives 60% of score :P
I have a naive solution which finds all possible game paths, sums there magic numbers and divides by number of paths only passes two submission tests.
I understand why it timeouts and maybe gets errors due to recursion depth, but why result could be incorrect?
I use following code for result:
res = (total_summ * math.factorial(n) // path_count) % (10**9+9)
Python has arbitrary length integers, so this should work. I use integer division, first multiplying and then dividing, because problem states that Em * n! will always be integer.
How to prove that D(k,n) = 1/(k+2) using two formulas given in the editorial?
We could also see this directly as we simply want to count the permutations for which A or B appears before any of the K intermediate nodes.
So consider the function FA, resp. FB, that transforms any permutation into a such a one by swapping the first of the K+2 nodes of the path with A, resp. B. Each permutation in the image of FA/FB has exactly K+2 pre-images so that the image has N!/(K+2) elements.
The set of permutations we want to count is the disjoint union of the images of FA and FB, so that their number is 2*N!/(K+2).
I thought that the probability that a path between two nodes which are separated by nodes would be included in was Then I computed the distance between every two nodes and multiplied them by their corresponding probabilities, including the factor of Why didn't this work?
If it worked then you would say, "Why weak solution passes in Hackerrank?" :P
because that probability can be fraction.
You should not find probability and multiply with n!
check thissolution ,I have done it in similar way and it works
I used modular inverse, which shouldn't result in any errors?
I'll check out your solution :)
EDIT: Unfortunately, my modular inverse function was incorrect.
No more comments