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.
