(a) is each element that is in the wrong position (b) is each element that is not being held when Goro hits the table.
So T is the number of elements not being held -> #set b + number of elements being held which are in the wrong position -> #(set a\set b). Let us define #setb = Tb and #(set a\set b) = Ta You know that the elements being held in the wrong position will stay there (Ta). As for the elements which are being permuted, if you assume the best case (that they are just a permutation of the correct order), according to the reasoning given in Lemma 2, the expected value of the number of elements that were permuted and end up in the wrong place is Tb-1. Since this is the best case, the actual expected value is >= Tb-1. To this value we have to add Ta, and hence the expected value is >=Ta +Tb-1 = T-1 On May 8, 4:01 pm, yiuyuho <[email protected]> wrote: > Hi, > > I was reading the analysis for GoroSort. Can someone give some more > details on the definition of T (in Lemma 2)? In particular, > > (i) What does it mean by an element "permuted when Goro hits the > table" (part (b)). Does it refer to an element for which Goro is > simply not holding down for the first time he hits the table following > the optimal strategy? Or is it the number of elements actually > displaced from their original position after one hit? Or something > else? > > (ii) Why is p0 * 0 + p1 * 1 + p2 * 2 + ... pT * T ≥ T - 1. Can't > really reason about this since I am confused about the definition of > T. > > Thanks, > Raymond -- 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.
