TELEPORT Help

I’m new here and have been trying to solve my first problem: TELEPORT. I have submitted a bunch of solutions (in c++) which all give the wrong answer about half of the time (and the other half correct). I can’t figure out what goes wrong in some of the cases. I would be very thankful if someone could help me out. I know the memory usage is not optimal, but this does not seem to be the problem.

#include <iostream> 
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;

class Teleport
{
    public:
        Teleport(unsigned long int a, unsigned long int b) : x(a), y(b){}
        unsigned long int get_x(){return this->x;}
        unsigned long int get_y(){return this->y;};
        static void setR(unsigned long int c){R=c;};
        static unsigned long int R;
    protected:
    private:
    unsigned long int x, y;
};
unsigned long int Teleport::R = 0;

void add_teleport(vector<Teleport> &teleports, unsigned long int i, unsigned long int j);
bool check_teleport(vector<Teleport> &teleports, unsigned long int i, unsigned long int j);

int main()
{
    vector<Teleport> teleports;
    unsigned long int Q, r, i, j;
    char ch;
        cin >> Q >> r;
        Teleport::setR(r);
        for(unsigned long int loop=0; loop<Q;loop++)
        {
            cin >> ch >> i >> j;
            if(ch == '+') // add a teleport
                add_teleport(teleports, i, j);
            else if(ch == '?') // check if you can reach teleport j from teleport i
            {
                add_teleport(teleports,0,0); // not optimal memory usage
                if(check_teleport(teleports,i,j)) //print DA if it's possible, otherwise NET
                    puts("DA");
                else puts("NET");
            }
        }

    return 0;
}
//adds a teleport att position (i,j)
void add_teleport(vector<Teleport> &teleports, unsigned long int i, unsigned long int j) {
    Teleport tp(i,j);
    teleports.push_back(tp);
}
//checks if it is possible to reach teleport j from teleport i
bool check_teleport(vector<Teleport> &teleports, unsigned long int i, unsigned long int j) {
     unsigned long int x_1 = teleports[i-1].get_x();
     unsigned long int y_1 = teleports[i-1].get_y();
     unsigned long int x_2 = teleports[j-1].get_x();
     unsigned long int y_2 = teleports[j-1].get_y();
     double mid_x = (double)x_1/2. + (double)x_2/2.;
     double mid_y = (double)y_1/2. + (double)y_2/2.;
     return (fabs(x_1-mid_x)+fabs(y_1-mid_y) <= Teleport::R) && (fabs(x_2-mid_x)+fabs(y_2-mid_y) <= Teleport::R);
}

Hey @john_1, there is a simple fault in your solution. You have not considered the possibility that it may be possible to travel from one teleport to another via multiple intermediate teleports.
If you scroll down to the bottom of the problem page, you will usually find a link to the editorial of the problem where the correct approach is explained. Here you will also find the prerequisites for the problem, which in this case is a couple of relatively advanced data structures called segment tree and disjoin set union. You may search for these online and find out how they work and how to implement them, and then follow the editorial to solve this problem. However, if you are new to competitive programming, I would recommend starting with simpler problems in the Practice section and learning new concepts at a more comfortable pace. Good luck!

1 Like
simple fault
 not considered the possibility that it may be possible to travel from one teleport to another via multiple intermediate teleports.

At first (during contest) i thought that “Oh, its the cakewalk Q for sure!”. And got rekt XD.

@vijju123 usually geometry problems look easy but turn out the opposite :stuck_out_tongue:

//