|
Match Editorial |
 |
|
||||||||||||
| |||||||||||||
| MATCH EDITORIAL LINKS: | |||||||||||||
|
|||||||||||||
| |||||||||||||
June 24, 2002
The Problems
Division-II Easy
200pt - LStrings.sumLength
This one was simple enough to just follow the instructions to get right. Keep a counter, set it to zero. For each character in each string, check to see if it's a dash. If it isn't, add one to the counter. At the end, return the counter. I haven't yet seen a single failed solution that would have passed the example cases.
Division-II Medium
550pt - PrimeCount.howMany
This one is straightforward at first glance - just set up another counter and a loop to go through each number and divide it by its factors until it reaches 1. While this works for most of the example cases, it fails rather dramatically when a number is a multiple of two large primes, or even worse, when a number *is* prime. A program can do 100,000,000 simple operations in eight seconds without much trouble, but there's no way you're ever going to manage 5,000,000,000 modulus operations in that much time.
The solution, however, is actually quite simple. The inner loop that times out looks like "for( factor = 0; factor <= number; factor++ )". Simply change it to "for( factor = 0; factor * factor <= number; factor++ )" and it will square-root the number of iterations you have. Once you're done, just add one to the count, since "number" will have a factor left over, and return that value.
Division-I Easy
250pt - BadCoding.numDecode
There are various ways to code this - the string size limitation of 20 makes it quite easy. Probably the simplest way is as a recursive function. Take a hypothetical recursive function "count". At each digit, check to see if this digit and the next digit form a number less than 26. If they do, return count( position + 1 ) + count( position + 2 ). It's an O( 2^n ) algorithm, and 2^20 is only a million, so it'll run easily fast enough. If you were worried about speed, you could store the results as you continued and refer to the stored versions.
Another solution is to keep a small array of all the possible states it could be in. There are only three - "ready to start another number", "right after a one", and "right after a two". For each digit you just need to update the various positions, and at the end, return the "ready" count.
Division-II Hard/Division-I Medium
1100pt/550pt - RangeSort.valueAt
It's quickly clear that simple brute-force just won't cut it. That would be a lot of tests. My approach was to put together a list of all the locations where the number of ranges a given number in would change. For example, given [1,5],[3,7], it could change at 1, 3, 6, and 8 (the *first* number it changes it, not before the number). I did this by adding 1 to the upper bounds and putting all the numbers together into a giant set. Of course, this could generate a few false positives - [1,1],[2,2],[3,3], for example, would look at 1,2,3,4, but with this approach it's fast enough.
Once I'd put together this table I simply started from the lowest number and went up one "important point" at a time. Multiplying the number of ranges the number was in by the distance to the next number gave me how many total array items our theoretical array would contain. Once I knew it was in the current "section", dividing the number of array items left by the number of ranges, and adding the start of the current section, gave me the answer.
SnapDragon had a rather nice solution also. While it's too slow to scan 50 integers for each of twenty million numbers, it's fast enough to prepare the arrays intelligently and just count from the bottom on up. He doesn't bother keeping a relationship between which array is which, and it really doesn't matter - if it's a "lower bound" it means "add one to the number of arrays it's currently in", and if it's a "upper bound" it means "subtract one to the number of arrays it's currently in".
John Dethridge, on the other hand, used a binary search, although I have to admit I don't understand why he didn't just use a similar algorithm counting from the bottom.
Division-I Hard
1000pt - OneWayRoad.totalCost
The key on this one was coming up with a working algorithm. Basically, you only cared whether or not it was possible to make a set of roads to fulfill the condition - you don't care *what* those roads are. The simplest way, by far, was to remove a road and see if you could still get from one end to the other end (basically ensuring that there are at least two ways to get from point A to point B.) Do this for all the roads - if you can, congrats, you're done. If you can't, once again you're done. That's really all there is to it. For the test of "getting from point A to point B" you could use Dijstra's or Floyd's - note, however, that there might be up to 100 locations, and 100 locations with Floyd's is slow. Although if there *are* more than 50 locations there's no way it's possible.
SnapDragon and I (and possibly several others) used a much ickier algorithm that I don't recommend, but I thought I'd record for posterity. Simply put, find a loop and collapse all the nodes in the loop into a single node. You can easily end up with multiple connections from this ubernode to another node, so you'll have to keep track of this. Once you're out of loops, with any luck you'll have a single point left - if you do, that section of the graph works. If you don't, it's impossible.
Note that there's a flaw with this algorithm - it won't work with disconnected graph segments. The solution, of course, is to simply feed all the graph segments in one at a time, and if a single one doesn't work, the whole thing is impossible.
