ColorfulParentheses
SRM 709 · 2016-12-07 · by cgy4ever
SRM 709 · 2016-12-07 · by cgy4ever · Search
Problem Statement
Problem Statement
Note: This problem has a non-standard time limit of 1 second.
You are given aint[] color with n elements.
Different values represent different colors.
We are interested in correct parentheses sequences of length n. Additionally, the parentheses will have colors. For each i, the color of the i-th parenthesis (0-based index) will be color[i]. Parentheses that share the same color must have the same type.
Formally, we are looking for a string S with the following properties:
You are given a
We are interested in correct parentheses sequences of length n. Additionally, the parentheses will have colors. For each i, the color of the i-th parenthesis (0-based index) will be color[i]. Parentheses that share the same color must have the same type.
Formally, we are looking for a string S with the following properties:
- S is a correct parentheses sequence of length n.
- For each i, j: if color[i] = color[j] then S[i] = S[j].
Constraints
- color will contain between 2 and 50 elements, inclusive.
- The length of color will be even.
- Each element in color will be between 0 and (|color|-1), inclusive.
Examples
0)
{0,0,1,2,3,4}
Returns: 3
We want a correct parentheses sequence that has length 6 and the first two characters are the same. There are exactly 3 such sequences: "(())()", "(()())", and "((()))".
1)
{0,1,2,3,4,5}
Returns: 5
This time all colors are different, which means there are no constraints. The correct return value is equal to the number of correct parentheses sequences of length 6.
2)
{0,1,0,1,0,1}
Returns: 1
The only one is: "()()()".
3)
{0,1,2,3,4,5,6,7,8,9,10,0}
Returns: 0
4)
{0,1,3,3,4,5,6,7,1,9,10,3}
Returns: 7
5)
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35}
Returns: 477638700
Watch out for integer overflow.
Submissions are judged against all 122 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ColorfulParentheses with a public method long long count(vector<int> color) · 122 test cases · 2 s / 256 MB per case