How to improvise further?

#1

I wrote a solution for HOSTEL VISIT problem but i am getting tle in 2nd test case, can anyone get in touch with me so that i can show my code and improvise it…

 #include<bits/stdc++.h>
using namespace std;

class hostel{
public:
    long long int x;
    long long int y;
    hostel(){
        
    }
    hostel(long long int x, long long int y){
        this->x = x;
        this->y = y;
    }
     int dist(){
      return  (x*x) + (y*y);
    }
    void print(){
      cout<<(x*x)+(y*y)<<endl;
    }
};

class dishostel{
public:
    bool operator()(hostel h, hostel ht){
        return h.dist()>ht.dist();
    }
};

int main(){
    long long int q,k,type_q;
    long long int x,y;
    priority_queue<hostel,vector<hostel>,dishostel> pq;
    cin>>q>>k;
    hostel hos[k];
    for(long long int i=0;i<q;i++){
        cin>>type_q;
        if(type_q==1){
            cin>>x>>y;
            hostel h(x,y);
            pq.push(h);
        }
        if(type_q==2){
           for(int i=0;i<k;i++){
              hos[i] = pq.top();
               pq.pop();
           }
           hos[k-1].print();
           for(int i=0;i<k;i++){
            pq.push(hos[i]);
           }
        }
    }
    return 0;
}

Thank you

#2

Hi

Hint 1->
You have to use Heap Data Structures to remove TLE. (is stl you can use priority_queue for c++ )

Hint 2 ->
Use max heap,
whenever you have query on type 1, calculate the distance, add this if size of priority queue is less than k.if size is==k then compare with top element if it greater then ignore this distance, if less then remove top element and add this new distance.

in every type 2 query return top element.

Algo:
priority_queue<int,int> pq.
if (querytype ==1)
{
int dis= (x2 - x1)2 + (y2 - y1)2
if(pq.size()<k)
pq.push(dis)

       else
       {
           if(pq.top()>dis )
              { 
                   pq.pop()
                   pq.push(dis)
               }
         }

}
if(querytype==2)
{
cout<<pq.top()
}

Hit like if you get it! :stuck_out_tongue:
Cheers! :smiley:

1 Like
#3

Hey there, i am getting wrong -answer for test-case 2 . Can you suggest me something to counter edge cases!!

#include<bits/stdc++.h>
using namespace std;

long long int distance(int x,int y){
   return (x*x) + (y*y);
}

int main(){
    long long int q,k,type_q;
    long long int x,y;
    int cal_dist;
    priority_queue<long long int> pq;
    cin>>q>>k;
    for(long long int i=0;i<q;i++){
          cin>>type_q;
          if(type_q==1){
            cin>>x>>y;
            cal_dist = distance(x,y);
           if(pq.size()<k){
                 pq.push(cal_dist);
           }
           else{
             if(cal_dist<pq.top()){
                pq.pop();
                pq.push(cal_dist);
             }
           }
        }
        else {
            cout<<pq.top()<<endl;
        }
    }
       return 0;
}