ParenthesesAndPermutation | Topcoder Archive

Problem Statement

Correct parentheses sequences can be defined recursively as follows:

The empty string "" is a correct sequence.
If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence.
If "X" is a correct sequence, then "(X)" is a correct sequence.
Each correct parentheses sequence can be derived using the above rules.

Examples of correct parentheses sequences include "", "()", "()()()", "(()())", and "(((())))".

You are given a int[] p with n elements. The elements of p are a permutation of the numbers 0 to n-1. Find strings s and t with the following properties:

Both s and t are correct parentheses sequences.
Each of them has exactly n characters.
For each valid i, s[i] = t[ p[i] ].

Return one possible string s. If there are multiple possibilities, you may return any of them. If there is no solution, return "Impossible" instead.

Definition

Class:: ParenthesesAndPermutation
Method:: getSequence
Parameters:: int[]
Returns:: String
Method signature:: String getSequence(int[] p)
(be sure your method is public)

Constraints

p will contain between 2 and 50 elements, inclusive.
The length of p will be even.
p will be a permutation of 0 to (|p|-1).

Examples

```
{2,0,3,1}
```
```
Returns: "(())"
```
We are looking for two correct parentheses sequences such that s[0]=t[2], s[1]=t[0], s[2]=t[3], and s[3]=t[1]. There are two parentheses sequences of length 4: "(())" and "()()". We can now argue as follows: Can s be "(())"? We can deduce that t must be "()()" which is a correct parentheses sequence, so this is a valid solution. Can s be "()()"? We can deduce that t must be "))((" which is not a correct parentheses sequence, so this is not a valid solution. Therefore, the only valid solution is s = "(())".
```
{1,0}
```
```
Returns: "Impossible"
```
s and t must each be "()", but then s[0] != t[p[0]], so it is impossible to find such s and t.
```
{4,5,6,7,0,1,2,3}
```
```
Returns: "(())(())"
```
Another valid solution is: s = t = "()()()()".

{9,8,7,6,5,4,3,2,1,0}

Returns: "Impossible"

```
{0,1}
```
```
Returns: "()"
```

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.