Imagine a game board and try to get "boundary condition"...
where:- blue arrows shows "far left" and "far right" cases;
- red arrows shows situation that will never happend (probability 0).
Also imagine "missing of a peg" situation,
where:- blue arrows shows that ball goes forward to the bottom with the same probability as it has before.
Test case from problem description
1st test case from example input
Posts
15 comments:
Thanks ! This is the only correct interpretation of the problem ! in my opinion =)
This is my interpretation of the problem as well. I dislike the angled boundaries, but given the math provided plus sample problems/solutions, it's the only thing that makes sense.
Hopefully the next round will be more clear.
Dear Illya Havsiyevych,
What about the second test case in the given example? I think I coded based on same strategy with yours, but, in my case, the probability is 0.5 when starting point is 1 and 2.
According to the problem, there is no ties or near. I did it several time on paper also, but I got same result.
Could you kindly explain what I might be missing?
I didn't exactly get that result. Instead of doing it your method I took out the peg at (2,2). I did manage to get the problem correct but it required doing a perfect grid ie:
x.x.x.x
x.x.x.x
x.x...x
x.x.x.x
x.x.x.x
#1pos: (0,0)
#2pos: (1,1) 1.0 probability
#3pos: (2,0).5prob (2,2).5prob
#4pos: (3,1).75prob (3,3).25prob
#5pos: (4,0).375prob (4,2).3125prob
leaving the ball in the first column (0) at .375000 probability. The reason at position 3 the ball goes to 2,2 then to 3,3 is because the peg is missing.
I would like to introduce the following pseudo-code to present my findings:
for(rows)
#1(0,0) = 1.0
//if(col = 0) then increment and keep probability
#2(1,1) = 1.0/2 //column not 0
//peg splits and col +- 1
#3(2,0) = .5 and (2,2) = .5
#4(3,1) = .5/2 and (3,2) = .5/2 //peg missing
#5(4,0) = .25 and (4,1) = .25/2 and (4,3) = .25/2
//if(col0 and col1 exists)
#6(END) = .25+.125=.375
FYI, my output for input file
-----------------------------
48 0.112857
0 0.375000
0 0.500000
16 0.089765
24 0.100113
8 0.175087
2 0.250000
35 0.230835
0 1.000000
25 0.089105
9 0.124782
8 0.167464
52 0.101299
30 0.100734
17 0.214032
44 0.266663
85 0.511620
11 0.072748
5 0.359375
2 1.000000
Can you give your input file... Just for testing purpose...
I am not sure your output is right... I got a different one...
Be careful, he is trying to decieve you! His solution is nowhere right, because 15th test case is 4 3 0 0, and his output is 17 column which does not even exist!
Please ignore my output because it looks like it has no sense without input. So some cases from my input:
2nd:
5 4 0 1 2 2
3rd:
3 4 0 0
7th:
5 4 2 6 1 1 3 0 2 0 2 3 3 1 1 0
9th:
3 3 0 1 1 0
15th:
71 35 17 1191 ....
Post a Comment