|
|
back to boardWA# 6 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 Re: WA# 6 Posted by vgu 9 Oct 2010 20:42 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]. Re: WA# 6 Posted by r1d1 10 Oct 2010 01:02 How ans for N=400? Re: WA# 6 N = 400
ANS = 184.652746446
Edited by author 10.10.2010 02:19 Re: WA# 6 Thank you, vgu, your tests helped a lot. Re: WA# 6 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. Re: WA# 6 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. Re: WA# 6 Posted by Proba 11 Oct 2010 12:19 How ans for N=6? Re: WA# 6 Which of these formulas correct for this problem
1. M(A) + M(B) - M(AB)
2. M(A)*M(B/A) Re: WA# 6 Please give tests for N=
20
30
40
50
60
70
80
90
100 Re: WA# 6 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. |
|
|
