TopCoder problem "SplitAndMergeGame" used in SRM 307 (Division I Level Three)



Problem Statement

    Split-and-merge is a one player game. The player starts out with several piles of coins. With each move, he can either merge two of the piles into a single pile, or split a single pile into two new non-empty piles. You are given a int[] startState, containing the starting configuration of the coins, and a int[] finishState, containing the target configuration. Each element of the int[]s represents the number of coins in a pile. The order of the elements do not matter. For example, {1, 2, 3} and {2, 1, 3} represent the same set of piles. Return the minimal number of moves necessary to reach the finishState from the startState. If a solution doesn't exist then return -1.
 

Definition

    
Class:SplitAndMergeGame
Method:minMoves
Parameters:int[], int[]
Returns:int
Method signature:int minMoves(int[] startState, int[] finishState)
(be sure your method is public)
    
 

Constraints

-startState will contain between 1 and 10 elements, inclusive.
-finishState will contain between 1 and 10 elements, inclusive.
-Each element of startState will be between 1 and 50, inclusive.
-Each element of finishState will be between 1 and 50, inclusive.
 

Examples

0)
    
{1, 2}
{3}
Returns: 1
Merge the two piles to form a single pile of 3 coins.
1)
    
{4, 2}
{2, 2, 2}
Returns: 1
Split the pile of 4 coins into two piles of 2 coins.
2)
    
{1, 2, 3, 4, 5, 6}
{7, 7, 7}
Returns: 3
3)
    
{3, 4}
{1, 6}
Returns: 2
One way to do this is to split the pile of 3 coins into a pile of 2 coins and a pile with 1 coin. Then, merge the pile of 2 coins with the pile of 4 coins to form a pile of 6 coins.
4)
    
{2}
{2,1}
Returns: -1
A solution doesn't exist.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9987&pm=6449

Writer:

Mike Mirzayanov

Testers:

PabloGilberto , brett1479 , Olexiy , marian

Problem categories:

Search