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.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
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)
This seems to be incorrect as I want all the pairs, but this doesn't take care of that.
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.
One has to return count of pairs not the exact pairs.
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.
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
How is it wrong? Can you explain a little bit.
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.
Here is the code. Look at example it outputs right if i didn't missunderstand.
https://ideone.com/lH6VQ5
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:
Your code outputs 3, when in reality the answer is at least 5(I did not count it properly).
Thank you, so it needs to be solved with segmentr tree.
no problem. Not true, you can use data structure such as binary search tree too.
Yea, sure
O(nlong)+O(nlogn)=O(nlogn)
Interesting :)