JOIN
 Match Editorial
2004 TopCoder Open
Qualification Problem Set 5

September 7-8, 2004

Summary

Jongman was one of two yellow coders to win his problem set, and he did so by over 70 points, beating second place ZorbaTHut, and third place kalinov, not to mention every one's favorite problem writer, Yarin.

# The Problems

TheThe
Used as: Division One - Level One:
 Value 250 Submission Rate 197 / 211 (93.36%) Success Rate 168 / 197 (85.28%) High Score gepa for 248.02 points (2 mins 2 secs) Average Score 218.90 (for 168 correct submissions)

A good string tokenizer was all you needed in this problem. Simply loop through all of the lines, tokenizing each one into words. Then, look at all pairs of adjacent lines, and see if the first token of one line matches the last token of the preceding line.

FewestTurns
Used as: Division One - Level Three:
 Value 1000 Submission Rate 81 / 211 (38.39%) Success Rate 37 / 81 (45.68%) High Score JongMan for 796.40 points (12 mins 9 secs) Average Score 481.02 (for 37 correct submissions)

This is a pretty standard search problem. The most efficient way to do it is with a breadth first search, but a simpler depth first search can be made to work as long as you are careful about not blowing the stack. Most coders went for a breadth first approach, so I'll discuss that one. The basic idea here is like any other breadth first search problem, you have a first in, first out queue. Each element in the queue represents a location and direction in the map. You also have a table which tells how many turns it has taken to get to a particular location in a particular direction. After you take a location and direction off the queue, you look at all the positions and directions that can be reached from there. For each one, you also look up how many turns it has taken in the table. If the value in the table doesn't exist, or is greater than the number of turns required to get there from the location we took off the queue, we insert the location and direction into the queue, and update the table. At the end, we return the minimum value in the table for the final position and some direction.

```    queue q;
table t;
initialize t[a][b][c] = INF, for all a,b,c;
//insert starting location and all four directions
q.insert(startx,starty,0);
q.insert(startx,starty,1);
q.insert(startx,starty,2);
q.insert(startx,starty,3);
t[startx][starty][0] = 0;
t[startx][starty][1] = 0;
t[startx][starty][2] = 0;
t[startx][starty][3] = 0;
while(!q.isEmpty()){
x = q.first().x;
y = q.first().y;
dir = q.first().dir;
q.removeFirst();
turns = table[x][y][dir];
if(t[x+dx[dir]][y+dy[dir]][dir] > turns){
t[x+dx[dir]][y+dy[dir]][dir] = turns;
q.insert(x+dx[dir],y+dy[dir],dir);
}
}
if(t[x][y][(dir+1)%4] > turns+1){
t[x][y][(dir+1)%4] = turns+1;
q.insert(x,y,(dir+1)%4);
}
if(t[x][y][(dir+3)%4] > turns+1){
t[x][y][(dir+3)%4] = turns+1;
q.insert(x,y,(dir+3)%4);
}
}
return min(t[finalx][finaly][0],t[finalx][finaly][1],
t[finalx][finaly][2],t[finalx][finaly][3]);
```
By lbackstrom
TopCoder Member