TopCoder Statistics - Problem Statement

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

{1, 2}

{3}

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.
{3,1,4,20,24,16,20}

{5,15,21,14,16,12,2,3}

Returns: 5
{22}

{22}

Returns: 0
{26}

{7,19}

Returns: 1
{35}

{14,11,10}

Returns: 2
{21}

{14,1,4,2}

Returns: 3
{5}

{1,1,1,1,1}

Returns: 4
{14}

{2,4,2,2,3,1}

Returns: 5
{18}

{3,5,2,5,1,1,1}

Returns: 6
{14}

{2,1,2,4,1,1,1,1,1}

Returns: 8
{18}

{6,1,3,2,1,1,1,1,1,1}

Returns: 9
{29,10}

{31,8}

Returns: 2
{4,39}

{36,1,6}

Returns: 3
{30,31}

{7,9,26,19}

Returns: 4
{39,31}

{23,19,5,15,8}

Returns: 3
{4,14}

{5,1,4,5,2,1}

Returns: 4
{13,15}

{21,2,1,1,1,1,1}

Returns: 7
{23,6,1,1,3,2,5,4}

{39,6}

Returns: 6
{3,21}

{4,8,2,5,1,1,1,1,1}

Returns: 7
{12,22}

{19,6,1,2,1,1,1,1,1,1}

Returns: 8
{6,3,32}

{38,3}

Returns: 1
{29,7,14}

{28,10,12}

Returns: 4
{16,39,21}

{36,13,18,9}

Returns: 5
{25,39,1}

{5,37,14,6,3}

Returns: 4
{29,14,36}

{13,30,18,6,5,7}

Returns: 5
{38,23,16}

{23,15,35,1,1,1,1}

Returns: 4
{25,6,23}

{29,12,1,4,3,1,2,2}

Returns: 7
{29,29,18}

{37,3,6,6,4,16,2,1,1}

Returns: 8
{38,30,30}

{9,31,12,3,28,7,5,1,1,1}

Returns: 7
{14,35,5,12}

{38,28}

Returns: 4
{37,39,19,3}

{31,42,25}

Returns: 3
{6,39,39,15}

{38,40,18,3}

Returns: 4
{11,38,30,3}

{2,14,32,26,8}

Returns: 5
{20,7,2,14}

{3,27,5,6,1,1}

Returns: 4
{25,22,37,22}

{21,11,22,14,13,23,2}

Returns: 5
{11,13,5,28}

{11,18,3,13,6,3,2,1}

Returns: 4
{20,14,24,40}

{4,25,23,5,3,28,5,1,4}

Returns: 7
{24,29,19,8}

{29,13,29,3,1,1,1,1,1,1}

Returns: 8
{28,23,25,6,10}

{23,27,42}

Returns: 4
{32,38,28,6,4}

{45,21,35,7}

Returns: 5
{19,30,36,20,33}

{39,36,36,25,2}

Returns: 4
{28,30,7,32,19}

{16,18,21,22,28,11}

Returns: 5
{32,6,10,39,12}

{3,25,17,5,34,4,11}

Returns: 6
{1,14,22,11,6}

{11,10,9,4,2,14,2,2}

Returns: 5
{28,6,29,17,35}

{9,25,15,30,11,21,2,1,1}

Returns: 8
{32,21,32,25,29}

{38,33,12,6,5,30,5,4,5,1}

Returns: 9
{18,6,7,40,23,11}

{41,28,32,4}

Returns: 6
{5,38,14,6,12,9}

{19,2,14,33,16}

Returns: 5
{14,38,26,17,6,26}

{11,28,4,42,27,15}

Returns: 6
{18,14,21,25,39,14}

{11,26,20,10,20,26,18}

Returns: 7
{27,22,1,37,25,22}

{39,7,5,7,9,16,39,12}

Returns: 8
{40,5,38,2,20,28}

{34,13,16,39,26,2,1,1,1}

Returns: 7
{9,13,9,13,6,37}

{25,37,10,8,1,2,1,1,1,1}

Returns: 8
{4,14,17,26,10,23,30}

{41,36,47}

Returns: 4
{39,6,4,3,25,37,31}

{32,22,23,46,22}

Returns: 6
{3,21,40,11,18,25,30}

{22,37,21,30,21,17}

Returns: 5
{12,22,19,23,4,1,20}

{6,19,22,22,14,5,13}

Returns: 4
{17,37,14,31,37,29,27}

{39,39,33,10,9,35,10,17}

Returns: 7
{3,29,22,36,27,27,38}

{17,7,34,25,6,25,13,41,14}

Returns: 8
{12,37,1,8,20,3,28}

{38,24,39,1,1,2,1,1,1,1}

Returns: 9
{25,6,23,29,12,8,14,28}

{39,34,23,22,27}

Returns: 5
{20,14,24,40,4,25,23,5}

{28,14,14,30,37,32}

Returns: 6
{24,29,19,8,29,13,29,9}

{4,20,37,36,30,21,12}

Returns: 7
{33,29,39,19,23,29,12,25}

{32,28,37,28,13,26,32,13}

Returns: 8
{20,21,6,25,12,27,30,40}

{27,25,7,22,40,37,3,19,1}

Returns: 7
{3,25,28,16,30,35,11,20}

{23,23,27,29,39,2,17,1,4,3}

Returns: 8
{32,6,10,39,12,2,24,16,4}

{40,43,35,27}

Returns: 7
{1,14,22,11,6,11,14,1,24}

{34,37,20,8,5}

Returns: 8
{28,6,29,17,35,9,25,15,30}

{45,12,20,35,40,42}

Returns: 7
{32,21,32,25,29,37,32,11,5}

{17,42,25,35,21,37,47}

Returns: 6
{1,21,4,36,14,13,14,35,33}

{26,36,19,19,16,18,17,20}

Returns: 7
{25,26,26,28,32,21,35,15,19}

{22,20,22,16,12,47,48,14,26}

Returns: 8
{11,17,33,34,21,19,13,22,25}

{19,23,9,36,15,6,39,17,4,27}

Returns: 7
{28,13,12,2,4,11,33,2,30,19}

{37,43,37,18,19}

Returns: 7
{14,5,19,16,33,17,11,16,36,26}

{27,25,43,40,33,25}

Returns: 6
{7,9,12,11,4,33,14,12,11,22}

{24,35,5,19,31,15,2,4}

Returns: 8
{16,10,32,23,30,10,4,36,31,30}

{25,29,30,23,13,24,41,29,8}

Returns: 9
{2,2,39,37,19,8,15,11,36,37}

{35,30,16,33,10,21,10,14,20,17}

Returns: 10
{4,15,40,32,13,15,50,46,18,11}

{27,33,19,23,12,39,34,35,20,2}

Returns: 10
{31,4,19,24,31,29,24,33,2,17}

{23,23,18,43,34,47,4,5,6,11}

Returns: 10
{8,2,35,11,47,32,41,12,4,28}

{7,41,15,29,45,19,37,10,3,14}

Returns: 8
{2,39,22,4,49,4,10,33,2,28}

{13,28,6,10,20,15,7,28,27,39}

Returns: 6
{8,31,13,4,17,35,9,46,7,15}

{48,9,44,15,14,24,21,8,1,1}

Returns: 6
{5,29,37,14,33,7,34,46,42,32}

{12,20,46,37,29,49,34,39,5,8}

Returns: 4
{21,25,31,42,34,31,33,37,40,33}

{49,28,38,45,28,47,36,8,12,36}

Returns: 12
{45,37,38,14,26,8,1,11,49,7}

{37,4,50,7,38,40,41,9,2,8}

Returns: 4
{13,9,31,45,33,9,18,31,44,46}

{39,39,48,37,35,8,41,17,5,10}

Returns: 12
{1}

{2}

Returns: -1
{1}

{1,1}

Returns: -1
{2}

{2,1}

Returns: -1

A solution doesn't exist.
{2,2}

{1,2}

Returns: -1
{1,2, 3}

{3,1, 1}

Returns: -1
{19,23,9,36,15,6,39,17,4,27}

{27,4,17,39,6,15,36,9,23,19}

Returns: 0
{23,23,27,29,39,2,17,1,4,3}

{23,40,27,29,39,2,1,4,3}

Returns: 1
{23,23,27,29,39,2,17,1,4,3}

{23,23,27,29,39,2,17,1,4,3}

Returns: 0
{23,23,27,29,39,2,17,1,4,3}

{23,23,27,29,39,3,17,1,4,3}

Returns: -1
{50,50,50,50,50,50,50,50,50,50}

{50,50,50,50,50,50,50,50,50,50}

Returns: 0
{42, 8, 18, 10, 11, 10, 49, 25, 39, 27 }

{18, 11, 31, 42, 12, 32, 26, 1, 19, 47 }

Returns: 8
{1, 2, 3, 4, 6, 20, 24, 25, 25, 26 }

{5, 10, 21, 24, 26, 50 }

Returns: 4
{15, 17 }

{3, 4, 10, 15 }

Returns: 2
{50, 40, 40, 40, 40, 40, 40, 40, 40, 40 }

{49, 49, 49, 49, 49, 49, 49, 49, 9, 9 }

Returns: 18
{1, 4, 5, 49 }

{3, 48, 6, 2 }

Returns: 4
{42, 35, 20, 29, 13, 6, 32, 12, 46, 28 }

{18, 1, 25, 9, 15, 46, 28, 42, 43, 36 }

Returns: 8
{50, 3, 7, 48, 50 }

{30, 20, 12, 46, 50 }

Returns: 4
{5, 11, 12, 13, 1, 1, 1, 11 }

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

Returns: 6
{1, 4, 2, 5, 1, 2, 48, 2, 8, 10 }

{30, 2, 10, 10, 10, 10, 11 }

Returns: 7
{11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }

{21, 22, 23, 24, 25, 6, 7, 8, 9, 10 }

Returns: 10
{50, 50, 50 }

{15, 15, 15, 16, 14, 13, 17, 15, 10, 20 }

Returns: 9
{1, 2, 3, 4, 5, 16, 17, 18, 19, 20 }

{6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }

Returns: 10
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

Returns: 0
{2, 2, 2, 4, 4, 50, 50, 8, 12, 2 }

{8, 1, 9, 26, 15, 11, 8, 6, 2, 50 }

Returns: 6
{25, 25, 22, 31, 24, 19, 22, 19, 13, 23 }

{23, 25, 23, 27, 28, 20, 19, 18, 14, 26 }

Returns: 8
{1, 2, 3, 4, 5, 6 }

{7, 7, 7 }

Returns: 3
{1, 12, 13, 4, 15, 6, 17, 8, 50, 50 }

{2, 5, 5, 5, 11, 17, 49, 49, 30, 3 }

Returns: 10
{5, 10, 15, 20, 25, 30, 35, 40, 45, 50 }

{6, 11, 16, 21, 26, 31, 36, 41, 46, 41 }

Returns: 16

Statistics

Problem Statement for "SplitAndMergeGame"

Problem Statement

Definition

Constraints

Examples