Get Time

   Problem Statement  

 Problem Statement for ParenthesesAndPermutation

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.


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


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


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 = "(())".
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.
Returns: "(())(())"
Another valid solution is: s = t = "()()()()".
Returns: "Impossible"
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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       2016 TCO Algorithm Round 3A - Division I, Level One