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 offbyone 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 sixthplace finish, he still advances to defend his title next month in Santa Clara. The ProblemsMusicLicensesUsed as: Division One  Level One:
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. TriptychUsed as: Division One  Level Two:
At first this feels like a shortestpath problem, but it's really a kind of minimalspanningtree problem. You need to find the lowestcost 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 lowestcost tree must have the form shown to the right, 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 AllPairs ShortestPath 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 "offtheshelf" algorithm around for programming challenges.) HanoiDistance Used as: Division One  Level Three:
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(n1,fromPeg,auxPeg,toPeg) move disc n from fromPeg to toPeg moveTower(n1,auxPeg,toPeg,fromPeg)A simple inductive proof shows that it takes 2^{n}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(n1,fromPeg,auxPeg,toPeg) if p == toPeg then return minMoves(n1,auxPeg,toPeg,fromPeg)  otherwise p == auxPeg count1 = minMovesToBuildTower(n1,fromPeg) count2 = minMovesToBuildTower(n1,toPeg) return min(count1,count2) + 2^(n1) 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(n1,toPeg) other = 3toPegp  assumes pegs are numbered 0,1,2 return buildTower(n1,other) + 2^(n1)See krijgertje's solution for a nice implementation of this approach. 
