This doesn't make sense too me. It seems like the case of sorting some of the numbers with a hit is not accounted for.
For example, with 3 numbers to sort, there is a 1/6 chance it is sorted on the first shot. And a 3/6 chance exactly one is sorted. If exactly 1 is sorted, then there is a 1/2 chance of sorting the rest. So doesn't that mean the chance of sorting it is 1/6 + (3/6 * 1/2)? On May 8, 4:31 am, "Alfonso J. Ramos" <[email protected]> wrote: > ... > > If you have 2 elements, then there is 1/2 chance of getting them right > [in one hit], and 1/2 of not. Of those last 1/2 you have 1/2 (that is > a 1/4 of the whole) to get it right [in two hits] and 1/2 (that's the > other 1/4 of the whole) not. Of that 1/4 you have 1/2 (that is a 1/8 > of the whole) to get it right [in three hits] and the other 1/2 (that > is 1/8 of the whole) not. > > So, you do the pondered sum of the N first iterations and you will see > that it converges to 2 (that's the average number of hits). > See: > first iteration = 1/2 * 1 hit = 1/2 hits > second iteration = 1/2 * 1 hit + 1/4 * 2 hits = 1 hit > third iteration = 1/2 * 1 hit + 1/4 * 2 hits + 1/8 * 3 hits = 1 hit + 3/8 hits > fourth iteration = 1/2 * 1 hit + 1/4 * 2 hits + 1/8 * 3 hits + 1/16 * > 4 hits = 1 hit + 5/8 hits > > No finite number of iterations is right because they only get as close > to cover all the posibilities, but you see the form: sum (i/2^i), you > may find that it converges to 2. I did ask wolfram alpha. > > Now... > > if you have 3 elements, then there is a 1/6 chance of getting them > right [in one hit], 3/6 of getting one element right, since Goro holds > those that are right, you can take this as a two element escenario so > it becomes a 3/6 chance of getting it right in three hits (the one he > did to the three elements plus the two average for the two element > case). And lastly the other 2/6 you get nothing right. Of those 2/6... > well you get the idea, when you do the pondered sum of the N first > iterations and you will see that it converges to 3 (that's the average > number of hits). I had to use excel for that. > > I did trust that that would work for the rest of cases, it took me a > long time... bad for me. > > You may be wondering, how comes the pondered sum is the average? well, > the classic average is the sum of the values over the total: [(A + B + > C) / Total], you can also express it like this: [(A / Total) + (B / > Total) + (C / Total)]. In a grouped average you multiply the values by > the number of times they appear [(A * timesA / Total) + (B * timesB / > Total) + (C * timesC / Total)]. > > In our case the total is 1 (that is the 100% of cases) the number of > times it appears is the probability and the value is the number of > cases. So you see that I don't need to divide by 1 as it gives me the > same value... so as it turns out the pondered sum of the number of > hits by it's probability is the group average of the number of hits. > > 2011/5/8 Lei Huang <[email protected]>: > > > > > > > > > Including the 2-elements array. > > There is 50% possibility that no elements will land in its position, > > and 50% possibility both of the elements are in the right position. > > So the expected is 50% * 2 + 50% * 0 = 1 > > > 2011/5/8 Jin Mingjian <[email protected]>: > >> "So we can expect that in any random permutation, one element will land in > >> its correct sorted pos." except for the 2-elements array? > > >> On Sun, May 8, 2011 at 3:20 PM, rajatag12 <[email protected]> wrote: > > >>> Yes. First thing to see is that Goro would never hit the table with open > >>> elements that *could not* land in their correct position for any > >>> permutation. Once it is understood, it will be easy to see that solving > >>> the > >>> prob for each permutation cycle is an independent one. Answering the main > >>> question, observe that each element in a sequence of N elements appears in > >>> its correct place (N-1)! times out of the N! permutations. So we can > >>> expect > >>> that in any random permutation, one element will land in its correct > >>> sorted > >>> pos. So after each hit, Goro should include the last element placed > >>> correctly in his set of elements to hold before he hits. Hence, expected > >>> number of hits = n. > >>> Formal proof has already been provided above. > > >>> On Sunday, May 8, 2011 7:22:39 AM UTC+5:30, Balajiganapathi wrote: > > >>>> I meant: Is n the expected number of hits to sort a n-element *cycle*. > > >>> -- > >>> 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. > > >> -- > >> 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. > > > -- > > 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.
