JOIN
 Match Editorial
2005 TopCoder Collegiate Challenge
Online Round 4

February 2, 2005

Summary

You probably wouldn't be surprised if I told you that Poland took first and second place in Round 4 of the TopCoder Collegiate Challenge, but you might be surprised if I told you that neither coder was named tomek. Eryx dominated from start to finish, which for him, occurred at the 35 minute mark. He was so fast on the Medium and Hard that even losing his Easy to a challenge on an off-by-one bug could not drop him out of first place. Fellow countryman cyfra took second by less than five points over Germany's AdrianKuegel. But don't cry for tomek. With a sixth-place finish, he still advances to defend his title next month in Santa Clara.

# The Problems

Used as: Division One - Level One:
 Value 250 Submission Rate 46 / 49 (93.88%) Success Rate 33 / 46 (71.74%) High Score dgarthur for 242.33 points (5 mins 5 secs) Average Score 200.15 (for 33 correct submissions)

The most common approach was to loop over all prefixes and check if each one was legal:

```    for (int i = 0; i < log.length; i++)
if (the prefix log[0..i] is illegal)
return i;
return -1;
```
As a minor optimization, you could start the loop at 7 instead of 0, because no prefix of length 6 or less can possibly be illegal.

One way to check if a prefix is illegal is to look for some index i such that three characters different from the character at i all occur both before and after i. For example, the prefix "ABCDABC" is illegal because 'A', 'B', and 'C' all occur both before and after the 'D'. dgarthur took a minor variation on this approach.

Another way to check if a prefix is illegal is to try to determine which computers need licenses when. Whenever a new computer needs a license, the license should be transferred from a computer that no longer needs it (because the computer is not used again within the current prefix). If no such computer exists—that is, if all three computers with licenses still need them—then the current prefix is illegal.

All solutions that consider each prefix separately take quadratic time or worse, but a linear solution is also possible using a greedy algorithm. Every time you need to transfer a license, transfer it from the computer whose next use is farthest in the future (if there is no next use, count it as infinitely far in the future). When you reach a computer that has already owned and lost a license, return the current index. Finding the next use of each computer requires a little preprocessing, but it is easy to build the required table in linear time.

Triptych
Used as: Division One - Level Two:
 Value 500 Submission Rate 40 / 49 (81.63%) Success Rate 26 / 40 (65.00%) High Score Eryx for 445.57 points (10 mins 11 secs) Average Score 305.68 (for 26 correct submissions)

At first this feels like a shortest-path problem, but it's really a kind of minimal-spanning-tree problem. You need to find the lowest-cost tree that includes the origin and all three destinations. Because the trip must end back at the origin, every edge in the tree will end up being crossed exactly twice (i.e., every return ticket will eventually be used), so the possibility raised in the problem statement of not using a return ticket was a red herring.

The key is to realize that the lowest-cost tree must have the form shown to the right,

where the green node is the origin and the three red nodes are the destinations. The lines in this picture represent paths, not necessarily direct flights. There are, of course, other shapes that the optimal tree might have, but all such variations are degenerate forms of the tree shown here, in which two or more of the nodes have been merged. For example, you might end up with a single intermediate point by merging both of the blue nodes, or you might end up with a single path by merging each of the blue nodes with one of its neighbors. To find the lowest-cost tree, we simply try every possible pair of intermediate points. For each pair, we try three different arrangments of the destination cities, where each of the three cities might be the red node on the left of the diagram (and the other two are the red nodes on the right of the diagram). In code, this can be written as
```    best = INFINITY;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
best = min(C[0][i]+C[d0][i]+C[i][j]+C[j][d1]+C[j][d2],
C[0][i]+C[d1][i]+C[i][j]+C[j][d0]+C[j][d2],
C[0][i]+C[d2][i]+C[i][j]+C[j][d0]+C[j][d1]);
return (best==INFINITY) ? -1 : best;
```
In this code, C[x][y] represents the minimum cost to travel from city x to city y. It is easy to build the C table from the original cost data using Floyd's All-Pairs Shortest-Path algorithm. (If you don't know Floyd's algorithm, learn it. Other than your system sorting routine, it may very well be the single most useful "off-the-shelf" algorithm around for programming challenges.)

HanoiDistance
Used as: Division One - Level Three:
 Value 1000 Submission Rate 10 / 49 (20.41%) Success Rate 6 / 10 (60.00%) High Score Eryx for 805.30 points (14 mins 43 secs) Average Score 585.34 (for 6 correct submissions)

To solve this problem, you had to remember or reconstruct how to solve the original Towers of Hanoi problem. The following procedure moves a tower of n discs from one peg to another peg:

```   procedure moveTower(n,fromPeg,toPeg,auxPeg) is
if (n == 0) return

moveTower(n-1,fromPeg,auxPeg,toPeg)
move disc n from fromPeg to toPeg
moveTower(n-1,auxPeg,toPeg,fromPeg)
```
A simple inductive proof shows that it takes 2n-1 moves to move a tower of n discs.

The moveTower procedure basically tells us where each disc needs to be in a valid configuration. For example, the biggest disc needs to be on either peg A (the "from" peg) or peg C (the "to" peg). The possible locations of the next biggest disc depend on which peg the biggest disc is on. If the biggest disc is on peg A, then the next biggest disc can be on either peg A or peg B. On the other hand, if the biggest disc is on peg C, then the next biggest disc can be on either peg B or peg C.

Now, if the bottom disc is already on peg A or peg C, then we'll leave it in place. But if it's on peg B, then we need to move it to either peg A or peg C, whichever one requires fewer moves. Suppose we want to move it to peg A. Then we'll first have to move all the remaining discs to peg C. After we move the biggest disc from peg B to peg A, what do we do with the dics on peg C? It turns out that we need to move the entire tower to either peg A or peg B. (Recall that when the biggest disc is on peg A, the next biggest disc needs to be on either peg A or peg B.)

All this can be accomplished using the following two recursive functions, the first for finding the minimum cost to get to a valid configuration and the second for finding the minimum cost to build a tower on a given peg:

```   function minMoves(n,fromPeg,toPeg,auxPeg) is
if n == 0 then return 0

p = the peg that disc n is currently on
if p == fromPeg then return minMoves(n-1,fromPeg,auxPeg,toPeg)
if p == toPeg then return minMoves(n-1,auxPeg,toPeg,fromPeg)

-- otherwise p == auxPeg
count1 = minMovesToBuildTower(n-1,fromPeg)
count2 = minMovesToBuildTower(n-1,toPeg)
return min(count1,count2) + 2^(n-1)

function minMovesToBuildTower(n,toPeg) is
if n == 0 then return 0

p = the peg that disc n is currently on
if p == toPeg then return buildTower(n-1,toPeg)
other = 3-toPeg-p  -- assumes pegs are numbered 0,1,2
return buildTower(n-1,other) + 2^(n-1)
```
See krijgertje's solution for a nice implementation of this approach.

By vorthys
TopCoder Member