SplitAndMergeGame
SRM 307 · 2006-06-14 · by Mike Mirzayanov
SRM 307 · 2006-06-14 · by Mike Mirzayanov · Search
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.
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)
{3,1,4,20,24,16,20}
{5,15,21,14,16,12,2,3}
Returns: 5
92)
{2}
{2,1}
Returns: -1
A solution doesn't exist.
Submissions are judged against all 118 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SplitAndMergeGame with a public method int minMoves(vector<int> startState, vector<int> finishState) · 118 test cases · 2 s / 256 MB per case