As I understand the probability, it goes something like this- If
you toss a coin 100 times, it is 'expected' (actual result may be
different) that 50 times you will get 'Heads' & 50 times 'Tails'. In
present problem also, you have to answer the 'expected' number of hits
by Goro to sort the numbers. This is also confirmed by the explanation
given for a case at the end of the problem statement D.
If three numbers are to be sorted, then the 'chance' or
probability of all three falling in correct place is 1/6. This means
that on an 'average', Goro will have to hit the table 6 times to sort
those numbers. But, there is a better strategy, and this number of
hits can be reduced. It goes like this-
The chance/probability of getting exactly one number in correct
position and the remaining two in wrong positions is 3/6 or 1/2. So,
on an 'average' if Goro makes two hits, he can 'expect' that one
number will be sorted. The hit counter is 2 by now. After this, he
holds the sorted number, and his requirement is to sort the remaining
two numbers. For these two numbers, as explained in the problem
statement itself, the probability of sorting is 1/2, and on 'average'
two hits would be required. The hit counter now becomes 2 + 2 = 4.
Mathematically, P(first event) = 1/2 and P(second event) = 1/2; so,
combined probability is 1/2 x 1/2 = 1/4, and reciprocal of that is 4,
which is average hits (the required answer).
Goro can use one more strategy, which again gives same answer. If
[3, 1, 2] are to be sorted, Goro will hold '3' and make on an
'average' two hits to bring '2' in correct position. Then, he would
release '3', hold the sorted '2', and make two more 'average' hits to
bring '1' & '3' in their respective correct positions.
@Bharath and @Pedro Osorio, I hope my explanation is not
frustrating to understand. If we come from different backgrounds, it
is normal that there is communication gap.
Eagle
On May 9, 12:07 pm, Bharath Raghavendran <[email protected]> wrote:
> Probability to get all 3 right = 1/6
> Probability to get only 1 right = 3/6
> Probability to get none right = 2/6
>
> If you get all 3 right, then it took only 1 try
> If you get 1 right, then you have 2 left .. hope you agree that on an
> avg, it will take 2 more tries [E(2) = 2] on an avg to solve this.
> Hence, total 3 tries
> If you get none right, on an avg, you will take E(3) more tries to
> solve this in an avg. So total tries = 1+E(3).
>
> So, E(3) = (1/6)*1 + (3/6)*3 + (2/6)*(1+E(3))
> = 1/6 + 9/6 + 2/6 + 2/6*E(3)
>
> 4/6 E(3) = 12/6
> E(3) = 12/4 = 3
>
> On 9 May 2011 12:13, Eagle <[email protected]> wrote:
>
> > @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
> > 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.
