- All Contests
- HourRank 16
- Magic Number Tree
- Discussions

# Magic Number Tree

# Magic Number Tree

ritesxz + 0 comments Editorial solution gives 60% of score :P

nullie + 0 comments 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.

Plastermind + 1 comment How to prove that D(k,n) = 1/(k+2) using two formulas given in the editorial?

xxxxxyyyc + 1 comment [deleted]NiakTheWizard + 0 comments 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).

bqi343 + 2 comments 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?

No more comments

Sort 5 Discussions, By:

Please Login in order to post a comment