Match Editorial

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 Problems

Value	250
Submission Rate	133 / 135 (98.52%)
Success Rate	111 / 133 (83.46%)
High Score	Sleeve for 249.81 points (0 mins 47 secs)
Average Score	233.84 (for 111 correct submissions)

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.

Value	500
Submission Rate	85 / 135 (62.96%)
Success Rate	42 / 85 (49.41%)
High Score	KSUGuy for 472.96 points (6 mins 52 secs)
Average Score	313.99 (for 42 correct submissions)

Value	250
Submission Rate	127 / 130 (97.69%)
Success Rate	99 / 127 (77.95%)
High Score	Eryx for 247.79 points (2 mins 41 secs)
Average Score	207.63 (for 99 correct submissions)

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³¹ - 1 works well), and a maximum to a very low number (-2³¹ 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)}.

Value	1000
Submission Rate	53 / 135 (39.26%)
Success Rate	22 / 53 (41.51%)
High Score	shuniu for 832.96 points (13 mins 17 secs)
Average Score	563.26 (for 22 correct submissions)

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.

Value	500
Submission Rate	58 / 130 (44.62%)
Success Rate	36 / 58 (62.07%)
High Score	antimatter for 323.68 points (23 mins 54 secs)
Average Score	228.81 (for 36 correct submissions)

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 self-consistent 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.

Value	1000
Submission Rate	2 / 130 (1.54%)
Success Rate	1 / 2 (50.00%)
High Score	tomek for 557.95 points (31 mins 3 secs)
Average Score	557.95 (for 1 correct submission)

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:

• Find the tree that you would hit first in this diameter (if there isn't one, return -1).
• Travel around that tree until you are closest to the center. There are two cases here:
1. The point on that tree closest to the center is outside the circle of radius 10 (simpler).
2. The point on that tree closest to the center is inside the circle of radius 10. In this case, you then have to intersect that tree with the circle of radius 10 at the center of the woods and use that point instead.