SRM 470 D1 500

Little John has drawn a rectangle. On the top edge, he draws n dots at different places and numbers them 1 through n from left to right. On the bottom edge, he also draws n dots at different places and numbers them 1 through n from left to right. 

John will then draw n straight line segments. For each segment, he will first choose a dot on the top edge that has not been chosen earlier. Then, he will choose a dot on the bottom edge that has not been chosen earlier. Finally, he will connect those two dots to form a straight line segment. 

John has drawn several of the n segments so far. You are given vector <int>s startDot and endDot. startDot[i] is the number of the top dot chosen for the i-th segment which has already been drawn, and endDot[i] is the number of the bottom dot chosen for that segment. For each remaining segment, John will randomly choose an available top dot and an available bottom dot (each available top dot has an equal probability of being chosen, and each available bottom dot has an equal probability of being chosen). Return the expected number of distinct pairs of line segments that cross each other in the final drawing.

 

Read more

未分类 Comments(1264) Fri, 28 May 2010 05:04:38 +0800