JOIN

 Room 1: - Summary - Problems - Log - Photos Room 2: - Summary - Problems - Log - Photos Room 3: - Summary - Problems - Log - Photos Room 4: - Summary - Problems - Log - Photos Championship: - Summary - Problems - Log - Photos

Championship Problem Analysis & Opinion

Saturday, November 23, 2002

Choosers
Used as: Level 1

#### Implementation

With a limit of 15 choosers, there are at most 215 configurations of the choosers, and 15 possible locations for the ball. This gives us a total of 15*215 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 2

#### Implementation

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 3

#### Implementation

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 Member
Author Profile

Championship Chrono Logs
8:00:00 AM - zoidal opens the Level One problem
8:00:01 AM - derkuci opens the Level One problem
8:00:01 AM - ambrose opens the Level One problem
8:00:02 AM - DjinnKahn opens the Level One problem
8:18:48 AM - DjinnKahn opens the Level Two problem
8:19:21 AM - ambrose submits the Level One problem for 180.11 points
8:19:29 AM - ambrose opens the Level Two problem
8:20:53 AM - zoidal opens the Level Two problem
8:25:52 AM - ambrose submits the Level Two problem for 476.36 points
8:26:03 AM - ambrose opens the Level Three problem
8:30:32 AM - derkuci submits the Level One problem for 140.90 points
8:30:44 AM - derkuci opens the Level Two problem
8:32:07 AM - DjinnKahn submits the Level Two problem for 416.07 points
8:32:14 AM - DjinnKahn opens the Level Three problem
8:35:04 AM - zoidal submits the Level Two problem for 407.77 points
8:35:09 AM - zoidal opens the Level Three problem
8:39:20 AM - derkuci submits the Level Two problem for 459.37 points
8:39:30 AM - derkuci opens the Level Three problem
9:04:41 AM - ambrose submits the Level Three problem for 491.61 points
9:09:24 AM - zoidal submits the Level One problem for 93.30 points
9:14:57 AM - zoidal submits the Level Three problem for 483.41 points

Challenges
9:23:18 AM - DjinnKahn challenges ambrose on the Level Two problem successfully