bvd's blog

How to find the expected shortest distance between two points in a subset of a set of points on a line?
By bvd, history, 5 years ago, In English

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.

  • Vote: I like it
  • +28
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

fft

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    How?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      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 + 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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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".

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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.

          → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.me/problemset/problem/623/E

          → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Rip your contribution lol, don't leave your PC opened.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

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

      → Reply
»
5 years ago, # |
  Vote: I like it -17 Vote: I do not like it

ntt

→ Reply
»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

→ Reply