bvd's blog

By bvd, history, 4 days 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

»
3 days ago, # |
  Vote: I like it -8 Vote: I do not like it

fft

  • »
    »
    3 days ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    How?

    • »
      »
      »
      2 days 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.

      • »
        »
        »
        »
        47 hours 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".

        • »
          »
          »
          »
          »
          33 hours 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.

        • »
          »
          »
          »
          »
          32 hours 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.com/problemset/problem/623/E

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

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

»
3 days ago, # |
  Vote: I like it -17 Vote: I do not like it

ntt

»
3 days ago, # |
  Vote: I like it +21 Vote: I do not like it