You are right. Its not 1/n. I misunderstood the problem and was lucky to get the right answer :P.
I calculated it as if once goro hits the table, all non-held elements shift by a random amount instead of a random permutation. Hope @pilhoon's math is right :) On 8 May 2011 22:32, shubham <[email protected]> wrote: > > Hey, > you said that if we have an n-element cycle then- > P(1) = probability to get it sorted in 1 shot =1/n > > How can it be 1/n as we have n elements then > there are n! ways for the elements to get arranged > after Goro's hit. And out of these n! ways only one > permutation will be sorted. > > So the probability to get the list sorted in one attempt > can't be 1/n! ?? > > Correct me if i am wrong.. > > -- > 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.
