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.

I had the correct algorithm, but was getting failure on test 3. Now that I fixed the problem, I realize that the issue was all due to not handling the integer division with enough precision for the larger N values. To get around that, I used the python fraction library. Here's the code:

fromfractionsimportFractionfrommathimportfloordefcompute_outcomes(n):outcomes=[0]*(n+1)outcomes[-1]=1outcomes[-2]=1#outcomes represents values of outcome tree after i turnsforiinrange(2,n+1):#looping through levels i of treeforjinrange(n):outcomes[j]=outcomes[j+1]#number of ways to get to given node is above right node plus i*(above left node) outcomes[n]=0#far right node initialized to 0 since only contribution is from above left nodeforjinrange(n,0,-1):#not including node 0 since it doesn't have contribution from above leftoutcomes[j]+=outcomes[j-1]*i;#contribution from above left node of treereturnoutcomesdefcompute_price(outcomes):n=len(outcomes)-1k=(n+1)//2returnFraction(sum(outcomes),sum(outcomes[:k]))T=int(input())forjinrange(T):N=int(input())outcomes=compute_outcomes(N)s=compute_price(outcomes)print(floor(s))

Cookie support is required to access HackerRank

Seems like cookies are disabled on this browser, please enable them to open this website

## Project Euler #121: Disc game prize fund

You are viewing a single comment's thread. Return to all comments â†’

I had the correct algorithm, but was getting failure on test 3. Now that I fixed the problem, I realize that the issue was all due to not handling the integer division with enough precision for the larger N values. To get around that, I used the python fraction library. Here's the code: