ACM Programming Contest solution walkthrough

In preparation for the ACM World Finals coming up in April, we’ve been running through previous years’ problem sets to get a feel for what we’ll be up against. It’s been interesting, for the most part. The problems definitely require more up-front thought before a solution presents itself, compared to the “regular” contest problems. Since a cursory Google search didn’t turn up anything useful for “ACM contest walkthrough,” I thought I’d write up the solution to one of the more interesting problems we’ve covered.

The problem at hand comes from the 2005 ACM World Finals problem set. Problem B, “Simplified GSM Network,” is the one we’re interested in.

Here’s an image that illustrates the sample input for the problem:

The problem includes a bunch of irrelevant verbiage meant to slow down contestants as they try to figure out what’s important and what isn’t. Input consists of a set of (x,y) coordinates for the towers and italic-numbered cities, plus a list of (city, city) pairs specifying which cities are connected by roads. Finally, another list of (city A,city B) pairs is given, which this time are start and end cities that (might) be connected. Output is the minimum number of cell boundaries a traveler would cross in going from A to B. In the picture above, those numbers (which I’ll refer to as weights) are colored red.

One noteworthy feature of the sample input is that the cell towers fall on a nice, neat grid pattern. This makes determining the number of cell crossings easy: for x and y coords, just take the difference of the floor() values. In code, this would be something like
abs(floor(x1) - floor(x2)) abs(floor(y1) - floor(y2)), assuming that the given cities are located at (x1,y1) and (x2,y2).

Heed Admiral Ackbar’s warning! Nothing in the problem specification constrains the locations of the cell towers. That means that sure as the sun is going to rise tomorrow, those towers are going to be in all sorts of crazy places. That, in turns, means we need to think harder about how we’re going to figure out how many cell boundaries a given road crosses.

My first idea involved doing things roughly the way someone doing it by hand would — construct cell boundaries by starting with small line segments through the perpendicular bisectors of all the lines connecting adjacent cities, and extend until they touch. Unfortunately, that’s complex and error-prone for any but the simplest arrangements of cell towers. Dr. Saunders was the first to have the key insight: every point is in the cell of the closest tower. He drew something on the whiteboard that looked like this:

The black dots represent towers; the green line a road. So for every tower (A / D), there’s a point on the road closest to that tower (q3 / q2), where the teal and green lines meet. And for every such point q, there is, in turn, a (possibly different) tower closest to q. In the image above, there are three red dots, marking the three cell boundaries the green road crosses. And there are a total of four towers that are closest to at least one of the five q points. So, take the cardinality of the set of closest-towers and subtract one, and that is the number of cell boundaries crossed.

If that’s not clear, it may make more sense (at least it does to me) if you work the logic out backwards. The number of cell boundaries crossed is one less than the number of cells the road travels through. So how many cells does the road travel through? Well, if the road travels through tower A’s cell, there must be some point on the road that is closer to tower A than any other tower, because that’s a requirement for any point being inside a tower’s cell. So, we take the n points on the road closest to the n towers, and then the set of towers closest to those n points. That gives us the set of cells the road passes through.

OK, so now we can figure out the weights for each road, at least in theory. That’s all well and good. The next step is to figure out how we get between cities in the minimum number of cell-boundary crossings. This screams graph theory: our cities are nodes, our roads edges. Computer scientists call this the shortest path problem, and there are a variety of algorithms to solve it. As it turns out, there’s no known algorithm in existence that will only give the shortest path between two nodes (cities). You can’t find out the shortest path from A to B without also discovering, along the way, shortest paths from A to every other node in addition to B. If your algorithm doesn’t know all the shortest paths starting at A, it’s possible that one of those other paths could lead to a better answer.

Because we could be looking for shortest paths between any pair of nodes, and because our graph isn’t too big, we’ll use a very cool algorithm called Floyd-Warshall to find the shortest path between every pair of cities.

Floyd-Warshall is clever, concise, and easily parallelizable. I love it. The core of the algorithm is this: suppose you have nodes labeled 1 to n. And suppose you know the shortest path between nodes i and j, such that the path only involves nodes labeled with numbers smaller than k.

Then if you allow the path to include node k, there are two choices: either the path you already have is shorter, or the shorter path is now the path connecting nodes i and k, plus the path connecting k and j.

This can be expressed as a remarkably simple and elegant way, with three nested loops:

          for(int k = 0; k < n;   k) {
for(int i = 0; i < n;   i) {
for(int j = 0; j < n;   j) {
spath[edge(i,j)] = min(
spath[edge(i,j)],
spath[edge(i,k)]   spath[edge(k,j)]);
}
}
}

Back to the problem at hand. What we have, from a high level, should work. Compute weights by taking each road, then computing the closest point on the road to each tower, and then the closest tower to each of those points. Take the set of those closest towers, and the weight for the road is one less than the set’s cardinality. Then, after all the weights have been calculated, use those weights as part of Floyd’s algorithm, which gives us what we want: a shortest-path value for the start/destination city pairs.

There’s one problem left, though. I glossed over a pretty major portion of the actual program. Namely, how does that geometry stuff actually work in code? There are no pretty pictures drawn inside the program. We get numbers in, crunch ’em, and out come results.

This is one of the bits I think is the coolest. Toy classes like Point are usually one of the first examples given by books trying to teach Object-Oriented programming. But the ACM contest isn’t about OO masturbation. Time spent typing out a Point class implementation is time NOT spent solving the actual problem at hand. Thus, I present to you the best-kept secret of the STL for programming contests: the complex class.

It’s technically meant for representing values on the complex plane, but if we sweep the imaginary constant under the rug, we’ve got a handy-dandy general representation of points on a 2D Cartesian plane. Best of all, the STL gives us, for free, a bunch of methods that have geometrical meaning, including vector addition and subtraction! The key idea here is an equivalence between points and vectors. A point (x,y) is equivalent to the (x,y) position vector — that is, a vector from (0,0) to (x,y). Any given vector, or line segment, can be represented with a pair of complex numbers: the location of the tail of the vector, and the other is the vector’s direction and length.

If we have points such as p = (4,5) and q = (1,1), the STL gives us length and angle for free: abs(q) == sqrt(2) and arg(q) == 0.785398, which is 45 degrees in radians. Plus, if we want the distance between p and q, it’s simply abs(p - q) which is of course 5. But the fun’s only getting started! What we really want is some elementary linear algebra.

We’ll start with the dot product. The dot product of (a,b) and (c,d) is defined as (ac bd). Multiplying complex numbers (a ib) * (c id) yields (ac – bd) i(ad bc). Note that the real part is almost what we want, but the sign of the second part is wrong. So, we merely multiply by the complex conjugate, and take the real portion of the result. And behold: dot product of 2D vectors in one line of code!
double dot(P a, P b) { return real(a*conj(b)); }

P is just shorthand for an STL complex point. Anyways, dot products are nice, but what they REALLY let us do is take projections. The Wikipedia page is quite indecipherable and gives no outstanding indication of how tremendously useful projections are to us. The MathWorld page for projections is slightly better, but not by much.

Here’s a diagram that’s a bit more relevant to what we’re doing.

Suppose we have the line segment (vector!) AB, and the point P. We wish to find the coordinates of the point Q on AB that is closest to P. Sound familiar? Luckily for us, the wonderfulness of linear algebra makes this easy. So we just take the direction vector AP — that’s (P – A) — and project it onto the direction vector AB. That gives us a direction vector AQ, which we add to point A to yield… the point Q! Magical stuff, math is. All of that, with two lines of code.
P proj(P v, P u) { return u * P(dot(u,v)/dot(u,u)); }

Going back to the picture with the blue lines, we now have a concrete method for finding those q values. There’s just one problem — we’re actually doing projections onto the LINE AB, not just the line segment. So, when we’re doing it, we might get points that aren’t actually on our road. Not good, but the fix is simple: if the point is off the line segment, instead use whichever endpoint of the segment is closest to the point. Okay, so how do we figure out when a point is on (or off) a given line segment?

There are two approaches we can take here. The first is to solve the more general problem of “where is a given point in relation to a given vector?” Called the ccw function, short for counter-clockwise, it takes three points a, b, and c, and determines whether going from a to b to c requires a clockwise, counterclockwise, or no turn at all. We can use the cross product to get a signed area for the parallelogram defined by the vectors ab and ac (labeled a and b on the wikipedia page). If the area is zero, the points a, b, and c all fall on the same line; otherwise, a turn is required, and the whole function is perhaps half a dozen lines.
double cross(P a, P b) { return -imag(a*conj(b)); }

ccw is one of the building blocks used in finding convex hulls and the area of arbitrary convex polygons, two other geometry problems that crop up quite often in ACM contest problem sets. I used it last year on a problem that involved finding the area of the intersection of convex hulls. However, it has a problem. Computers are limited in the precision of the numbers they can manipulate. So sometimes, the area that the cross product will return won’t be 0, it’ll be a very, very, very small number, like one-quadrillionth (1e-15). That bites (so to speak), and it bit me. So, anyways, we could use ccw to determine whether or not the q-points we’ve computed fall within the line segment or not. But that would be overkill.

More specifically, doing so would ignore information we already have about those q-points: namely, they aren’t arbitrary points. We know that they fall somewhere along the line AB, we just don’t know if they fall within the line segment AB. So the problem we’re actually faced with is equivalent to a much simpler problem: if we draw a box around AB, does our q point lie inside the box?

It looks like we can simplify even further, to merely ask: does our point fall within the bounds of the x-coordinates of the line? After all, if it falls outside the bounds of the x-coordinates, it cannot be on the line segment. However, contrary to Mike Huckabee’s misguided beliefs, (~X -> ~S) -/-> (X -> S). In particular, checking only the X coordinate and not the Y will fail in the case of points on a straight vertical line.

Now, finally, we have all the pieces we need. Calculate weights, then do find shortest paths with a standard algorithm. The devil, as always, is in the details.

For those who want it, here’s the full C program.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s