"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.
