@Bharath, No it should require 6 hits in your case, if you extend the
following logic-
For the three unsorted numbers 3 1 2, the sample set of arrangements
is-
1 2 3
1 3 2
2 1 3
2 3 1 - Not even one in correct position
3 1 2 - Not even one in correct position
3 2 1
The probability of at least one number being at its sorted position is
2/3, while the probability of not getting even one number in its
correct position is 1/3. So, how come, all of a sudden, the
probability of getting at least one number in its correct position is
becoming 1.0? If at all, average hits are to be calculated (being
average, it can be non-integer real number), then it would be
reciprocal of 2/3, that is, 3/2, that is 1.5 and not 1.
Also, while calculating total probability of dependent events, you
MULTIPLY the individual probabilities, and NOT add them.
In the present example, the P(exactly one element in correct position)
is 3/6 = 1/2. After that event is realized, Goro will hold that
number, and only two unsorted numbers are there. This time, the
P(correct sorting) is 1/2. So, the combined probability is 1/2 x 1/2 =
1/4. Thus, total 4 hits would be required on average.
(If my analysis is correct, I will have the life-time joy of catching
Google employees making logical error! Ha ha ha!!)
Eagle
On May 9, 7:45 am, Bharath Raghavendran <[email protected]> wrote:
> The 4 steps for sorting are not definite. Its just that Goro has to
> follow the following steps :
> * Hold down any element that is in its place
> * Bang table to re-arrange other elements.
>
> Repeat this step till all elements are sorted. As elements get in
> place, include them into the held down elements.
>
> If Goro is lucky, all elements get sorted in a single step.
> If Goro is unlucky, it can take indefinitely long to sort.
> On an average, you will see that the above method will get the
> elements sorted in 4 shots.
>
> On 9 May 2011 06:32, WL Teng <[email protected]> wrote:
>
> > Could anyone show me what are the four steps in sorting 4 1 2 3?
>
> > Sorry for the repost, if any, because my old post did not show up.
>
> > --
> > 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
> > athttp://groups.google.com/group/google-code?hl=en.
--
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.
