Hi, I'm trying to practice this round, and I don't quite understand the official analysis for problem C.
It says the transition function is as follows > if (K == 0): > dp[K, L] = 0; > else: > dp[K, L] = Σi!=L(dp[K-1, i] + dis[L, i]) / (N-1). However, that seems incorrect for the 3rd input case(The 2nd case is kind of special so I treat it separately) 5 4 2 1 2 1 2 3 2 1 4 2 4 5 1 According to the transition formula above, dp[1][1]=0, dp[1][2]=0.25, dp[1][3]=0.75, dp[1][4]=0.5, dp[1][5]=0.75 dp[2][1]=2.8125, dp[2][2]=3, dp[2][3]=4.375, dp[2][4]=3.1875, dp[2][5]=3.875 according to the analysis, when P = 2, ans = Σi=1to5(dp[2][i]), but the ans is 17.25, obviously much larger than the right answer 5.437500. There must be something missing but everything seems reasonable and intuitive... Could anyone please give me some clues? Thanks. -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/beeefdb4-ee9d-4d81-a578-514e53c80835%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
