TCO 2007, Q1, 1000-Pointer (Alarmed)

James S. Plank

Thu Oct 18 14:44:06 EDT 2012 (Recently revised: Mon Nov 12 16:34:30 EST 2018)

In case the topcoder problem description isn't showing, I'm going to summarize the problem below:
This Topcoder problem is difficult, but the cool thing about it is that it transforms what appears to be a problem involving circles and floating point numbers into a graph problem that we solve with Depth-First-Search.

I would not expect you to figure this out on a test. However, it shows the power of structuring problems with graphs. We'll see more of that later in the semester.

As always, let's wrap our heads around the problem with the examples. Here's a drawing of example #0, where there is one sensor at (50,2) with a threshold of 87.

I'm only showing the relevant part of the room. I've drawn two circles around the sensor. The first has a radius of 1, which means that when the intruder's noise level is 87, the sensor can detect the intruder when the intruder is at or within that circle. The second has a radius of 2, which means that when the intruder's noise level is at 348, the sensor can detect the intruder when the intruder is at or within that circle. This is because (A/d2) ≥ 87.

It should be pretty clear that so long as the intruder's noise level is less than 348, he can bypass the sensor. Therefore, the answer is any value that is less than 348 by 10-9 or less. The answer that the example gives is 347.99999999999994, which certainly fits the bill.

Let's try example #2:

I've drawn circles where the radius equals 5, and therefore it can detect noises where A ≥ 25, and where the radius equals 49, and therefore it can detect noises where A ≥ 2401. It should be clear from the picture that so long as A < 2401, the intruder can get through. Therefore, the answer is any value that is less than 2401 by 10-9 or less.

One more picture. Let's look at example 2, when A = 1538:

Well, I can see why 1538 is the crossing point. But how to turn this into a solution? And what does this have to do with graph theory?

Here's a better example. Let's move one sensor from (11,10) to (18,15), and another from (62,25) to (62,30), and keep A at 1538:

It should be clear from this picture that at this value of A, the intruder cannot pass from one door to another. Those three sensors and the walls make it impossible. Hopefully this example gives you a clue about turning the problem into a graph.


Turning an instance of the problem into a graph

Suppose you have affixed a value of A, like 1538 in that last picture. Then, you create a graph which has one node per sensor, plus a node for the walls to the left of the doors (that includes the left wall and the left segments of the top and bottom walls), and a node for the walls to the right of the doors.

You insert an edge between two sensors if their circles intersect for that value of A. You also insert an edge between a sensor and a "wall" node if the sensor's circle intersects the wall. If the edge of the circle intersects a door, then you put edges to both wall nodes. As an example, here's the graph of that last set of sensors when A = 1538:

If there is a path in this graph from the "Left" node to the "Right" node, then the intruder cannot pass.

So, our first piece of code is to write a procedure called TestA(), which takes a value of A, creates the graph and prints it out. We read in A before calling it to test it. It's in Alarmed-1.cpp, and below. It calculates the radius of a sensor as: r = sqrt(A/T). It then checks the distance between every pair of sensors, and if that distance is less than the sum of the two radii, then it creates an edge in the graph. Finally, it checks for intersecting with the "Left" node and "Right" node. That check is a bit complex -- I've put comments in there so you can see each case: Alarmed-1.cpp

#include <string>
#include <cmath>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class Vertex {
  public:
    int visited;
    vector <int> adj;
}; 

class Alarmed {
  public:
    int TestA(double A);
    vector <double> X;
    vector <double> Y;
    vector <double> T;
    vector <Vertex> V;
    double noise(vector <int> x, vector <int> y, vector <int> threshold);
};

int Alarmed::TestA(double A)
{
  int lw, rw;
  int i, j;
  vector <double> Radius;
  double d;
  int intersect;

  V.clear();
  V.resize(X.size()+2);
  lw = X.size();
  rw = X.size()+1;
  for (i = 0; i < X.size(); i++) {
    Radius.push_back(sqrt(A/T[i]));
    printf("Radius of %d: %lf\n", i, Radius[i]);
  }
  cout << endl;
  for (i = 0; i < X.size(); i++) {

    for (j = 0; j < i; j++) {
      d = sqrt(((X[i] - X[j])*(X[i]-X[j]))+
               ((Y[i] - Y[j])*(Y[i]-Y[j])));
      printf("Distance between %d and %d: %lf (%lf)\n", i, j, d, Radius[i]+Radius[j]);
      if (d <= Radius[i]+Radius[j]) {
        V[i].adj.push_back(j);
        V[j].adj.push_back(i);
      }
    }
 
    /* Check for edge to "Left" */

    intersect = 0;
    if (X[i] <= Radius[i]) intersect = 1;  /* Intersect with left wall */

                                 /* Intersect with top or bottom wall, left: */
    if (X[i] <= 50 && (Y[i] <= Radius[i] || Y[i]+Radius[i] >= 100)) intersect = 1;

    if (X[i] > 50) {             /* Check to see if either door is in the circle */
      d = sqrt((X[i]-50)*(X[i]-50)+(Y[i]*Y[i]));
      if (d <= Radius[i]) intersect = 1;
      d = sqrt((X[i]-50)*(X[i]-50)+((100-Y[i])*(100-Y[i])));
      if (d <= Radius[i]) intersect = 1;
    }
    if (intersect) {
      V[lw].adj.push_back(i);
      V[i].adj.push_back(lw);
    }

    /* Check for edge to "Right" */
    intersect = 0;
    if ((100-X[i]) <= Radius[i]) intersect = 1;
    if (X[i] >= 50 && (Y[i] <= Radius[i] || Y[i]+Radius[i] >= 100)) intersect = 1;
    if (X[i] < 50) {
      d = sqrt((50-X[i])*(50-X[i])+(Y[i]*Y[i]));
      if (d <= Radius[i]) intersect = 1;
      d = sqrt((50-X[i])*(50-X[i])+((100-Y[i])*(100-Y[i])));
      if (d <= Radius[i]) intersect = 1;
    }
    if (intersect) {
      V[rw].adj.push_back(i);
      V[i].adj.push_back(rw);
    }
  }

  for (i = 0; i < V.size(); i++) {
    printf("%d:", i);
    for (j = 0; j < V[i].adj.size(); j++) printf(" %d", V[i].adj[j]);
    printf("\n");
  }
}

double Alarmed::noise(vector <int> x, vector <int> y, vector <int> threshold)
{
  int i;
  double A;

  for (i = 0; i < x.size(); i++) {
    X.push_back(x[i]);
    Y.push_back(y[i]);
    T.push_back(threshold[i]);
  }
  
  cout << "Enter A: ";
  cin >> A;
  i = TestA(A);

  return 0;
}

We compile and run it, and the graphs look as they should. In example 0, there are no edges when A=87, but there are edges from the sensor to the left and right nodes with A=348. When A is slightly smaller, there are no edges:

UNIX> cp Alarmed-1.cpp Alarmed.cpp
UNIX> g++ Alarmed-Main.cpp
UNIX> a.out 0
Enter A: 87
Radius of 0: 1.000000

0:
1:
2:
0
UNIX> a.out 0
Enter A: 348
Radius of 0: 2.000000

0: 1 2
1: 0
2: 0
0
UNIX> a.out 0
Enter A: 347.9999999
Radius of 0: 2.000000

0:
1:
2:
0
In example 1, we test the two circles in the drawing -- A=25 and A=2401. In both cases, there are edges from a sensor to a wall, but in the second, there is also an edge between sensors:
UNIX> a.out 1
Enter A: 25
Radius of 0: 5.000000
Radius of 1: 5.000000

Distance between 1 and 0: 98.000000 (10.000000)
0: 2
1: 3
2: 0
3: 1
0
UNIX> a.out 1
Enter A: 2401
Radius of 0: 49.000000
Radius of 1: 49.000000

Distance between 1 and 0: 98.000000 (98.000000)
0: 2 1
1: 0 3
2: 0
3: 1
0
UNIX> 

Doing the DFS:

Next, we do the Depth-First-Search. It is like the connected-components DFS, and you only call it from the "Left" node. All nodes connected to the "Left" node will have their visited fields set after the DFS, so you simply test to see if the "Right" node is connected to the "Left." If so, the intruder cannot pass, and 1 is returned. Otherwise, the intruder can pass, and 0 is returned.

The code is in Alarmed-2.cpp. I'm only including the DFS and the final testing in TestA:

void Alarmed::DFS(int n)
{
  int i;

  if (V[n].visited) return;
  V[n].visited = 1;
  for (i = 0; i < V[n].adj.size(); i++) DFS(V[n].adj[i]);
}

int Alarmed::TestA(double A)
{
  ....

  for (i = 0; i < V.size(); i++) V[i].visited = 0;
  DFS(lw);
  return (V[rw].visited);
}

When we run it, it works as anticipated:

UNIX> cp Alarmed-2.cpp Alarmed.cpp
UNIX> g++ Alarmed-Main.cpp
UNIX> a.out 0
Enter A: 87
0
0
UNIX> a.out 0
Enter A: 348
1
0
UNIX> a.out 0
Enter A: 347.9999999999
0
0
UNIX> a.out 1
Enter A: 2401
1
0
UNIX> a.out 1
Enter A: 2400.9999999
0
0
UNIX> 
The last piece of the puzzle is to find the right value of A. I'm going to do it by binary search. I'll start with A equal to one and I'll keep multiplying it by 10 until I find a value where the intruder cannot pass. Call that value higha. And start with lowa equal to zero. Then iterate the following: Do that until the difference between lowa and higha is less than 10-9. There's a subtlety here, that I didn't catch until I submitted the program and got case 42 wrong -- if lowa and higha are large enough, then their difference will be greater than 10-9, however when you calculated mida, it will equal either lowa or higha. Therefore, I also test for that condition and return when that happens. Here's the relevant code (in Alarmed-3.cpp):

double Alarmed::noise(vector <int> x, vector <int> y, vector <int> threshold)
{
  int i;
  double lowa, higha, mida;

  for (i = 0; i < x.size(); i++) {
    X.push_back(x[i]);
    Y.push_back(y[i]);
    T.push_back(threshold[i]);
  }
  
  for (higha = 1; !TestA(higha) ; higha *= 10) ;
  lowa = 0;

  while(higha-lowa >= 0.000000001) {
    mida = (higha+lowa)/2.0;
    if (mida == higha || mida == lowa) return lowa;
    if (TestA(mida)) {
      higha = mida;
    } else {
      lowa = mida;
    }
  }
  printf("Final answer: %.11lf\n", lowa);
  return lowa;
}

Test it out:

UNIX> cp Alarmed-3.cpp Alarmed.cpp
UNIX> g++ Alarmed-Main.cpp
UNIX> a.out 0
Final answer: 347.99999999996
348
UNIX> a.out 1
Final answer: 2400.99999999984
2401
UNIX> a.out 2
Final answer: 1537.99999999990
1538
UNIX> a.out 3
Final answer: 3295.57178787468
3295.57
UNIX> 
Time to submit!

In conclusion

Yes, this is a hard program. However, again, I'm hoping you see how the graph theory has made the problem solvable.