Connection Status:
Competition Arena > ParenthesesDiv2Hard

ParenthesesDiv2Hard

SRM 688 · 2016-04-01 · by cgy4ever

SRM 688 · 2016-04-01 · by cgy4ever · Dynamic Programming
Class Name: ParenthesesDiv2Hard
Return Type: int
Method Name: minSwaps
Arg Types: (string, vector<int>, 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 String s. You are also given int[]s L and R, each with the same number of elements. These encode a set of conditions. For each valid i, you have to satisfy the following condition: the substring of s that begins at the 0-based index L[i] and ends at the 0-based index R[i] must be a correct parentheses sequence. Note that the constraints guarantee that all the given ranges of indices are pairwise disjoint.


You can only modify s in one way: in each step you can choose two characters of s and swap them. Return the minimal number of swaps needed to produce a string that satisfies all the given conditions. If it is impossible, return -1 instead.

Constraints

  • s will contain between 1 and 50 characters, inclusive.
  • Each character in s will be '(' or ')'.
  • L will contain between 1 and 50 elements, inclusive.
  • L and R will contain the same number of elements.
  • For each valid i, 0 <= L[i] <= R[i] < |s|.
  • For different i and j, intervals [(L[i]), (R[i])] and [(L[j]), (R[j])] will not intersect.
Examples
0)
")("
{0}
{1}
Returns: 1

We have one condition: The substring that begins at index 0 and ends at index 1 must be a correct parentheses sequence. In this case, this means that the entire string s must be a correct parentheses sequence. We can achieve that by swapping s[0] with s[1]. This swap produces the string "()".

1)
"(())"
{0,2}
{1,3}
Returns: 1

The only way to satisfy both conditions is to change s into "()()". This can be done in 1 swap: by swapping s[1] with s[2].

2)
"(((())"
{0,2}
{1,3}
Returns: 2

This time we do swap(s[1],s[4]) and swap(s[3],s[5]).

3)
"((()()"
{0,2}
{1,3}
Returns: 1
4)
"((((((((("
{0,2}
{1,3}
Returns: -1

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

Coding Area

Language: C++17 · define a public class ParenthesesDiv2Hard with a public method int minSwaps(string s, vector<int> L, vector<int> R) · 86 test cases · 2 s / 256 MB per case

Submitting as anonymous