|
Match Editorial |
 |
|
||||||||||||
| |||||||||||||
| MATCH EDITORIAL LINKS: | |||||||||||||
|
|||||||||||||
| |||||||||||||
May 29, 2002
The Problems
LEVEL ONE
The Level One problem was a very annoying math-intensive problem (yes, I'm mostly saying this because I failed it due to a dumb bug.) The trick was to recognize that wheelsize/spokes was a fraction, and give both fractions a common denominator. Then it was the Least Common Multiple of them - multiply them both together and divide by the GCD - take that, and multiply it by 2 (24 frames in a second, but 12 inches in a foot.) And if it was an even division, subtract 1, the easiest way being to subtract 1 before doing the division. I can only imagine what strange bugs other people had. My problem was only checking to see if it was even before multiplying by 2. If the multiply-by-two made it an even division, mine would fail, and this is what dmwright (successfully) challenged me on. SnapDragon's solution is quite clean, though a little puzzling. dmwright's solution is good also, though it's very verbose, using BigInteger all over the place. I find venco's solution to be the easiest to read of all the working Room One solutions.
LEVEL TWO
The Level Two problem required a little bit of thought. The easiest way to approach it was to choose a word to be the "pivot", or the downward-hanging word (in my visualization, at least - I know of at least one other person who visualized the pivot as being horizontal.) From here you simply tried all the possible arrangements of the other two words. They couldn't start on the same vertical position, and they also couldn't start next to each other unless they were completely contained on different sides on the pivot. All that's left is to make sure that their start position actually has matching letters - take the best value you get from this. It's worth noting that if you choose the first word as the pivot, every example will work, but your solution will not - while the positions of the other two words don't matter, you must test every word as a potential pivot. I chose to do this with next_permutation - I did twice as many calculations as necessary (due to it also swapping the two words that weren't the pivot) but runtime wasn't an issue with this problem. SnapDragon did the same as I did, right down to next_permutation, only his works :) I believe my bug was with the "width" calculations. Other solutions were to make a function to process three words, then hardcode in three possibilities (one pivot word for each), and this is what reid did.
LEVEL THREE
As for the Level Three, the easiest way to explain it algorithmically is to dive into graph theory. Imagine each "open area" as a node, and each potential mineshaft as an edge (weighted appropriately). We'll also want a node for the "outside". Now what we want to create is something known as a "minimal spanning tree" - the tree connecting all the points with the smallest total weight. Do a search on Google and you'll find a lot of very complex descriptions of what is actually a very simple algorithm. The algorithm is: Find the lowest-weight edge from a node you've already connected to to a node you haven't. Connect them. Repeat until all nodes are connected. That's all. In my case I didn't bother constructing the graph, I just did the work on the data itself (copied out of the Topcoder input data, and with a row of empty space on the top for the "open air", just for ease of coding). I'd find the shortest path from a section I'd been to to a section I hadn't, then fill in the new section as "a place I've been". And repeated until I ran out of closed areas. I recommend my solution (ZorbaTHut's) for readability, as I ended up with several nicely-named functions, though SnapDragon's is impressive due to sheer brevity of code.
