Блог пользователя bvd

How to find the expected shortest distance between two points in a subset of a set of points on a line?
Автор bvd, история, 5 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +28
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

fft

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится

    How?

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится -6 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          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.

          → Ответить
        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          → Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
5 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

ntt

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

→ Ответить