TopCoder problem "HanoiDistance" used in TCCC05 Round 4 (Division I Level Three)



Problem Statement

    

In the famous Towers of Hanoi puzzle, you have three pegs, labeled A, B, and C, and n discs, of sizes 1 through n, inclusive. The discs are initially stacked on peg A in order of size, with the smallest disc on top. The goal is move the entire stack from peg A to peg C, under the constraints that you can only move one disc at a time and you can never move a larger disc onto a smaller disc. In each move, you remove the top disc from one of the three pegs and place it on top of the discs on another peg. In some cases, you move a disc to an empty peg, in which case the disc goes on the bottom of the peg.

There is a unique sequence of moves that solves the Towers of Hanoi puzzle in the minimum number of moves. There are a total of 2n configurations of discs that are encountered during the course of this solution, counting the initial configuration. Call each of these configurations valid and all other configurations invalid.

Your little sister dropped your Towers of Hanoi puzzle and put the discs back on random pegs. She remembered to always put smaller discs on top of larger discs, but did not necessarily make a valid configuration. You would be embarrassed if your friends saw your puzzle in an invalid configuration, so you want to move the discs back into a valid configuration. Naturally, you want to do so in the minimum number of moves. As usual, you can only move one disc at a time and you can never place a larger disc on top of a smaller disc.

You will be given the number of discs, n, and three int[]'s, pegA, pegB, and pegC, representing the order of the discs on each of the pegs, with the top disc on each peg at the front of the int[] and the bottom disc at the back. Return the minimum number of moves required to reach a valid configuration.

 

Definition

    
Class:HanoiDistance
Method:distance
Parameters:int, int[], int[], int[]
Returns:long
Method signature:long distance(int n, int[] pegA, int[] pegB, int[] pegC)
(be sure your method is public)
    
 

Constraints

-n is between 1 and 50, inclusive.
-pegA contains between 0 and n elements, inclusive.
-pegB contains between 0 and n elements, inclusive.
-pegC contains between 0 and n elements, inclusive.
-Each element of pegA is between 1 and n, inclusive.
-Each element of pegB is between 1 and n, inclusive.
-Each element of pegC is between 1 and n, inclusive.
-Each peg is sorted in increasing order.
-Each integer between 1 and n, inclusive, must appear on some peg.
-No element of pegA, pegB, or pegC may appear on more than one peg or more than once on the same peg.
 

Examples

0)
    
4
{ 1,2,3,4 }
{ }
{ }
Returns: 0
This configuration is already valid, so no moves are necessary.
1)
    
4
{ }
{ 1,2,3,4 }
{ }
Returns: 15
The whole stack should be on peg A or peg C, not peg B. It takes 15 moves to transfer the entire stack to either of the other pegs.
2)
    
50
{ 1,5,10,20,40,45,50}
{ 2,4,8,16,32,48}
{ 3,6,7,9,11,12,13,14,15,17,18,19,
  21,22,23,24,25,26,27,28,29,30,
  31,33,34,35,36,37,38,39,41,42,
  43,44,46,47,49 }
Returns: 405717644182423

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3522

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6531&pm=3522

Writer:

vorthys

Testers:

PabloGilberto , lbackstrom , Yarin

Problem categories:

Recursion