Match Editorial

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

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.

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(roadFrom(x,y,x+dx[dir],y+dy[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]);