Of course you can do precalculation and AC with Python But it is really hard to AC with Python with "online" calculation Use probability P(i,j) that a line with i rockets is finished after at most j salvos. The probability that it ends after exactly k+1 salvos is P(i,k+1)-P(i,k) = 1/i sum_l P(l,k) * P(r,k) - P(l,k-1) * P(r,k-1), where l is the index of the first launched rocket and thus the size of the left part and r is the size of the right part (r=i-1-l) of the line. The output is with cout << setprecision(12) << s*10 << endl; Edited by author 27.03.2014 23:04 I tried to solve it with (dp[i] = sum_j(max(dp[j - 1], dp[i - j])) + 10) formula, but the way of getting the math expectation as max(dp[A], dp[B]) isn't right. Ho to do it? What is the formula..? please, help me... :( Add one more dimension to your DP oough, I still cant get it. What is the 2nd dimension? I divide the current line(C) to A and B... I really cant understand what else should I know or do to calc C. What else? You should actually know what is max you're trying to find expectation of! I'm again and again experiencing WA#6. Can you help me? If you got AC, please, share the correct answers to some tests. N = 7 N = 8 N = 9 N = 10 N = 19 N = 20 N = 399 N = 400 Your idea is not correct. I have WA#6 too. N=7; ans = 38.0; N=8; ans = 42.6666; N=9; ans = 46.69841269841; N=10; ans = 50.1746031746; Try think about 2-parameters DP p[n][k]. How ans for N=400? N = 400 ANS = 184.652746446 Edited by author 10.10.2010 02:19 Thank you, vgu, your tests helped a lot. How ans for N=6? 33.333333333 Please give tests for N= 20 30 40 50 60 70 80 90 100 WA6 got all the contestants, used dynamic formula f(N) = 1/N * sum(i=0..n-1)max(f(i),f(N-i-1)) + 10 It's incorrect. This formula is almost correct. The following example will illustrate it. Imagine you have two groups of rockets (A and B) and you know, that group A will launch in 10 seconds with probability 1/2, and in 20 seconds with probability 1/2 (math expectation equals 15 in this case). The group B has probabilities 1/3 and 2/3 correspondingly (math expectation = 50/3). But a probability that all rockets will launch in 10 seconds equals 1/2 * 1/3 = 1/6 (it is almost evident), and in 20 seconds: 1 - 1/6 = 5/6. Math expectation = 55/3. So, the only mistake in this formula is M(max(A,B)) != max(M(A),M(B)). Change this, and this fomula will be correct. By the way, I got AC using it. Which of these formulas correct for this problem 1. M(A) + M(B) - M(AB) 2. M(A)*M(B/A) Could you explain what formula is for max(M(A),M(B))? This formula is almost correct. The following example will illustrate it. Imagine you have two groups of rockets (A and B) and you know, that group A will launch in 10 seconds with probability 1/2, and in 20 seconds with probability 1/2 (math expectation equals 15 in this case). The group B has probabilities 1/3 and 2/3 correspondingly (math expectation = 50/3). But a probability that all rockets will launch in 10 seconds equals 1/2 * 1/3 = 1/6 (it is almost evident), and in 20 seconds: 1 - 1/6 = 5/6. Math expectation = 55/3. So, the only mistake in this formula is M(max(A,B)) != max(M(A),M(B)). Change this, and this fomula will be correct. By the way, I got AC using it. Could you say complexity of yours AC solution? (mine is N^3, so I would like to know is there better ways to solve this problem). I think n^2 is possible. Mine is n^3 too and it works about 0.350s, but there are a lot of 0.031s solutions. I know dp algorithm, but it is too slow - O(N^4). Please explain faster algorithm. Here algorithm O(1): use precalculated array ;) It is possible to use a different DP state and calculate each of N^2 cells in O(N) time (N^3 DP algorithm) I have WA8, N = 17 in this test. Please give answers! Thank you. Edited by author 29.05.2011 13:58 The answer is 68.3998769. Bless! Which of these formulas correct for this problem 1. M(A) + M(B) - M(AB) 2. M(A)*M(B/A) I used dp with two params. dp[n][k] =(sum(i=0..n-1)max(dp[i][k+1], dp[n-i-1][k+1]))/n k is number of salvos ans =10 * dp[n][1]; Edited by author 23.10.2010 02:29 I used dp with two params. dp[n][k] =(sum(i=0..n-1)max(dp[i][k+1], dp[n-i-1][k+1]))/n number of salvos ans =10 * dp[n][1]; Nice. What about initialisation values for array dp, interval for k, and solution explanation? initial params is as follows read n then n = n - 2; dp[0][k] = 0 {k = 1..n} dp[1][k] = k {k = 1..n} k is salvo number Edited by author 23.10.2010 02:29 Can anybody explain me the hint? If we have 3 not launched rockets, why the probability of launching each is 1/3. There are 6 segments, that can be used [1,1] [2,2] [3,3] [1,2] [2,3] [1,3]. I think talk is about Markov chain on sets of disjoint segments. This graph is aciclic => DP is possible |
|