rahul_1234's blog

Pair finding
By rahul_1234, history, 8 years ago, In English

You are given a number of points on the XY-plane, [(x0,y0),(x1,y1),(x2,y2),...]. A point (xi,yi) is dominant to another point (xj,yj) iff xi>xj and yi>yj. Calculate all pairs of points such that one dominates the other.

A time complexity less then O(n*n) was required.

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

»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can solve it in O(nlogn). First, you sort points by x-coordinate value. And you just do (i can't call it dp) partial sum. What does it mean is, (remember x values are sorted) if x[i]>x[i-1] than d[with value x[i]]=d[with value x[i-1]]+1 where d is arrays where we can count number of points where point i is greater than point j by x coordinate. That takes O(nlogn). Now do the same for y-axis but instead of array d you can make new array d2 (O(nlogn). We did for x-axis and y-axis now we need for both. Easily you can add to 'sum' min(d[i],d2[i]). If you didn't understand something comment. If you want the code comment. UPD: Total time complexity O(nlong)+O(nlogn)=O(nlogn)

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

    This seems to be incorrect as I want all the pairs, but this doesn't take care of that.

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

      you mean to say we have to return all pairs? If so, that's impossible as the number of pairs is O(n^2). basic example is if you have n points such that each point is (1,1), (2,2), ... (n,n). Then you have 0+1+2+...+n-1 = n(n-1)/2 which is order n^2.

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

        One has to return count of pairs not the exact pairs.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 3   Vote: I like it +3 Vote: I do not like it

          Thanks for making it clear.

          Here's a nlogn solution:

          Sort the points by from right to left. and start from the first one. we need to processing each line, and then increase all their y-value on that line by 1 in a segment tree. As the y-value maybe too large. We will need to use a hash table to remap the points. So to remap the points, simply sort all y-value and map the y-value to (1...total number of y-value).

          How we process the line is simple. We just query sum of the segment tree for each point on that line from the map(y-value) to the total number of y-value and add that to the total.

          Just do that from the rightmost line to the leftmost line, and we will get the answer we desire.

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

          secondly, you can use a treap instead of segment tree + hashtable. so instead of doing a range sum query, you just query for the index of the y-value. Here's some information of treap

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

      How is it wrong? Can you explain a little bit.

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

        What does in stand for in min(d[i], d2[i])? Anyway, as far as I see your approach doesn't require that the set that forms min(d[i], d2[i]) should be a subset of max(d[i], d2[i]). And that's definitely wrong.

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

          Here is the code. Look at example it outputs right if i didn't missunderstand.

          https://ideone.com/lH6VQ5

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

            you coincidentally got the right answer. This is clearly wrong. I think what you are trying to do is find number of points with x-value less than point i in d[i] and vice versa of the y-value(though your implementation for this is wrong as well). Furthermore, the minimum of both sets is not the intersection(so this makes it more wrong). So your code make no sense whatsoever.

            Here's an example:

            4
1 1
2 2
1 0
3 3

            Your code outputs 3, when in reality the answer is at least 5(I did not count it properly).

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

              Thank you, so it needs to be solved with segmentr tree.

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

                no problem. Not true, you can use data structure such as binary search tree too.

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

    O(nlong)+O(nlogn)=O(nlogn)
    Interesting :)

    → Reply