Connection Status:
Competition Arena > GirlsAndBoys

GirlsAndBoys

TCO10 Qual 1 · 2010-04-11 · by soul-net

TCO10 Qual 1 · 2010-04-11 · by soul-net · Greedy
Class Name: GirlsAndBoys
Return Type: int
Method Name: sortThem
Arg Types: (string)
Problem Statement

Problem Statement

There are N students standing in a single row, one next to the other, numbered 0 to N-1 from left to right. Your goal is to minimize the number of adjacent pairs where one student is a boy and the other is a girl. More precisely, you want to minimize the number of values i, 0 <= i < N-1, where student i and student i+1 are of different genders.

You are given the current arrangement as a String row, where the i-th character is 'G' if student i is a girl, and 'B' if student i is a boy. In a single move, you can choose two adjacent students and swap their positions. Return the minimum number of moves required to achieve your goal.

Constraints

  • row will contain between 1 and 50 characters, inclusive.
  • Each character in row will be 'G' or 'B'.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
"GGBBG"
Returns: 2

You can swap the rightmost girl with the two boys (one after the other) to get "GGGBB", with a minimum of only 1 pair of adjacent students of different gender.

1)
"BBBBGGGG"
Returns: 0

There is already a single pair of adjacent students of different gender, and there is no arrangement without such pairs at all, so the best solution is to swap nothing.

2)
"BGBGBGBGGGBBGBGBGG"
Returns: 33
3)
"B"
Returns: 0

With only one student, there is not much swapping to do.

4)
"G"
Returns: 0

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

Coding Area

Language: C++17 · define a public class GirlsAndBoys with a public method int sortThem(string row) · 77 test cases · 2 s / 256 MB per case

Submitting as anonymous