PerryThePlaytypus's blog

Finding all the pairs whose individual values are more than a given pair
By PerryThePlaytypus, history, 3 days ago, In English

So, I came across a problem that has a subtask of finding all the pairs (from a given set of pairs), whose first and second values are greater than the corresponding first and second values of a given pair. For example : we have a set of pairs s = {{2,3},{4,5},{6,7}} and the given pair is {3,4}, now we have to return all the pairs whose first value is greater than 3 and second value is greater than 4. It is evident that {4,5} and {6,7} are the answers.

Initially I thought of using lower_bound()/upper_bound() functions. But unfortunately, only one of the values (either first or second) will be taken care if we use it. Then @steveonalex told that we had to use segment tree to get the required answer. I don't know how to do it. So can someone explain how we can get the answer using segment tree?

I have an approach which seems fine at first but has a not so good time complexity (according to me). Approach : I will have a map whose keys are the first values of pair and their corresponding values to be a set/multiset of all the second values it has in the original set. For example: Given the set = {{1,2},{1,3},{1,4},{2,4},{2,5}} would have the map as m[1] = {2,3,4} m[2] = {4,5}

Now after these values are stored. I can directly do binary search to get the pointer/index of the set of each individual keys (the point from where the second value is greater).

The time complexity would be (log(N_1) + log(N_2) + log(N_3) ......). Where can N_1 + N_2 + .... = N. Is this right?

Can we do better than this? Please let me know.

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

»
3 days ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

You can do it with merge sort tree in $$$log_2^2{n}$$$ per query. Sort all pairs by the first value and create a merge sort tree over the second values. Now for each query binary search the first pair whose first value is greater than the given pair's first value. Now in the merge sort tree ask how many values are greater than the second value of the given pair in the range $$$[pos, n]$$$.

EDIT: do you have to just count the pairs or output every one. Also if there is just one given pair, why can't you just iterate over every pair?

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

    So we had to return all the pairs that satisfy the constraint. Also, the question was not just for one pair. They had multiple queries.

    → Reply
    • »
      »
      »
      3 days ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Then you can just modify the merge sort tree to iterate over the valid pairs and print them out.

      → Reply
»
3 days ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

we can consider each pair as a point in O(x, y)

now, assume that you have points (3, 5), (4, 2), (7, 9) and the given points are (2, 3), (4, 5), each given point (x, y) will become (x + 1, y + 1)

sort all points by first value.

(3, 4)(B), (3, 5)(A), (4, 2)(A), (5, 6)(B), (7, 9)(A)

(we will divide all the points into 2 types: A(the points we already have), B(the given points))

now scan from right to left, at point (x, y) if its type is A, we will add y into segment tree, otherwise we need to count number points in segment tree that greater than or equal to y.

→ Reply
»
3 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Instead of thinking of it as a pair, think of it as a line segment instead. The problem now becomes counting the numbers of segment (x',y') such that x>x', and y>y'. Let's try answering this offline, we can now solve this by sorting either x or y in such a way that it's strictly non-decreasing, and adding to the count of x', or y' (the point which we aren't fixing) by 1, for each query, we'll count the numbers of point such that it's smaller than the one we didn't fix (if we fix x, we find the numbers of point < y, and vice versa). For this, we need a data structure which supports quickly updating and querying range sum, for this, we can use either Segment Tree or Fenwick Tree If you need to output the pairs as well, you might wanna consider saving the indices instead.

→ Reply