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 bvd 2019-10-10 20:56:49 1 Tiny change: 'ome reasons, I misrea' -> 'ome reason, I misrea'
en2 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 bvd 2019-10-10 20:52:16 698 Initial revision (saved to drafts)