Tuesday, June 29, 2004 Match summary Congratulations to tomek for being the only one to successfully solve all three problems in Division 1. Also of note is a newcomer, shuniu, scoring the highest in Division 2. The match tonight was relatively smooth  a few issues with input verification surfaced late in the game, but were solved with minimal impact to the contest. The Division 1 500 point problem took many contestance quite a while to code, likely due to the long and detailed problem statement. Division 1 1000 posed much more of a problem, unless you know trigonometry very well; even though you were given most of the algorithm and formulae necessary to solve, it was still a headache to code within the time limits. Overall, Division 2 had a moderate day, with relatively straightforward problem, but the 500 point problem seemed to trip people up with all the min/max code.
The ProblemsMultiplesUsed as: Division Two  Level One:
This is about as easy as they come. Very nice score, Sleeve, with only 47 seconds to solve. The simplest solution, which works because the constraints are so low, is best here: loop from min to max and check each number to see if it is divisible by factor. If you want to get more efficient, you can increment min until you hit a number divisible by factor, decrement max until you hit a number divisible by factor, then subtract min from max, divide by factor and add 1. ElevatorLimitUsed as: Division Two  Level Two: Used as: Division One  Level One:
This problem is all about minimums and maximums. The basic algorithm is as follows: Initialize a counter to 0, a minimum to a very high number (2^{31}  1 works well), and a maximum to a very low number (2^{31} would work here). The minimum and maximum will keep track of the lowest and highest counter ever gets. For each stop x the elevator makes, decrement counter by exit[x], update your minimum, increment counter by enter[x], and update your maximum. Once you're done, you know the how big the range of people is that were on the elevator throughout the simulation (maximum  minimum). If the range is bigger than physicalLimit return an empty array because it's an impossible situation. Otherwise, the return value is {max(minimum, 0), min(physicalLimit, physicalLimit  maximum)}. WordSpacesUsed as: Division Two  Level Three:
This problem involves nested loops  one for each word given in the array, one for each starting point in the sentence, and one for how many characters to skip. My approach was simply to append the characters from a starting point, skipping the right number of characters, and see if the final result started with the word I was looking for. If so, that's the return, otherwise keep looking. If one is never found, return 1 for that word. RPGRobotUsed as: Division One  Level Two:
A favorite of mine (because I actually wanted to do this in the past), this one is maybe a little tricker than it looks. You have to consider three states of a "wall": on, off, and unknown. The unknown state is used for anything which is off the given map. Because we're guaranteed selfconsistent input, we don't even have to keep track of the unknown area  if we see it, we can forget about it because the next time the robot moves into an adjacent (or the same) square, the same data will be presented to us. The solution that I used (and many others) is to initially assume that all spaces are valid (all spaces with an odd x and y coordinate, because those are the <GAMESPACE>s mentioned). After this, you iterate through each move the robot makes  if the description given makes a starting location invalid, mark it as invalid. Once you're done iterating through each move, return all the leftover ones. An edge case that seemed to catch some people off guard was that the very edges of the given map do in fact border spaces off the map  and you have to take this into account and make sure that just because the robot could be off the map that you don't ignore the known walls there. DogWoodsUsed as: Division One  Level Three:
For this problem, you were basically given the algorithm and left to do the math yourself. The boring formulae for intersection of two circles was given, so you just had to plug that in and hope you didn't mistype something. What you weren't given was how to determine the arc length given two points on a circle; however, a background in trigonometry would lead you to a relatively simple solution using arctan (of course, you have to write your own, most likely, because the real function arctan has a range from pi to pi, and you need a range that covers the whole circle. Since all the really interesting cases were gotten rid of by the constraints (intersecting trees, trees whose closest points to the center were at the same distance from the center as another tree's furthest point from the center, trees that covered the center), all you really had to do was iterate until the dog hit the center:

