How to find the expected shortest distance between two points in a subset of a set of points on a line?

Revision en3, by bvd, 2019-10-10 20:56:49

This problem is a variation of the following problem:

http://icpcvncentral.tk/public/practice_problem.php?id=I19CE&fbclid=IwAR2j4yF6-LvsAn7ATxinyuo7LYj97MSiDIKCHsclI6dIr-bWgAySbqYRQ98

For some reason, I misread "longest" into "shortest", which made the problem much harder.

My version of this problem:

Given $$$n$$$ points $$$(a_1,0)$$$, $$$(a_2,0)$$$, ..., $$$(a_n,0)$$$. Pick $$$k$$$ points from $$$n$$$ points and calculate the shortest distance $$$d$$$ between two points in those $$$k$$$ points. Calculate the expected value of $$$d$$$.

An easier version of this problem:

$$$n$$$ points are $$$(1,0)$$$, $$$(2,0)$$$, ..., $$$(n,0)$$$.

Is this problem solvable in $$$O(n^3)$$$, $$$O(n^2)$$$, $$$O(nk)$$$ or even $$$O(n\log{n})$$$? Thank you.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English bvd 2019-10-10 20:56:49 1 Tiny change: 'ome reasons, I misrea' -> 'ome reason, I misrea'
en2 English bvd 2019-10-10 20:56:16 194 Tiny change: 'O(nk)$ or $O(n\log{' -> 'O(nk)$ or even $O(n\log{' (published)
en1 English bvd 2019-10-10 20:52:16 698 Initial revision (saved to drafts)