Match Editorial

		MATCH EDITORIAL LINKS:
	Room 1 Review Archive   Rookie Review Discuss this match   Problem Set Want to write a feature?   Lessons Learned

The Level One problem was a bruteforcable geometry problem with a few catches. The easiest way was to simply test all possible lines, calculate which points lay on the lines, and return the best of those. Implementation got tricky. I'm using my solution for reference because I understand it and because, in the end, it's quite clean. los/loe are Line One Start and Line One End, lts/lte are Line Two Start and Line Two End. Technically speaking the lines don't end, but it's useful to think of them as always having to go "through" two points. The core of my solution is a simple loop to determine whether a given point is intersected by any line. Here's where things get a little tricky, so I'll make a paragraph break and explain that chunk of code.

Given three points A, B, and C, it's easy to visualize the fact that if C would lie on an infinite line through A and B, then the slope from A to B must equal the slope from A to C. As many know, math isn't my strong point, so I didn't prove this, I just trusted it. Early algebra tells us that the slope calculation is rise-over-run, so ( ABrise / ABrun ) == ( ACrise / ACrun ). Unfortunately, this involves non-integer math, and as any TopCoder veteran knows, floating-point is something to be avoided whenever possible. Luckily, algebra saves us here - multiply both sides by ABrun and ACrun to get ABrise * ACrun == ACrise * ABrun. I'll be the first to admit that this isn't intuitive, but it works, and you'll notice two statements of that type in that enormous if statement of mine.

Some people decided to cast to a 64-bit int of some sort. I didn't, and it's not necessary The largest possible rise is 40,000, and the largest possible run is 40,000 as well. 40,000*40,000 is only 1,600,000,000, and a signed 32-bit integer goes up to about 2,100,000,000. On the other hand, I spent a few seconds thinking about it, so it might have been to my benefit if I'd just reflexively cast to a 64-bit int.

You'll also notice a few tests for whether we're actually talking about an endpoint. In retrospect this isn't necessary - working out the calculations it definitely won't matter, it will return the same thing anyway - but it made me feel better, since division by zero is generally a bad thing. Note that, even if you trust floating-point accuracy, the potential division by zero would have possibly caused problems.

The other thing worth mentioning is that obviously if there's only one point, there's not going to be any way to draw a line from one point to another. If there are zero points, there's not even anything to intersect! This is the bug venco found in dgarthur's code - I solved it with a simple size test, before the main loop. Obviously if there are less than three points we can just throw a line through all of them - in fact, any test with less than five points can be solved with no points remaining.

The Tron Racing (Level Two) was more of a "here's the code, go implement it" than anything else. You could either make a field with "wall" around the outside or just check bounds. I believe checking bounds would be easier by far - the fact that I didn't is part of what contributed to my horrible score. Another thing worth pointing out is the racer-collision algorithm. It's important to not remove any trails or racers until you've checked *all* the racers for death. Removing pairs of racers causes failures if three racers collide at once - the "third" keeps going on. And removing a racer the instant you detect its death might cause the disappearance of its wall that another racer had just hit.

Speed wasn't an issue - the maximum runtime of this problem was under 1250 cycles (I believe it's 49*49/2+1, but I could be off on that.) One could potentially get an out-of-bounds error if you made a 1250-size array for holding instructions, however, since instructions could be at the 1250 point.

I fully expect that I got one of the lowest scores on the 1100, if not *the* lowest - in general, it was something that either you got instantly or couldn't figure out, and I figured it out at the last minute. My solution was, eventually, the dynamic programming solution - I don't have a clue what the divide-and-conquer solution was.

The trick was to look at the problem sort of inside-out. If you tried to approach it like a single car starting from the beginning, going to the end, and back again, you were doomed. The best way to look at it is like two cars, both starting from the beginning, both ending at the finish. Iterate through the locations from left to right, and each location you have two choices - either the "first" car goes there, or the "second" car goes there. You ended up with a 2-dimensional array at each step, one dimension for the potential positions of the first car, one dimension for the potential positions of the second car. I decided not to attempt to prove I could do the work in a single array and used two arrays, one for reading and one for writing, copying the write array over the read array after each step (ready for the next one) and resetting the write array to an appropriately chosen "infinity" value. (I started with 1, then hit 0 a lot, and added .0 at the end so it was floating-point - reid simply typed 1E12, which I consider significantly classier.) Then for each position in the read array, set the appropriate two positions in the write array to the minimum of the current value and what it would be if that car had taken the trip. It's hard to explain in text - I recommend looking at my solution (ZorbaTHut's), since, for obvious reasons, it's the closest to what I wrote.