ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1776. Anniversary Firework

WA# 6
Posted by Artem Khizha [DNU] 9 Oct 2010 20:35
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
Posted by Artem Khizha [DNU] 10 Oct 2010 02:00
N   = 400
ANS = 184.652746446

Edited by author 10.10.2010 02:19
Re: WA# 6
Posted by Artem Khizha [DNU] 10 Oct 2010 02:04
Thank you, vgu, your tests helped a lot.
Re: WA# 6
Posted by olpetOdessaONU [1 2/3] 10 Oct 2010 14:48
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
Posted by bsu.mmf.team 10 Oct 2010 16:47
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
Posted by bsu.mmf.team 11 Oct 2010 18:47
33.333333333
Re: WA# 6
Posted by Ibragim Atadjanov (Tashkent U of IT) 27 Oct 2010 16:20
Which of these formulas correct for this problem
1. M(A) + M(B) - M(AB)
2. M(A)*M(B/A)
Re: WA# 6
Posted by Vasily Slesarev 21 May 2011 16:02
Please give tests for N=
20
30
40
50
60
70
80
90
100
Re: WA# 6
Posted by Amirbekov Artem[Ivanovo SPU] 9 Nov 2011 03:17
Could you explain what formula is for max(M(A),M(B))?
bsu.mmf.team wrote 10 October 2010 16:47
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.