The explanation of why on average exactly 1 element will take its
place is given on the problem analysis page:
Goro is permuting N elements; each one has probability exactly 1/N
of ending up in the correct position, and hence, the expected
number
of elements that end up in the correct position is N * 1/N = 1.
Let's count how many elements, on average, will take their places
after one permutation:
C = sum_{i=1..N} ( C_i )
C = sum_{i=1..N} ( prob_i * 1 + (1 - prob_i) * 0 )
C = sum_{i=1..N} ( 1/N )
C = N * 1/N
C = 1
where
C_i is, so to say, which part of i-th element on average will take
its place.
prob_i=1/N is the probability that i-th element will take its place.
After a permutation, on average, so to say 1/N part of one element
will take its place, so for N elements that will be N * 1/N = 1.
On May 8, 5:41 pm, rnld <[email protected]> wrote:
> Yes, that seems correct.
>
> Let's say M is the number of unsorted elements in the array of length
> N.
>
> If you randomly permute the M unsorted elements once, the expected
> number of elements that fall into its right place equals exactly 1.
> Hence, on average you'll have to do this M times (after each
> permutation you freeze everything that's in place, and repeat until
> number of unsorted elements equals zero), which makes that the
> expected number of hits is M.
--
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.
