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 at http://groups.google.com/group/google-code?hl=en.
