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.
