Friday, November 22, 2002

Implementation

This problem was a pretty straightforward simulation. You basically just have to follow the instructions and go from one stop light to the next. It takes you 150/speed to get from one light to the next, though you have to use double because of the possibilty of the speed being 20. Then, once you get to the light, you just have to check if it is red or green, and wait for it to turn green if it is red.

Implementation

Undoubtedly the easiest medium problem of the match, this problem simply involved running floyds to find the transitive closure. Since the indexes of all the airports are between 0 and 50, inclusive, it is simple to just build an adjacency matrix. Once you have this, you simply run floyds, and count the number of connected vertices. DjinnKahn's solution was probably the cleanest, and he got the most points on this one.

Implementation

To make up for the easy medium, the hardest hard problem was used in this round. You are given a list of rules of the form <SEQ1>:<SEQ2> indicating that strings starting with <SEQ2> can be appended to strings ending with <SEQ1>. You start with an unlimited supply of all of the strings that are <SEQ1> or <SEQ2> in one of these rules. Additionally, sequences are the same forwards and backwards, but this is easily handled by including the reverse of all the rules.

Since the length of <SEQ1> and <SEQ2> are limited to 4, it appears at first glance that we can simply keep track of the longest string with a given ending and then keep trying to add new strings from <SEQ1> or <SEQ2>. However, a close examination of example 4 shows that this will fail. However, this approach is on the right track. In order to get example 4 correct, then we have to do some preproccessing. So, after reversing the rules, we then take each of the rules, and remove the semicolon. It is obvious that all of these strings can be formed. Then, for each of these strings, we go through all of the rules, and if the string we formed starts with <SEQ2> in one of the rules then we add a new rule, <SEQ1>:<new string>, and its reverse.

Once we have these extra rules, we can just do some simple dynamic programming to keep track of the longest strings with each of 4 character ending. If the length every get over 404, then we can form an infinite loop.