Match Editorial

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

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;

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.

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,

    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;

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)

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)