This problem is a variation of the following problem:

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.

fft

How?

Firstly, the solution is computed with the following code:

So we have an equivalent equation:

`SUM(Ckn(d,k - 2) * SUM((Aj - Ai)^2) with j - i = d + 1`

You can rewrite it in the following way:

`(Aj - Ai)^2 = Ai^2 + Aj^2 + 2AiAj`

With above approach, we have 3 steps to complete this task:

`1. SUM(Ai^2 * SUM(Ckn(j,k - 2)) with j <= i - 1 -> Partial Sum`

`2. SUM(Ai^2 * SUM(Ckn(j,k - 2)) with j <= n - i -> Partial Sum`

`3. SUM(SUM(AiAj) * 2.Ckn(d,k - 2) with j - i = d + 1.`

The third part can be done by using

`FFT`

to computed`SUM(AiAj)`

with pair`(i,j)`

has particular difference.However, you cannot straightforwardly use

`FFT`

(low accuracy) or`NTT`

(`1e9 + 7`

is not a modulo to use`NTT`

). Instead, you can choose one of these methods:`1. Represent each Ai in a 2000-based number form. Then FFT with obtained arrays.`

`2. Use 3 modulo which is available with NTT then use Chinese Remainder Theorem.`

Complexity: O(Nlog(N))Finally, I mentioned my true solution, so don't misunderstand and down-vote me. Thank to everybody.You seem to be computing the version with largest, but OP asked for the shortest. However, it's easy to change it.

After sorting and assuming the distance is defined as $$$(x_i - x_j)^2$$$, the $$$O(n^2)$$$ approach would be

Then you just have to change your step 3.

If distance was defined as $$$|x_i - x_j|$$$, the $$$O(n^2)$$$ approach would be

That can be computed like steps 1 and 2.

Btw, it's possible to use FFT with item 17, I don't know if that's what you were referring to with "2000-based number form".

If you choose two certain points and others points outside the segment between those two points, the two points you choose might not neccessarily have the shortest distance. So your solution might not work.

actually I think the author has misunderstood the statement because I'm a participant of this contest. However I think this problem is quite intriguing, so I will try to solve it :3

About FFT with modulo

`1e9 + 7`

, i think you can refer to my code in this problem: http://codeforces.com/problemset/problem/623/ERip your contribution lol, don't leave your PC opened.

My bad. I will be more careful. Thanks bro :3

ntt

Relevant problem https://codeforces.com/contest/1188/problem/C