ColorfulParentheses | Topcoder Archive

Problem Statement

Note: This problem has a non-standard time limit of 1 second.

You are given a int[] 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:

S is a correct parentheses sequence of length n.
For each i, j: if color[i] = color[j] then S[i] = S[j].

Return the number of such strings.

Definition

Class:: ColorfulParentheses
Method:: count
Parameters:: int[]
Returns:: long
Method signature:: long count(int[] color)
(be sure your method is public)

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,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 "((()))".
```
{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.
```
{0,1,0,1,0,1}
```
```
Returns: 1
```
The only one is: "()()()".
```
{0,1,2,3,4,5,6,7,8,9,10,0}
```
```
Returns: 0
```
```
{0,1,3,3,4,5,6,7,1,9,10,3}
```
```
Returns: 7
```

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

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.