| ENG RUS | Timus Online Judge |
Discussion of Problem 1817. Merry-go-roundFelix_Mate I understand test // Problem 1817. Merry-go-round 25 Sep 2016 12:55 Let n=4 and i-1=2. Why ans is 0.687500? We have 6 variants: (carousel moves to the "left") 0011 => Waiting time = 0+0+2+1=3 Conditional expectation(0011) = 0*(1/4)+0*(1/4)+2*(1/4)+1*(1/4)=3/4 Probality(0011)=(1/4)*(2/4)+(1/4)*(1/4)=3/16 0101 => Waiting time = 0+1+0+1=2 Conditional expectation(0101) = 0*(1/4)+1*(1/4)+0*(1/4)+1*(1/4)=2/4 Probality(0101)=(1/4)*(1/4)+(1/4)*(1/4)=2/16 0110 => Waiting time = 0+2+1+0=3 Conditional expectation(0110) = 0*(1/4)+2*(1/4)+1*(1/4)+0*(1/4)=3/4 Probality(0110)=(1/4)*(1/4)+(1/4)*(2/4)=3/16 1001 => Waiting time = 1+0+0+2=3 Conditional expectation(1001) = 1*(1/4)+0*(1/4)+0*(1/4)+2*(1/4)=3/4 Probality(1001)=(1/4)*(1/4)+(1/4)*(2/4)=3/16 1010 => Waiting time = 1+0+1+0=2 Conditional expectation(1010) = 1*(1/4)+0*(1/4)+1*(1/4)+0*(1/4)=2/4 Probality(1010)=(1/4)*(1/4)+(1/4)*(1/4)=2/16 1100 => Waiting time = 2+1+0+0=3 Conditional expectation(1100) = 2*(1/4)+1*(1/4)+0*(1/4)+0*(1/4)=3/4 Probality(1100)=(1/4)*(2/4)+(1/4)*(1/4)=3/16 ans = Expected value = Sum(Conditional expectation(mask) * Probality(mask)) ans = (3/4)*(3/16)+(2/4)*(2/16)+(3/4)*(3/16)+(3/4)*(3/16)+(2/4)*(2/16)+(3/4)*(3/16)=(3/4)*(3/16)*4+(2/4)*(2/16)*2=3*(3/16)+2*(2/16)=11/16. Edited by author 21.06.2017 12:40 72VanVector[SevNTU] Is the test case correct??? [14] // Problem 1817. Merry-go-round 30 Jan 2011 13:19 consider the test case in problem statement. Will the kid really wait for 0.6875 sec, when 2 kids are riding merry-go round?? Mb this value should be 0.625 = 5/8??? Edited by author 30.01.2011 13:22 Samsonov Alex [USU] Re: Is the test case correct??? [13] // Problem 1817. Merry-go-round 30 Jan 2011 13:30 The test case is correct. waterlink Re: Is the test case correct??? [12] // Problem 1817. Merry-go-round 30 Jan 2011 14:13 it seems to be wrong at all there are 6 posibilities in this hypothesis (there are 2 childrens) they are: 1100 - 2 1010 - 1 1001 - 1 0110 - 0 0101 - 0 0011 - 0 so, the posibility must be 2*1/6 + 1*1/6 + 1*1/6 = 0.66666667 isn't it right?? Edited by author 30.01.2011 14:15 _________________________________________ test case is right. there are sub-hypothesis with different posibilities Edited by author 30.01.2011 14:54 72VanVector[SevNTU] Re: Is the test case correct??? // Problem 1817. Merry-go-round 30 Jan 2011 14:56 Seems like the possibility of each case isn't equal to 1/6, some of the cases have more then 1/6, others - less. Oleg Topalov Re: Is the test case correct??? [10] // Problem 1817. Merry-go-round 30 Jan 2011 16:19 How did you do that?? Edited by author 30.01.2011 16:45 Alexey Dergunov [Samara SAU] Re: Is the test case correct??? [9] // Problem 1817. Merry-go-round 31 Jan 2011 15:32 Yes, test case is correct. Look: 1010 you can get from 1000 and 0010, p = 2/16 0101 you can get from 0100 and 0001, p = 2/16 But: 1100 you can get from 1000 (2 times!) and 0100, p = 3/16 0110 you can get from 0100 (2 times!) and 0010, p = 3/16 0011 you can get from 0010 (2 times!) and 0001, p = 3/16 1001 you can get from 0001 (2 times!) and 1000, p = 3/16 Thus, we get: p(1100) = 3/16, p(1001) = 3/16, p(1010) = 2/16 And the answer is: (3/16)*2 + (3/16)*1 + (2/16)*1 = 11/16 = 0.6875 Nice problem! rohit Re: Is the test case correct??? [1] // Problem 1817. Merry-go-round 31 Jan 2011 17:14 Alexey Dergunov [Samara SAU] wrote 31 January 2011 15:32 Look: 1010 you can get from 1000 and 0010, p = 2/16 0101 you can get from 0100 and 0001, p = 2/16 But: 1100 you can get from 1000 (2 times!) and 0100, p = 3/16 0110 you can get from 0100 (2 times!) and 0010, p = 3/16 0011 you can get from 0010 (2 times!) and 0001, p = 3/16 1001 you can get from 0001 (2 times!) and 1000, p = 3/16 Can you please explain why for 1010 -> p = 2/16 but 1100 -> p = 3/16 How does 1000 come 2 times in this case ? Alexey Dergunov [Samara SAU] Re: Is the test case correct??? // Problem 1817. Merry-go-round 31 Jan 2011 18:40 1000 -> 1010 if start position = 3 0010 -> 1010 if start position = 1 (2 times) 1000 -> 1100 if start position = 1 1000 -> 1100 if start position = 2 0100 -> 1100 if start position = 1 (3 times) Chabanenko Vlad Re: Is the test case correct??? [1] // Problem 1817. Merry-go-round 1 Feb 2011 21:46 "And the answer is: ... + (3/16)*1 + = 11/16 = 0.6875" Could you explain why (3/16)*1 but not (3/16)*2, though max waiting time is 2 (1001 - if we stand at place 1)?? Alexey Dergunov [Samara SAU] Re: Is the test case correct??? // Problem 1817. Merry-go-round 1 Feb 2011 22:19 Mask Time 0011 0 0101 0 0110 0 1001 1 1010 1 1100 2 Nikita++ Re: Is the test case correct??? [4] // Problem 1817. Merry-go-round 2 Feb 2011 00:02 Sorry, but why 11/16? Why not 3/16 + 3/16 + 3/16 + 3/16 + 2/16 + 2/16 = 16/16 I understand that 4/16 == 0.250000 ====== 1000 1/16 0100 1/16 0010 1/16 0001 1/16 24/16 == 1.500000 ===== 1110 (3+2+1=6)/16 1101 (3+2+1=6)/16 1011 (3+2+1=6)/16 0111 (3+2+1=6)/16 But why 11/16? Alexey Dergunov [Samara SAU] Re: Is the test case correct??? [3] // Problem 1817. Merry-go-round 2 Feb 2011 00:44 Just some basic knowledge from probability theory... 3/16 + 3/16 + 3/16 + 3/16 + 2/16 + 2/16 = 16/16 It's a normalization requirement (p1 + p2 + ... + pn = 1). And mean MX = p1*x1 + p2*x2 + ... + pn*xn, where pi - probabilities, xi - values. So we have (3/16)*2 + (3/16)*1 + (2/16)*1 + (3/16)*0 + (3/16)*0 + (2/16)*0 = 11/16. svr Re: Is the test case correct??? [2] // Problem 1817. Merry-go-round 2 Feb 2011 07:59 In Buffon problem there are 3 different solution and all of them are right. Answer depend on exact understanding all conditions of random experiment. I think that this problem also safer from too brief explanation. waterlink Re: Is the test case correct??? [1] // Problem 1817. Merry-go-round 2 Feb 2011 21:08 i've used this explanation of test: let it be some kind of class: 1100 0110 0011 1001 - first class, maked by all rotations of first one, and it's representative would be a smallest, so: [1100] : {1100 0110 0011 1001} [1010] : {1010 0101 1010 0101} - second class, we have repeatings here, but it must be always n rotations so, we could get [1100] from: 1000 - waiting 1 sec, 0001 - not waiting 0100 - not waiting all of them is class [1000] which comes from [0000] with 100% posibility so posibilities of [1000] would be: 1000 - 100% * 1 / 4 0001 - 100% * 1 / 4 0100 - 100% * 1 / 4 so posibility of getting in class [1100] is 3/4 [1010] we could get from: 0010 which posibility is 100% * 1 / 4 so our classes have such posibilities: [1100] - 3 / 4 [1010] - 1 / 4 [1100]: mask sec posibility 1100 2 1/4*3/4 0110 0 1/4*3/4 0011 0 1/4*3/4 1001 1 1/4*3/4 [1010]: mask sec posibility 1010 1 1/4*1/4 0101 0 1/4*1/4 1010 1 1/4*1/4 - it repeats, but it is another rotation, 3rd 0101 0 1/4*1/4 - 4th so, our result would be: MX = 2 * 3/16 + 1 * 3/16 + 1 * 1/16 + 1 * 1/16 = 11/16 = 0.6875 like in our test case i've used DP for this problem, just filling array of posibilities in recursive with saving way, rotating my current mask, and looking from where i could go here tester Re: Is the test case correct??? // Problem 1817. Merry-go-round 22 Feb 2011 05:58 What answer for n=20? Oleg Topalov What does mean the expected number of seconds a kid will have to wait? I don't understand what does word expeсted means. [1] // Problem 1817. Merry-go-round 30 Jan 2011 13:56 Edited by author 30.01.2011 13:57 Edited by author 30.01.2011 13:57 Edited by author 30.01.2011 13:58 Edited by author 30.01.2011 14:41
|