You are saying that it is impossible to put "exactly one element into the right position" when N=2, right? I agree, obviously, we have 2 elements in the right position, or 0 elements in the right position.
What you don't seem to understand is that this doesn't contradict the statement "The expected number of elements that are put into position is exactly 1". The reason why you don't understand it, is because you don't understand the concept of expected value (I won't link it again, since you refuse to read and try to understand what it means). What baffles me is that for the case N=2, it is trivial to understand that, even though "having exactly one element in the right position" is impossible, the expected value of elements put into the right position is exactly 1: Initial: 2 1 Possible outcomes: 1 2 - 0.5 probability - 2 elements in the right position 2 1 - 0.5 probability - 0 elements in the right position X - elements that go into the right position after one hit for the array [2 1] E[X] = sum(p(X=x) * x) = p(X=0) * 0 + p(X=1) * 1 + p(X=2) * 2 + ... = All elements with p(X=x)=0 will be eliminated so only x=0 and x=2 matter (as you have repeatedly said): E[X] = p(X=0) * 0 + p(X=2) * 2 = 0.5 * 0 + 0.5 * 2 = 1 Do you understand now that p(X=E[X]) can be 0? -- 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.
