Why is my pbds solution not working?

#1

QUESTION:

Dean of MAIT is going to visit Hostels of MAIT. As you know that he is a very busy person so he decided to visit only first “K” nearest Hostels. Hostels are situated in 2D plane. You are given the coordinates of hostels and you have to answer the Rocket distance of Kth nearest hostel from origin ( Dean’s place ) .

MY DOUBT:

The editorial solution is done with a heap, but I came up with the solution with pbds and it works for the all test cases except the last one, can you explain why is that?

Here is my solution:

2fe72fbd-0a83-4e40-8229-14b879e2dbeb.png876Ă—516

#2

Solution link : https://ide.codingblocks.com/s/660568

#3

hey, refer this–> https://ide.codingblocks.com/s/660718

#4

I know the priority queue solution but I wanted to know why my pbds solution does not work?
Because in the question kth nearest hostel is asked and in pbds find_by_order() returns the element at the kth index i.e. k+1th nearest. So in theory pbds should also work, but it fails the last test case.

#5

I actually figured it out!!!
The problem with pbds is that it only allows unique elements thus when two DIFFERENT hostels lets say (10, 20) and (20, 10) get’s added as (10^2) + (20^2) = 500, it will be added as a single entry, where as in heap this won’t be the case.

So when the kth entry is retrieved it looks like this in pbds:
500, -entry1-, -entry2-
kth entry being -entry2-

in head:
500, 500, -entry1-
kth entry being -entry1-

Thus resulting in different answers, therefore the failure of last test case.
I guess that solves it and I will close my question.

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.