Connection Status:
Competition Arena > EllysPearls

EllysPearls

TCO19 Round 1B · 2019-04-15 · by espr1t

TCO19 Round 1B · 2019-04-15 · by espr1t · Dynamic Programming
Class Name: EllysPearls
Return Type: int
Method Name: getMin
Arg Types: (int, int, vector<int>)
Problem Statement

Problem Statement

Elly has a long narrow jewelry box. In the box she stores a row of N pearls. Each pearl has one of M different colors – white, pink, blue, etc. The girl wants to order the pearls by color – all white should be next to each other, all pink should be next to each other, and so on. The order of the colors in the final configuration doesn’t matter – e.g., Elly doesn't care if the white pearls will be before or after the pink ones.

Now Elly is wondering what is the minimal number of pearls she must move in order for them to be grouped by color? (Moving a pearl means taking it away from the row and then inserting it back at an arbitrary position - either between any two pearls or before or after all of them.)

You are given the ints N and M - the number of pearls and the number of colors, respectively. You are also given the int[] pearls - the color of each of the pearls in the initial configuration from left to right. Return one integer: the minimal number of pearls Elly should move.

Constraints

  • N will be between 1 and 50, inclusive.
  • M will be between 1 and 15, inclusive.
  • pearls will contain exactly N elements.
  • Each element of pearls will be between 1 and M, inclusive.
Examples
0)
11
4
{2, 4, 1, 1, 1, 3, 2, 1, 4, 2, 2}
Returns: 3

Elly can make the following sequence of moves: move the leftmost pearl (color 2) to the right end of the row move the rightmost of the two pearls of color 4 to the beginning of the row (i.e., immediately before the other pearl of color 4) move the isolated pearl of color 1 anywhere between (or immediately before or after) the group formed by the other pearls of color 1 This way she will have moved only three pearls. The final configuration of pearls will be {4, 4, 1, 1, 1, 1, 3, 2, 2, 2, 2}.

1)
5
1
{1, 1, 1, 1, 1}
Returns: 0

With only one color the answer is obviously zero.

2)
10
2
{2, 2, 2, 1, 2, 2, 2, 1, 1, 2}
Returns: 2

Pick the leftmost 1 and move it to the back, then pick the rightmost 2 and move it to the front.

3)
30
7
{5, 6, 2, 4, 7, 2, 2, 3, 3, 6, 1, 3, 6, 3, 7, 5, 1, 2, 3, 4, 6, 5, 6, 3, 2, 5, 3, 3, 5, 6}
Returns: 16
4)
1
1
{1}
Returns: 0

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

Coding Area

Language: C++17 · define a public class EllysPearls with a public method int getMin(int N, int M, vector<int> pearls) · 105 test cases · 2 s / 256 MB per case

Submitting as anonymous