7KIRA1999's blog

N points, dist btw two points is defined as min(abs(x1-x2), abs(y1-y2)).find kth min dist.
By 7KIRA1999, history, 19 months ago, In English

I am trying to solve the given problem from here :

https://stackoverflow.com/questions/69444907/given-an-array-of-n-points-the-distance-between-two-points-is-defined-as-minab

using very similar problem : https://www.spoj.com/problems/NKPAIRS/en/

The code for this spoj problem looks something like this -

int n, m=50000, x[100005], y[100005];
long long ans;
struct segtree {
    int v[2*L];
    void upd (int P, int V) {
        P += L;
        while(P) {
            v[P] += V;
            P /= 2;
        }
    }
    int get (int S, int E) {
        S += L;
        E += L;
        int R = 0;
        while(S <= E) {
            if(S % 2 == 1) R += v[S++];
            if(E % 2 == 0) R += v[E--];
            S /= 2;
            E /= 2;
        }
        return R;
    }
} seg;
 
vector<int> b[150005];
 
long long solve2 (int d) {
    for(int i=1;i<=n;i++) {
        b[x[i]+y[i]-1].push_back(x[i]-y[i]+m);
    }
    for(int i=1;i<=2*m;i++) {
        for(auto &T : b[i]) {
            ans += seg.get(max(0,T-d), min(2*m,T+d));
            seg.upd(T, 1);
        }
        if(i - d <= 0) continue;
        for(auto &T : b[i-d]) {
            seg.upd(T, -1);
        }
    }
    return ans;
}

What changes should be done in this part so that the distance factor is updated in regards to my problem ?

Any help is appreciated.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
19 months ago, # |
  Vote: I like it -8 Vote: I do not like it

If I understand correctly, the tasks are not so similar. In one place, you need to get the sum of absolute values $$$|x_i - x_j| + |y_i - y_j| + |z_i - z_j|$$$, and check for each pair if they are <= D. Here you need to take the minimum of the two absolute differences.

You can solve this task in O(NlogNlogMAX), where MAX is the maximum coordinate. Let's do binsearch on the value. Now we need to check how many points there exist with distance <= D. Let's do this separately: first we count how many pairs have $$$|x_i - x_j| \leq D$$$, then with y, then we subtract the pairs that have both $$$|x_i - x_j| \leq D$$$ and $$$1|y_i - y_j| \leq D$$$. The first part is simply counted independently for each coordinate. The second part is trickier to count. In order to do so, we need to notice that the points in which both coordinates are $$$\leq D$$$ gives us a square. Now you need to count number of points inside. This is doable with segment tree + sorting in $$$O(NlogN)$$$. Now we have solved the task in $$$O(NlogNlogMAX)$$$

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Yes I too realised recently that these two are not actually related. I was trying with the sqrt decomposition to calculate the part where |xi — xj| > D and all the Ys with values in range Yi — D to Yi + D. But it is becoming complex.

    Can you help with the tricky second part, didn't understand how we will build/query segment tree with xi and yi as param here. Where for each index our square border will change.

    Also the constraints are like spoj problem. Xi, Yi <= 50000. N<= 50000

    Thanks for the help.

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      We want to count number of points inside a square. Let's do scanline on x values and y values. We have points (X_i, Y_i-Y_z) and borders (X_z, Y_i-y_z) Sort all of this "events" by the X-coordinate. When we handle a square, we make an event for its left low corner and high right corner. When we get a point, we simply add 1 to the y-coordinate. When we get one of the corners, we get the sum of all the points from Y_i to Y_z that already exist. Then we subtract the vales and get the correct answer. It is a standard problem, you could probably find it online.

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

        event will be like this ( Xi, Yi — D ) and ( Xi, Yi + D) ? with 1 and -1 being added for their contribution ?

        also if possible do u know some problem which solves something similar. I haven't seen this standard problem.

        → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'd say you can do a binary search on the answer. The condition would be P(x) = "are there less than k distances less tham or equal to x?".

You can answer these by using 2D Fenwick Tree with lazy creation. (For each point, count how many points are inside its corresponding cross shape using three queries)

Total running time is $$$O(N \log^{3} X)$$$ where $$$X$$$ is the size of the world.

You can remove one log by solving queries offline with 1D Fenwick Tree (Sort query corners left to right). Because you have to sort inside the binary search, there is a $$$log N$$$ factor that gets added.

Then complexity is $$$O(N \cdot (\log N + \log X) \cdot \log X)$$$

With coordinate compression, you can get $$$O(N \log^{2} N)$$$ but idk if that would be faster in practice

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

    Yes, I think the intended solution is close to Nlog^2N. As N = 50000. I am able to code the O(Nlog^3N) approach using this binary search and segment tree. Will try to bring it down.

    → Reply