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.
Consider the following examples.
A = [2 3 1]
--> all 3 not in their right place
--> random shuffle gives one of the following permutations:
3 2 1 -> 1 element in correct place (the "2")
3 1 2 -> 0 element in correct place
2 3 1 -> 0 element in correct place
2 1 3 -> 1 element in correct place
1 2 3 -> 3 elements in correct place
1 3 2 -> 1 element in correct place
All are equally likely, so the expected number of elements in it's
correct place equals 1/6 * (1+0+0+1+3+1) = 1. I'm not sure how to
proof this, but it always gives 1, no matter how many elements you
permute. For 2 it's easy to see as well:
1 2 -> 2 elements in right place
2 1 -> 0 elements in right place
1/2 * (2+0) = 1.
1 -> 1 elements in right place
1 * 1 = 1.
Hope his helped.
/rnld
On May 7, 6:24 pm, SwiftCoder <[email protected]> wrote:
> I looked at some of the solutions, as per that umber of hits are same
> as the count of numbers which are not at their correct sorted
> position. Is that so?
--
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.
