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.


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


-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.


{1, 2}
Returns: 1
Merge the two piles to form a single pile of 3 coins.
{4, 2}
{2, 2, 2}
Returns: 1
Split the pile of 4 coins into two piles of 2 coins.
{1, 2, 3, 4, 5, 6}
{7, 7, 7}
Returns: 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.
Returns: -1
A solution doesn't exist.

Problem url:

Problem stats url:


Mike Mirzayanov


PabloGilberto , brett1479 , Olexiy , marian

Problem categories: