|
|
| Show all threads Hide all threads Show all messages Hide all messages | | I understand test | Felix_Mate | 1817. Merry-go-round | 25 Sep 2016 12:55 | 1 | 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 | | Is the test case correct??? | 72VanVector[SevNTU] | 1817. Merry-go-round | 22 Feb 2011 05:58 | 15 | 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 The test case is correct. 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 Seems like the possibility of each case isn't equal to 1/6, some of the cases have more then 1/6, others - less. How did you do that??
Edited by author 30.01.2011 16:45 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! 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 ? 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) "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)??
Mask Time
0011 0
0101 0
0110 0
1001 1
1010 1
1100 2 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? 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. 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.
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 | | What does mean the expected number of seconds a kid will have to wait? I don't understand what does word expeсted means. | Oleg Topalov | 1817. Merry-go-round | 3 Feb 2011 18:38 | 2 | 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 |
|
|
|
