bvd's blog

By bvd, history, 4 days ago, , 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. Comments (10)
 » fft
•  » » How?
•  » » » Firstly, the solution is computed with the following code: for(int i = 1 ; i <= n ; ++i) for(int j = i ; j <= n ; ++j) ans += (a[j] - a[i]) * (a[j] - a[i]) * Ckn[j - i - 1][k]; with Ckn(i,j) is the number of ways to choose j elements from an i-element set. So we have an equivalent equation:SUM(Ckn(d,k - 2) * SUM((Aj - Ai)^2) with j - i = d + 1You can rewrite it in the following way:(Aj - Ai)^2 = Ai^2 + Aj^2 + 2AiAjWith above approach, we have 3 steps to complete this task:1. SUM(Ai^2 * SUM(Ckn(j,k - 2)) with j <= i - 1 -> Partial Sum2. SUM(Ai^2 * SUM(Ckn(j,k - 2)) with j <= n - i -> Partial Sum3. 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 for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) { ans += (x[j] - x[i]) * C(n - (j - i + 1) - 2, k - 2)); } 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 for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) { ans += (x[j] - x[i]) * C(n - (j - i + 1) - 2, k - 2)); } 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 :3About FFT with modulo 1e9 + 7, i think you can refer to my code in this problem: http://codeforces.com/problemset/problem/623/E
•  » » Rip 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