@Pedro,
In your last two steps,
> E[n=3] = 2 + 1/3 * E[n=3]
>
> E[n=3] = 3
there is something wrong. How are you eliminating E[n=3] on the right
hand side of the equation?
Eagle
On May 9, 12:28 am, Pedro Osório <[email protected]> wrote:
> Hi Ricardo,
>
> For your example regarding 3, you have the following possibilities:
>
> 1 2 3 - perfect
> 1 3 2 - one correct
> 2 1 3 - one correct
> 2 3 1 - wrong
> 3 1 2 - wrong
> 3 2 1 - one correct
>
> As you can see, if goro hits without holding anything, 1/6 of the time
> it will be sorted, 1/2 of the time there will be 2 out of place and
> 1/3 of the time there will be 3 out of place.
>
> This means that:
>
> E[n=3] = 1 + (1/6 * 0 + 1/2 * E[n=2] + 1/3 * E[n=3])
>
> As you have shown, E[n=2] = 2, so:
>
> E[n=3] = 2 + 1/3 * E[n=3]
>
> E[n=3] = 3
>
> On May 8, 7:57 pm, werneckpaiva <[email protected]> wrote:
>
> > I read too and it doesn't make any sense for me.
>
> > I understand that this is a geometric distribution where if P(X)=p so
> > E(X)=1/p. So, if you have 2 numbers unsorted and Goro hits the table,
> > there is 0.5% chance to stay in the same position and 0.5% chance to
> > swap positions. But, if you have 3 unsorted elements, there are 6
> > different permutations, so, P(X)=1/6 and the E(X)=6. My solution is
> > hold 1 number, swap the other 2; hold the sorted element and swap the
> > other 2 remaining, so 2 + 2 = 4 hits
>
> > 3 1 2
> > 1 3 2
> > 1 2 3
>
> > But this doesn't seem to be the correct answer. The developers
> > solutions say that for 3 unsorted numbers needs only 3 hits. Anyone
> > knows how to explain that?
>
> > Regards,
>
> > Ricardo
>
> > On May 7, 8:24 pm, SwiftCoder <[email protected]> wrote:
>
> > > I looked at some of the solutions, as per that umber of hits are same
> > > as the count of numbers which are not at their correct sorted
> > > position. Is that so?
--
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
