Connection Status:
Competition Arena > BoxesArrangement

BoxesArrangement

SRM 351 · 2007-05-29 · by Andrew_Lazarev

SRM 351 · 2007-05-29 · by Andrew_Lazarev · Dynamic Programming
Class Name: BoxesArrangement
Return Type: int
Method Name: maxUntouched
Arg Types: (string)
Problem Statement

Problem Statement

Several boxes are placed in a row. Each box is one of three colors. We want to rearrange these boxes in a such way that no three consecutive boxes are of the same color. This process should affect the fewest boxes possible. More formally, we want to achieve the desired configuration by swapping pairs of boxes, and we want to maximize the number of boxes that are never moved.

You will be given a String boxes which describes the colors of the boxes. Colors are given as characters 'A', 'B' and 'C' respectively. Rearrange the boxes as described above and return the maximum possible number of boxes that are never moved. Return -1 if it is not possible to achieve the desired configuration.

Constraints

  • boxes will contain between 1 and 50 characters, inclusive.
  • boxes will consist of characters 'A', 'B' and 'C' only.
Examples
0)
"AAABBBCCC"
Returns: 6

The boxes could be rearranged into "ABABCBCAC".

1)
"AAAAAAAACBB"
Returns: 7

The best rearangement is "AABAABAACAA".

2)
"CCCCCB"
Returns: -1
3)
"BAACAABAACAAA"
Returns: 5
4)
"BCBBBACBBBBBBACCBB"
Returns: 12

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

Coding Area

Language: C++17 · define a public class BoxesArrangement with a public method int maxUntouched(string boxes) · 117 test cases · 2 s / 256 MB per case

Submitting as anonymous