| ENG RUS | Timus Online Judge |
Обсуждение задачи 1776. Праздничный фейерверкMahilewets Nikita [BSUIR] Python TLE // Задача 1776. Праздничный фейерверк 2 сен 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 ASK hint // Задача 1776. Праздничный фейерверк 27 мар 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 BORODA give me a hint, please... [3] // Задача 1776. Праздничный фейерверк 31 янв 2014 23:16 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... :( Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: give me a hint, please... [2] // Задача 1776. Праздничный фейерверк 1 фев 2014 03:13 Add one more dimension to your DP BORODA Re: give me a hint, please... [1] // Задача 1776. Праздничный фейерверк 2 фев 2014 00:11 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. Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: give me a hint, please... // Задача 1776. Праздничный фейерверк 2 фев 2014 04:02 What else? You should actually know what is max you're trying to find expectation of! hliu20 cannot get the meaning, sigh. // Задача 1776. Праздничный фейерверк 3 июн 2013 09:28 Artem Khizha [DNU] WA# 6 [11] // Задача 1776. Праздничный фейерверк 9 окт 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 vgu Re: WA# 6 [6] // Задача 1776. Праздничный фейерверк 9 окт 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]. r1d1 Re: WA# 6 [1] // Задача 1776. Праздничный фейерверк 10 окт 2010 01:02 How ans for N=400? Artem Khizha [DNU] Re: WA# 6 // Задача 1776. Праздничный фейерверк 10 окт 2010 02:00 N = 400 ANS = 184.652746446 Edited by author 10.10.2010 02:19 Artem Khizha [DNU] Re: WA# 6 // Задача 1776. Праздничный фейерверк 10 окт 2010 02:04 Thank you, vgu, your tests helped a lot. Proba Re: WA# 6 [2] // Задача 1776. Праздничный фейерверк 11 окт 2010 12:19 How ans for N=6? bsu.mmf.team Re: WA# 6 [1] // Задача 1776. Праздничный фейерверк 11 окт 2010 18:47 33.333333333 Vasily Slesarev Re: WA# 6 // Задача 1776. Праздничный фейерверк 21 май 2011 16:02 Please give tests for N= 20 30 40 50 60 70 80 90 100 olpetOdessaONU [1 2/3] Re: WA# 6 [3] // Задача 1776. Праздничный фейерверк 10 окт 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. bsu.mmf.team Re: WA# 6 [2] // Задача 1776. Праздничный фейерверк 10 окт 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. Ibragim Atadjanov (Tashkent U of IT) Re: WA# 6 // Задача 1776. Праздничный фейерверк 27 окт 2010 16:20 Which of these formulas correct for this problem 1. M(A) + M(B) - M(AB) 2. M(A)*M(B/A) Amirbekov Artem[Ivanovo SPU] Re: WA# 6 // Задача 1776. Праздничный фейерверк 9 ноя 2011 03:17 Could you explain what formula is for max(M(A),M(B))? bsu.mmf.team писал(a) 10 октября 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. AT1 Complexity [1] // Задача 1776. Праздничный фейерверк 14 сен 2011 07:25 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). ValenKof Re: Complexity // Задача 1776. Праздничный фейерверк 9 окт 2011 23:54 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. Vasily Slesarev Please explain algo faster than N^4 [3] // Задача 1776. Праздничный фейерверк 21 май 2011 15:51 I know dp algorithm, but it is too slow - O(N^4). Please explain faster algorithm. AterLux Re: Please explain algo faster than N^4 [1] // Задача 1776. Праздничный фейерверк 23 май 2011 12:16 Here algorithm O(1): use precalculated array ;) Vasily Slesarev Re: Please explain algo faster than N^4 // Задача 1776. Праздничный фейерверк 23 май 2011 20:16 Thank you) Jonathan Paulson Re: Please explain algo faster than N^4 // Задача 1776. Праздничный фейерверк 8 сен 2011 11:04 It is possible to use a different DP state and calculate each of N^2 cells in O(N) time (N^3 DP algorithm) Vasily Slesarev give answers for N= 11, 12, 13, 14, 15, 16, 17 [1] // Задача 1776. Праздничный фейерверк 23 май 2011 20:35 I have WA8, N = 17 in this test. Please give answers! Thank you. Edited by author 29.05.2011 13:58 Nily Re: give answers for N= 11, 12, 13, 14, 15, 16, 17 // Задача 1776. Праздничный фейерверк 18 авг 2011 22:52 The answer is 68.3998769. Bless! Ibragim Atadjanov (Tashkent U of IT) Which of these formulas correct for this problem? // Задача 1776. Праздничный фейерверк 27 окт 2010 16:24 Which of these formulas correct for this problem 1. M(A) + M(B) - M(AB) 2. M(A)*M(B/A) 2rf 2 admins : Minor typo in russian statement [1] // Задача 1776. Праздничный фейерверк 25 окт 2010 01:46 фейреверк -> фейерверк Sandro (USU) Fixed (-) // Задача 1776. Праздничный фейерверк 25 окт 2010 02:39 Ibragim Atadjanov (Tashkent U of IT) help wa6 [2] // Задача 1776. Праздничный фейерверк 22 окт 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 Oleg Strekalovsky [Vologda SPU] Re: help wa6 [1] // Задача 1776. Праздничный фейерверк 22 окт 2010 18:57 Ibragim Atadjanov (Tashkent U of IT) писал(a) 22 октября 2010 12:28 I used dp with two params. Nice.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]; What about initialisation values for array dp, interval for k, and solution explanation? Ibragim Atadjanov (Tashkent U of IT) Re: help wa6 // Задача 1776. Праздничный фейерверк 23 окт 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 SuperLight About Hint [1] // Задача 1776. Праздничный фейерверк 10 окт 2010 12: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]. svr Re: About Hint // Задача 1776. Праздничный фейерверк 10 окт 2010 15:11 I think talk is about Markov chain on sets of disjoint segments. This graph is aciclic => DP is possible
|