SRM 347, D1, 250-Pointer (Aircraft)

James S. Plank

Sat Sep 3 10:13:08 EDT 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: May, 2007
Competitors who opened the problem: 525
Competitors who submitted a solution: 255
Number of correct solutions: 152
Accuracy (percentage correct vs those who opened): 28.91%
Average Correct Time: 26 minutes, 43 seconds.

This problem brutalized the topcoders, and I'm not really sure why. Maybe floating point issues?

There are two ways you can solve this, and they are radically different. A key observation for both of them is that you can take the square root out of the problem, and simply look to see if the square of the distance between the two planes is less than or equal to the square of the threshhold. That simplifies the problem a bit.

Solution 1: Calculus

What you do here is come up with a formula for the square of the distance between the two planes, S, at time t:

S(t) = (p1[0]+v1[0]t - p2[0]+v2[0]t)² + (p1[1]+v1[1]t - p2[1]+v2[1]t)² + (p1[2]+v1[2]t - p2[2]+v2[2]t)²

Differentiate this and set it to zero. That's the value of t where the distance is minimized. Check this against the threshhold, and you're done. It will make your life easier to change some of those variables. For example, let x_i = p1[i]-p2[i] and let y_i = v1[i]-v2[i]. That will simplify those equations.

I have code for this solution in Solution-1.cpp.

Solution 2: Binary Search

When I solved this one a second time, six years after the first, I was taking a walk, and didn't have pen, paper or a computer. The equation seemed too messy to do in my head, so I thought about the graph of S(t) vs t. It can only have one of three shapes:

Flat if all of the velocities are equal.
Strictly increasing, if the planes are traveling away from each other in the beginning.
Decreasing then increasing otherwise.

You can solve for the first case instantly. In the other two cases, you can use binary search. Your first task is to write a function S(t). That simplifies your life.

Next, let's graph examples 0, 1 and 2 -- that may help us visualize a solution:

Example 0.

Example 1.

Example 2.

Our goal is to find a value of t, which we'll call min, that minimizes S(t).

Our first observation is that if we find a value of high where S(high) > S(0), then min has to be less than high. That is because high will have to be on the increasing part of that graph, and values of t that are larger than high will have S(t) > S(high).

I found high by setting t equal to one, and then doubling it until S(t) > S(0). You can see those points on the graphs above.

Next, you are going to perform a binary search. You maintain two values: low and high, where you know that min has to be between them. You'll start with low equal to 0. You then successively move low and high towards each other, until they are so close that any answer would be in the roundoff error. At that point, you set min equal to one of them.

Here's how I did that. Suppose you have three points a, b and c, such that:

low < a < b < c < high. Take a look at S(a), S(b) and S(c). Suppose they are stricty decreasing. Then, you know that the minimum point in the graph has to be either between b and c, or between c and high. The following two graphs illustrate the point:

Minimium between b and c

Minimium between c and high

In this case, you can set low equal to b, and repeat the algorithm.

Similarly, if S(a), S(b) and S(c) are increasing, then you can set high to b.

Now, suppose that S(a) and S(b) are decreasing, and S(b) and S(c) are increasing. In that case min has to be between a and c, so you set low to a and high to c. Again, the following graphs will illustrate:

Minimium between a and b

Minimium between b and c

This gives us the information that we need to do the binary search. At each step, we set a, b and c so that divide the interval between low and high into four equal pieces:

a = low + (high-low)/4.
b = low + (high-low)/2.
c = low + 3(high-low)/4.

You should see now, that every step in the binary search halves the interval between low and high. That means that the algorithm will converge quickly.

The final piece of the puzzle involves roundoff error, and it's a bit unfortunate. You repeat this algorithm, narrowing the interval between low and high, until that interval is beneath a threshhold. I used 10^-9 as that threshhold. At that point, you can calculate S(min) and see if it is less than or equal to R*R.

The unfortunate part is that because of roundoff error, you really need to check to see if it is within some threshhold of R*R. Again, I used 10^-9 -- in other words, you need to check to see if S(min) is less than R*R + 10^-9. That handles the roundoff error. If you don't do that, you'll fail one of the cases in the system test. I'm guessing that may be the reason why the success rate here was so low.

I have a solution in this directory, but it is protected to be read-only, because I will probably give this as an in-class or honors lab.