We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Is there a data structure that is directly applicable to this problem? I've come up with a few different approaches but they are all too slow. With a little probing I found that O(NlogN + Z) [where Z is the sum of all r-l] is right at the edge of the 3-second limit, so I am led to believe that you need to be able to answer each query without looking at each node in the range. That means either some kind of precomputed fast lookup for the range, or a dynamic programming approach where you re-use the results of previous queries. I don't think dynamic programming is the answer because when you get a new query that overlaps with a previous one you might know how many pairs were within the previous range but you still have to consider pairs between the two ranges.
My last best attempt was to group the wrestlers into clusters where the difference between the shortest wrestler and tallest wrestler in the cluster was <= k. Then sort the wrestler indices within each cluster. Then for a given query, you can find how many wrestlers are in the query range in each cluster by using a binary search. You already know all those wrestlers are valid pairs with each other. There is additional complexity where you have a group of wrestlers that are close in height but the full range is greater than k. I had a plan to address that but just the internal clustering approach was too slow for some test cases.
My gut says that a kd-tree might be the right answer since the queries are essentially on two axes. But I'm not exactly sure what the handling of the height-axis would look like.
I'd love to hear if I'm on the right track or a push in the right direction. Thanks!
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Almost Equal - Advanced
You are viewing a single comment's thread. Return to all comments →
Is there a data structure that is directly applicable to this problem? I've come up with a few different approaches but they are all too slow. With a little probing I found that O(NlogN + Z) [where Z is the sum of all r-l] is right at the edge of the 3-second limit, so I am led to believe that you need to be able to answer each query without looking at each node in the range. That means either some kind of precomputed fast lookup for the range, or a dynamic programming approach where you re-use the results of previous queries. I don't think dynamic programming is the answer because when you get a new query that overlaps with a previous one you might know how many pairs were within the previous range but you still have to consider pairs between the two ranges.
My last best attempt was to group the wrestlers into clusters where the difference between the shortest wrestler and tallest wrestler in the cluster was <= k. Then sort the wrestler indices within each cluster. Then for a given query, you can find how many wrestlers are in the query range in each cluster by using a binary search. You already know all those wrestlers are valid pairs with each other. There is additional complexity where you have a group of wrestlers that are close in height but the full range is greater than k. I had a plan to address that but just the internal clustering approach was too slow for some test cases.
My gut says that a kd-tree might be the right answer since the queries are essentially on two axes. But I'm not exactly sure what the handling of the height-axis would look like.
I'd love to hear if I'm on the right track or a push in the right direction. Thanks!