Friday, April 4, 2002
Problem Set Analysis & Opinion
Semifinal rounds 13 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.
Circuits
Used as: Division 1  Level 1:
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.
DecodeMoveToFront
Used as: Division 1  Level 2:
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 "...".
 If the current character in the cyphertext is i then that will determine the position in
the key to examine
 If the current character in the plaintext is j then we know that is the character that must
be found in the key
 We assign j to the key at the location determined by position i in our list
 We remove the number at position i from our list, and add it to the front
For example, lets say we have plaintext "A" and cyphertext "B". We assign "A" to the key at
position 1 and then perform the removal. The finished list is (1,0,2,3,...,26) and the updated
key guess is "A...". This process is repeated on each pair of corresponding inputs,
successively updating our guess at the key. In addition, if any conflicts occured, we can detect
them at step 3 above. The only special case to check for, is whether or not all keys elements
have been determined except 1. In this situation, we simply fill in the remaining '' with the
only unused letter.
TreeTraversals
Used as: Division 1  Level 3:
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.
By brett1479
TopCoder MemberAuthor Profile
