If we ask a statistician, how many tosses of a perfect coin are required to get H (heads) 40 times, then he would answer- 80 tosses. This is because P(H) is 1/2. But, if we tell that the coin is imperfect, and empirically it is found that P(H) is 4/5, then his answer would be- 40 divided by 4/5 = 40 x 5/4 = 50 tosses. If, on the other hand, empirically P(H) is 1, then only 40 tosses are required. I hope everybody here agrees with this explanation.
Now, in the contest analysis of problem D, the first Lemma/theorem given is- Lemma: x(A) = n(A) for all A. This Lemma breaks down (or at least becomes absurd) for A=1, since there is no such case; there can not be just one unsorted number. Hence for A=1, the number of hits is zero. Conversely, for 1 hit, there is no case. After such a gap, I am doubtful whether "the inductive hypothesis" can be used. More over, I am frustrated by the contest analyzer's assertion - 'This follows from "linearity of expectation": 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.' This is not correct; the probability of getting 1 element in correct position is 1/2 and not 1/N. The probability of getting not even a single element in its correct position is 1/N. Therefore, on an average 2 hits would be required to bring 1 (any one) number at right position. Second mistake in the above assertion is- N * 1/N, i.e., 1/N + 1/N + 1/ N .... N times. You can not add probabilities in this manner. Some of you may then point to the third sample case in the problem statement. It was [2 1 4 3]. This is what I would like to call as 'semi-sorted' case to mean it is favorable to Goro. Here, pairs [2 1] and [4 3] are having numbers in swapped positions. That is why the mentioned strategy gives the answer (correctly) as 4 hits. However, if the case were [4 1 2 3], then it would require 6 hits as per the given strategy. In lighter vein - I am having the same feeling as Galileo Galilee, who was saying that the earth revolves around the sun while the powerful Church people were calling him heretic. I am facing the wrath of 2704 contestants whose solution was judged correct as well as that of the Pope aka Google. Ha Ha Ha... (No offense to anybody intended. My apologies if any body's feelings are hurt!) Eagle On May 9, 8:58 pm, Pedro Osório <[email protected]> wrote: > @Paul > > Thanks for answering for me > > @Eagle > > Glad I could help =) > > On May 9, 3:10 pm, Eagle <[email protected]> wrote: > > > @Pedro, > > > In your last two steps, > > > > E[n=3] = 2 + 1/3 * E[n=3] > > > > E[n=3] = 3 > > > there is something wrong. How are you eliminating E[n=3] on the right > > hand side of the equation? > > > Eagle > > > On May 9, 12:28 am, Pedro Osório <[email protected]> wrote: > > > > Hi Ricardo, > > > > For your example regarding 3, you have the following possibilities: > > > > 1 2 3 - perfect > > > 1 3 2 - one correct > > > 2 1 3 - one correct > > > 2 3 1 - wrong > > > 3 1 2 - wrong > > > 3 2 1 - one correct > > > > As you can see, if goro hits without holding anything, 1/6 of the time > > > it will be sorted, 1/2 of the time there will be 2 out of place and > > > 1/3 of the time there will be 3 out of place. > > > > This means that: > > > > E[n=3] = 1 + (1/6 * 0 + 1/2 * E[n=2] + 1/3 * E[n=3]) > > > > As you have shown, E[n=2] = 2, so: > > > > E[n=3] = 2 + 1/3 * E[n=3] > > > > E[n=3] = 3 > > > > On May 8, 7:57 pm, werneckpaiva <[email protected]> wrote: > > > > > I read too and it doesn't make any sense for me. > > > > > I understand that this is a geometric distribution where if P(X)=p so > > > > E(X)=1/p. So, if you have 2 numbers unsorted and Goro hits the table, > > > > there is 0.5% chance to stay in the same position and 0.5% chance to > > > > swap positions. But, if you have 3 unsorted elements, there are 6 > > > > different permutations, so, P(X)=1/6 and the E(X)=6. My solution is > > > > hold 1 number, swap the other 2; hold the sorted element and swap the > > > > other 2 remaining, so 2 + 2 = 4 hits > > > > > 3 1 2 > > > > 1 3 2 > > > > 1 2 3 > > > > > But this doesn't seem to be the correct answer. The developers > > > > solutions say that for 3 unsorted numbers needs only 3 hits. Anyone > > > > knows how to explain that? > > > > > Regards, > > > > > Ricardo > > > > > On May 7, 8: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.
