Connection Status:
Competition Arena > LittleElephantAndRGB

LittleElephantAndRGB

SRM 595 · 2013-06-25 · by Witaliy

SRM 595 · 2013-06-25 · by Witaliy · Brute Force, Dynamic Programming
Class Name: LittleElephantAndRGB
Return Type: long
Method Name: getNumber
Arg Types: (vector<string>, int)
Problem Statement

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).

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
0)
{"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".

1)
{"GG", "GG"}
3
Returns: 9

There are 3 valid quadruples such that T="GGGG" and 6 quadruples such that T="GGG".

2)
{"GRBGRBBRG"}
2
Returns: 11

One of the valid quadruples is (0,0,3,5). This quadruple corresponds to the nice string T="GGRB".

3)
{"RRBRBBRRR", "R", "B"}
1
Returns: 0
4)
{"GRGGGRBRGG", "GGGGGGGG", "BRGRBRB"}
4
Returns: 12430

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

Coding Area

Language: C++17 · define a public class LittleElephantAndRGB with a public method long long getNumber(vector<string> list, int minGreen) · 58 test cases · 2 s / 256 MB per case

Submitting as anonymous