Saturday, November 23, 2002
Choosers
Used as: Level 1Implementation
With a limit of 15 choosers, there are at most 2^{15} configurations of the choosers, and
15 possible locations for the ball. This gives us a total of 15*2^{15} possible states.
We can then move the ball around, according to the rules, and cache the states we reach. Then,
if we ever reach the same state twice, there is a loop, since the sequence of states is totally
deterministic. This can be simply implemented by representing each of the states as a bitmask
and using an array as a cache.
If the input was larger, we might run into memory limits and would have to find a different
solution. One other way to do this is to run the marble through twice, simultaneously, with
one marble moving through two choosers at a time, while the other only goes through one at time.
Then, if the one going twice as fast every gets to the same state as the slow one, there is a
loop somewhere. However, this isn't neccessary.
Comment
Used as: Level 2Implementation
This is a classic string parsing problem. You should start in a CODE state, and then scan the
strings, one at a time. If you hit "//" then you simply ignore the rest of the line. If you
hit "/*", then you ignore until you see "*/". One thing to watch for is the case {"/*/*/"},
where the output should be {}, not {"*/"}. It was this case that caused SnapDragon to resubmit.
The most difficult case to handle is probably that involving double quotes. If you are in the
CODE state, and you see a double quote, you should then ignore all characters until you see
another double quote. However, there is the possibility that there will be an escaped double
quote, which must not terminate the first double quote. A few other things to watch out for
are slashes at the end of strings, and slashes at the end of one string, followed by an
asterisk at the beginning of the next.
Mirrors
Used as: Level 3Implementation
Computational geometry is always ugly, and tonight was certainly no exception. This problem
combined three subtasks. You have to be able to reflect a ray when it hits a segment, find the
intersection of a line and a ray, and find the distance from a line to a point.
Once you solve all of these subproblems using some dot products and cross products and such,
its not too hard to combine then, but its certainly not trivial. You should start with the ray
defined by the start input. Then, you should find the intersection between this ray, and every
mirror. Of all the mirrors that the ray intersects, you have to find the one closest to the start,
and pick it. Then, you also have to check if the ray hits an object before it hits the mirror.
If it does, you are done, otherwise, you reflect the ray with the mirror you found, and repeat
the whole process until you either hit an object, yourself, or the hit no mirrors.
One interesting note to add is that there are classes in java.awt which have methods for finding
the distance from a line to a point, and whether or not two lines intersect. Using this can make
it much easier, but unfortunately for them, all the coders used C++.
By lbackstrom
TopCoder MemberAuthor Profile
