Connection Status:
Competition Arena > DiverseFlowers

DiverseFlowers

TCO19 Semifinal 2 · 2019-11-14 · by Errichto

TCO19 Semifinal 2 · 2019-11-14 · by Errichto · Greedy, Search
Class Name: DiverseFlowers
Return Type: String[]
Method Name: solve
Arg Types: (string, int)
Problem Statement

Problem Statement

There are N flowers in a garden. Each flower has two properties: size (big or small) and color (red, green or blue). We will mark the type of a flower with one of six letters: R, G, B, r, g, b. For example, 'g' denotes a small green flower and 'B' denotes a big blue flower.

You will pick some flowers from the garden and arrange them into flower bouquets, each containing exactly K flowers. A bouquet must contain at least one flower of each color. A bouquet must also contain at least one flower of each size. And obviously, each individual flower can only be used in at most one bouquet.

Can you maximize the number of created bouquets?

You are given a String S with N characters that describe types of flowers in the garden. Return a String[] where each element represents one bouquet as a String with exactly K characters. If multiple solutions maximize the number of bouquets, return any of them. The order of bouquets doesn't matter, and neither does the order of flowers in a bouquet.

Constraints

  • S will contain exactly N characters.
  • N will be between 3 and 5000, inclusive.
  • K will be between 3 and N, inclusive.
  • Each character in S will be one of six: R, G, B, r, g, b.
Examples
0)
"BBgbr"
3
Returns: {"Bgr" }

The only possible bouquet is "Bgr" (big blue, small green, small red) or any other permutation of these three characters. Note that chosen flowers don't have to be consecutive in the given String S.

1)
"BBgbrGBBB"
3
Returns: {"rGB" }

Even though we have many more flowers in the garden this time, we still can create at most one bouquet.

2)
"RGBrgb"
4
Returns: {"RBrg" }

Each bouquet must consist of 4 flowers. We can create only one bouquet, for example "RBrg" or "bRGB".

3)
"RGBrgbRGBrgbRGBrgbRG"
5
Returns: {"RGBrg", "bRGBr", "gbRGB", "rgbRG" }
4)
"rrrrrbbbbbbgR"
4
Returns: {"Rrbg" }
5)
"gbgBgBgBbGGGBGGgbGBbGgGBBBBGGBGBbgBGBbbgGBBG"
3
Returns: { }

No bouquet will contain a red flower because there are no red flowers in the garden.

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

Coding Area

Language: C++17 · define a public class DiverseFlowers with a public method vector<string> solve(string S, int K) · 193 test cases · 2 s / 256 MB per case

Submitting as anonymous