LittleElephantAndRGB | Topcoder Archive

Problem Statement

Little Elephant from the Zoo of Lviv likes strings that consist of characters 'R', 'G' and 'B'. You are given a String[] list. Concatenate all elements of list to get the string S of length N. The characters in S are numbered from 0 to N-1, inclusive.

You are also given int minGreen. Little Elephant thinks that string is nice if and only if it contains a substring of at least minGreen consecutive characters 'G'. For example, if minGreen = 2, then strings "GG", "GGRGBB" and "RRRGRBGGG" are nice, but "G", "GRG", "BBRRGRGB" are not.

Little Elephant wants to know the number of quadruples of integers (a,b,c,d) such that:

Each of a, b, c, d is between 0 and N-1, inclusive.
a <= b and c <= d. (Both a..b and c..d are valid ranges of values.)
b < c. (The entire range a..b lies before the range c..d.)
The string T = S[a..b] + S[c..d] is nice.

Compute and return the number of such quadruples (a,b,c,d).

Definition

Class:: LittleElephantAndRGB
Method:: getNumber
Parameters:: String[], int
Returns:: long
Method signature:: long getNumber(String[] list, int minGreen)
(be sure your method is public)

Constraints

list will contain between 1 and 50 elements, inclusive.
Each element of list will contain between 1 and 50 characters, inclusive.
Each element of list will consist only of characters 'R', 'G' and 'B'.
minGreen will be between 1 and 2500, inclusive.

Examples

```
{"GRG"}
```
```
2
```
```
Returns: 1
```
The only valid quadruple is (0,0,2,2). For this quadruple we have S[a..b]="G" and S[c..d]="G", thus T = "GG".
```
{"GG", "GG"}
```
```
3
```
```
Returns: 9
```
There are 3 valid quadruples such that T="GGGG" and 6 quadruples such that T="GGG".
```
{"GRBGRBBRG"}
```
```
2
```
```
Returns: 11
```
One of the valid quadruples is (0,0,3,5). This quadruple corresponds to the nice string T="GGRB".
```
{"RRBRBBRRR", "R", "B"}
```
```
1
```
```
Returns: 0
```

{"GRGGGRBRGG", "GGGGGGGG", "BRGRBRB"}

Returns: 12430

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.