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

Semifinal Room 4 Problem Analysis & Opinion

Friday, November 22, 2002

Traffic
Used as: Level 1

#### 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.

TopPilot
Used as: Level 2

#### 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.

DNAsynth
Used as: Level 3

#### 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.

By lbackstrom
TopCoder Member
Author Profile

Semifinal Room 4 Chrono Logs

CODING PHASE
6:00:01 PM - ZorbaTHut opens the Level One problem
6:00:03 PM - jms137 opens the Level One problem
6:00:03 PM - DjinnKahn opens the Level One problem
6:00:35 PM - John Dethridge opens the Level One problem
6:06:15 PM - ZorbaTHut submits the Level One problem for 190.94 points (final submission)
6:06:21 PM - ZorbaTHut opens the Level Two problem
6:08:02 PM - John Dethridge submits the Level One problem for 187.47 points (final submission)
6:08:21 PM - John Dethridge opens the Level Three problem
6:12:42 PM - ZorbaTHut submits the Level Two problem for 381.24 points (final submission)
6:12:48 PM - ZorbaTHut opens the Level Three problem
6:20:29 PM - jms137 submits the Level One problem for 140.35 points (final submission)
6:20:38 PM - jms137 opens the Level Two problem
6:21:18 PM - John Dethridge opens the Level Two problem
6:25:15 PM - DjinnKahn submits the Level One problem for 125.79 points (final submission)
6:25:20 PM - DjinnKahn opens the Level Two problem
6:34:05 PM - DjinnKahn submits the Level Two problem for 366.41 points (final submission)
6:34:19 PM - DjinnKahn opens the Level Three problem
6:36:54 PM - John Dethridge submits the Level Two problem for 315.46 points (final submission)
6:44:44 PM - jms137 submits the Level Two problem for 257.74 points (final submission)
6:44:52 PM - jms137 opens the Level Three problem
7:14:50 PM - John Dethridge submits the Level Three problem for 416.94 points (final submission)

CHALLENGE PHASE
7:25:36 PM - jms137 challenges John Dethridge on the Level Two problem UNsuccessfully