Connection Status:
Competition Arena > MarblesRegroupingHard

MarblesRegroupingHard

SRM 387 · 2008-01-09 · by Relja

SRM 387 · 2008-01-09 · by Relja · Dynamic Programming
Class Name: MarblesRegroupingHard
Return Type: int
Method Name: minMoves
Arg Types: (vector<string>)
Problem Statement

Problem Statement

John is (as you probably know) a marble collector. He keeps his marbles in boxes. He also likes to keep things in order - in each box there are only marbles of the same color (some boxes may be empty).

One day, his younger brother was playing with the marbles. After he was done, he put all the marbles back in boxes, but he did it randomly, so certain boxes might now contain marbles of different colors. You are given a String[] boxes, where each element is a space separated list of integers and the j-th integer of the i-th element is the number of marbles of color j in the i-th box. John wants him to regroup the marbles so that each box is either empty or contains only marbles of the same color, and all marbles of the same color are in the same box. Return the minimal number of moves necessary to do this, where each move consists of taking exactly one marble from any box and putting it into another.

Constraints

  • boxes will contain between 1 and 50 elements, inclusive.
  • Each element of boxes will contain only digits ('0'-'9') and spaces (' ').
  • Each element of boxes will be a single space separated list of integers without leading or trailing spaces.
  • Each integer in boxes will not contain leading zeros and will be between 0 and 99, inclusive.
  • Each element of boxes will contain between 1 and 14 integers, inclusive (that's the number of different colors used).
  • All elements of boxes will contain the same number of integers.
  • The number of different colors used will be less then or equal to N, where N is the number of elements in boxes.
Examples
0)
{"0"}
Returns: 0
1)
{"77 97","8 0"}
Returns: 77

Move all marbles of color 0 to box 1.

2)
{"6 97 7","73 45 0","67 45 63"}
Returns: 170

In the end, all marbles of color 0 are in box 1, all marbles of color 1 are in box 0, and all marbles of color 2 are in box 2.

3)
{"88 55 47 92","0 0 59 0","69 0 61 75","2 94 4 0"}
Returns: 330
4)
{"97 94 0 99","1 72 46 45","0 10 47 75","0 92 76 20","2 25 98 22"}
Returns: 559

Submissions are judged against all 55 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MarblesRegroupingHard with a public method int minMoves(vector<string> boxes) · 55 test cases · 2 s / 256 MB per case

Submitting as anonymous