Friday, April 4, 2002

Problem Set Analysis & Opinion

Semifinal rounds 1-3 were full of dramatic endings. In each match, it wasn't clear till the very end who would come away with a final's spot. Round 4 proved quite the opposite, with dgarthur defeating his opponents by a large margin. While the other coders struggled with the medium, dgarthur swept through the medium and hard attaining a score of 1233.47. DjinnKahn, the only other competitor to submit more than the easy, had both the hard and easy finished going into the challenge phase. DjinnKahn's hard ended up failing systests. Stunned by the ease with which dgarthur destroyed this set of problems, onlookers began to realize how exciting the final round will be. "The finals are stacked" said one spectator, eagerly awaiting tomorrow's main event.

Value	275
Submission Rate	4 / 4 (100.00%)
Success Rate	4 / 4 (100.00%)
High Score	DjinnKahn for 248.25 points

Finding the longest path in a directed graph is a difficult problem to solve. Luckily, the constraints ensured that the given graph would be acyclic, thus allowing for a simple solution. We will assign to each vertex, a cost that represents the longest path that can begin at that vertex. With a DFS (depth first search) we pass over all the vertices determining each ones' cost. At first, we can only determine the cost of the vertices whose outdegree (number of edges leaving) are 0 assigning each a cost of 0. Using those as our "base cases" we can build the costs for the rest of the vertices out of them using the following recursive definition: cost of vertex v = Max[ cost of each vertex reachable in one step from v + cost of connecting edge]. The return value is the maximum cost of any vertex in the graph. This algorithm could be described as memoization on a graph. An alternative dynamic programming approach would be to topologically sort the vertices, and then build each cost bottom up.

Value	550
Submission Rate	1 / 4 (25.00%)
Success Rate	1 / 1 (100.00%)
High Score	dgarthur for 326.61 points

Reference implementation: brett1479 in practice room
The process described in the problem allows us to take a plaintext string and a key, and make a cyphertext string. Reverse engineering this process, we can use the plaintext string and the cyphertext string to learn more about the key. The first thing to write, is a function that takes plaintext, cyphertext, and a guess at the key and will produce a more updated guess. To update our guess at the key, we go through the following process iterating through each character of the given strings. To aid in this process, we maintain a list representing where the initial key characters have moved to. That list begins as (0,1,2,3,...,26), whereas the initial key guess begins as "----...--".

1. If the current character in the cyphertext is i then that will determine the position in the key to examine
2. If the current character in the plaintext is j then we know that is the character that must be found in the key
3. We assign j to the key at the location determined by position i in our list
4. We remove the number at position i from our list, and add it to the front

Value	950
Submission Rate	2 / 4 (50.00%)
Success Rate	1 / 2 (50.00%)
High Score	dgarthur for 623.78 points

Reference implementation: brett1479 in practice room
The trick to this problem is realizing which order to process the inputs in. By using the breadth first traversal we know how each row should look, if we read them left to right. By using the in order traveral we can determine how wide each row is, and whose child each node is. The algorithm will iterate through the breadth first traversal elements 1 row at a time. The first row is clearly size 1. The size of future rows will be determined by their predecessors (higher rows). Assume v is the value of the current element we are observing in the breadth first traversal. First we determine iPos, the location of v in the in order traversal. Secondly, we see if we have already used the elements to the left and right of iPos in the in order traversal. If there are unused elements to the left we know v will have a left child. The same goes for the right side. We also know that when we process v's left child in the next row, it must lie to the left of iPos, and the same for v's right child (if they exist). This information can be used to figure out the characteristics of the next row by keeping track of the children discovered. Continuing this process till the tree is formed, or an error occurs produces our result.