| Show all threads Hide all threads Show all messages Hide all messages |
| Python TLE | Mahilewets Nikita [BSUIR] | 1776. Anniversary Firework | 2 Sep 2017 18:49 | 1 |
Python TLE Mahilewets Nikita [BSUIR] 2 Sep 2017 18:49 Of course you can do precalculation and AC with Python
But it is really hard to AC with Python with "online" calculation |
| hint | ASK | 1776. Anniversary Firework | 27 Mar 2014 23:03 | 1 |
hint ASK 27 Mar 2014 23:03 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 |
| give me a hint, please... | BORODA | 1776. Anniversary Firework | 2 Feb 2014 04:02 | 4 |
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! |
| cannot get the meaning, sigh. | hliu20 | 1776. Anniversary Firework | 3 Jun 2013 09:28 | 1 |
|
| WA# 6 | Artem Khizha [DNU] | 1776. Anniversary Firework | 9 Nov 2011 03:17 | 12 |
WA# 6 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 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 Artem Khizha [DNU] 10 Oct 2010 02:00 N = 400
ANS = 184.652746446
Edited by author 10.10.2010 02:19 Re: WA# 6 Artem Khizha [DNU] 10 Oct 2010 02:04 Thank you, vgu, your tests helped a lot. Please give tests for N=
20
30
40
50
60
70
80
90
100 Re: WA# 6 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. 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 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 Amirbekov Artem[Ivanovo SPU] 9 Nov 2011 03:17 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. |
| Complexity | AT1 | 1776. Anniversary Firework | 9 Oct 2011 23:54 | 2 |
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. |
| Please explain algo faster than N^4 | Vasily Slesarev | 1776. Anniversary Firework | 8 Sep 2011 11:04 | 4 |
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) |
| give answers for N= 11, 12, 13, 14, 15, 16, 17 | Vasily Slesarev | 1776. Anniversary Firework | 18 Aug 2011 22:52 | 2 |
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? | Ibragim Atadjanov (Tashkent U of IT) | 1776. Anniversary Firework | 27 Oct 2010 16:24 | 1 |
Which of these formulas correct for this problem
1. M(A) + M(B) - M(AB)
2. M(A)*M(B/A) |
| 2 admins : Minor typo in russian statement | 2rf | 1776. Anniversary Firework | 25 Oct 2010 02:39 | 2 |
|
| help wa6 | Ibragim Atadjanov (Tashkent U of IT) | 1776. Anniversary Firework | 23 Oct 2010 02:18 | 3 |
help wa6 Ibragim Atadjanov (Tashkent U of IT) 22 Oct 2010 12:28 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 Re: help wa6 Oleg Strekalovsky [Vologda SPU] 22 Oct 2010 18:57 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? Re: help wa6 Ibragim Atadjanov (Tashkent U of IT) 23 Oct 2010 02:18 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 |
| About Hint | SuperLight | 1776. Anniversary Firework | 10 Oct 2010 15:11 | 2 |
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 |
