Connection Status:
Competition Arena > ParenthesesAndPermutation

ParenthesesAndPermutation

2016 TCO Algo 3A · 2016-03-24 · by cgy4ever

2016 TCO Algo 3A · 2016-03-24 · by cgy4ever · Greedy
Class Name: ParenthesesAndPermutation
Return Type: String
Method Name: getSequence
Arg Types: (vector<int>)
Problem Statement

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.

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

2)
{4,5,6,7,0,1,2,3}
Returns: "(())(())"

Another valid solution is: s = t = "()()()()".

3)
{9,8,7,6,5,4,3,2,1,0}
Returns: "Impossible"
4)
{0,1}
Returns: "()"

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

Coding Area

Language: C++17 · define a public class ParenthesesAndPermutation with a public method string getSequence(vector<int> p) · 123 test cases · 2 s / 256 MB per case

Submitting as anonymous