Hostel visit problem

#1

Not able to think a solution with max heap. Please help

#2

@Rakshitgarg99 make a max heap.
For query of type 1, if size of heap is less than k, insert distance. If size of heap is more than or equal to k, in this case, if the top element is larger than the current distance, pop that distance from the queue and push the current distance, else do nothing. This will ensure that k nearest distances remain in the heap and because the heap is max heap, kth largest distance will be given by pq.top()
Therefore, for queries of type 2, print the top element of the queue.

#3

Hey i am actually facing problem in uderstanding this part
else{
if(pq.top()>dist){
pq.pop();
pq.push(dist);
}
}
else{
cout<<pq.top()<<endl;
}

I code the problem and it works but didn’t get how top element becomes kth element everytime.

For ex -
4 3
1 2 2
1 9 9
1 -8 -8
2

answer has to be 4 - {128,162,4} but output is 162

#4

@Rakshitgarg99 for the example

4 3
1 2 2
1 9 9
1 -8 -8
2

q = 4, k = 3
so the max size of the heap can be 3
1 2 2 -> insert 8 in the heap
1 9 9 -> insert 162 in the heap
1 -8 -8 -> insert 128 in the heap

Now, if you look at all the distances from origin, they are {8, 128, 162}
Third nearest hostel is 162

No, that will be the nearest hostel, we have to find 3rd nearest hostel.

#5

Now, if you look at all the distances from origin, they are {8, 128, 162}
Third nearest hostel is 162

As we making max heap it has to be {162,128,4} to fullfil heap condition and that is the reason i get puzzled while solving it with heaps

#6

@Rakshitgarg99 we need 162 as answer, max heap will give kth largest, ie kth nearest distance.

#7

I still don’t get it :sweat_smile: heaps ke saath jugaad jaisa lag rha h

#8

@Rakshitgarg99 do a dry run for the sample input of the question, make a heap and everything and try to do all the operations manually, maybe that will help in getting the intution of this problem.

#9

I do that i think there is a problem between heap explanation and sample input expalanation provided with question
beacause for example -
6 3
1 10 10
1 9 9
1 -8 -8
2
1 11 11
2

According to sample input explanation - {242,128,162,200}
output - 200,168

Heap - 200,168,128
top element as output - 200
as 200>242 is false because
if(pq.top()>dist){
pq.pop();
pq.push(dist);
}
so output will be again 200

#10

@Rakshitgarg99

9 3
1 10 10
1 9 9
1 -8 -8
2
1 7 7
2
1 6 6 
1 5 5
2

200
162
98

Here , No of queries = n = 9 k = 3

We have to print the kth distance from the hotel.

We are calculating and storing the rocket distance here i.e. (x2-x1)^2 + (y2-y1)^2 … basically the cartesian distance but without the squareroot.

First integer of each input defines the query type. 1 means take the coordinates input and 2 means display the kth distance so far.

Iteration 1 :
First we get 1 10 10
Distance = 10^2 + 10^2 = 200
We store it in our data structure. Lets call it A.
A = { 200 }

Iteration 2 :
1 9 9
Distance = 9^2 + 9^2 = 162
A = { 162 , 200 }

Iteration 3 :
1 -8 -8
Distance = (-8)^2 + (-8)^2 = 168
A = { 128, 162 , 200 }

Iteration 4 :
2
A = { 128, 162 , 200 }
Time to print the 3rd nearest distance ( k=3 )
Output : 200


Iteration 5 :
1 7 7
Distance = 7^2 + 7^2 = 98
A = { 98, 128, 162 , 200 }

Iteration 6 :
2
A = { 98, 128, 162 , 200 }
Time to print the 3rd nearest distance ( k=3 )
Output : 162

Iteration 7 :
1 6 6
Distance = 6^2 + 6^2 = 72
A = { 72, 98, 128, 162 , 200 }

Iteration 8 :
1 5 5
Distance = 5^2 + 5^2 = 50
A = { 50, 72, 98, 128, 162 , 200 }

Iteration 9 :
2
A = { 50, 72, 98, 128, 162 , 200 }
Time to print the 3rd nearest distance ( k=3 )
Output : 98

This is the information given in the question, I dont think there is anything wrong with the information.

#11

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.