Connection Status:
Competition Arena > ParenthesisRemoval

ParenthesisRemoval

SRM 714 · 2017-02-20 · by lg5293

SRM 714 · 2017-02-20 · by lg5293 · Math
Class Name: ParenthesisRemoval
Return Type: int
Method Name: countWays
Arg Types: (string)
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 that is guaranteed to be a correct parentheses sequence. A removal is an action that consists of two steps:

  1. Remove the first opening parenthesis in s.
  2. Remove one closing parenthesis in s. After you do so, s must again be a correct parentheses sequence.

Compute and return the number of distinct ways in which s can be reduced to an empty string by performing consecutive removals, modulo 10^9+7. Two ways are considered distinct if there is a step in which you remove a different closing parenthesis. (See Example 1 for clarification.)

Constraints

  • s will have between 2 and 2,500 characters, inclusive.
  • s will be a correct parentheses sequence.
Examples
0)
"()()()()()"
Returns: 1

In each removal we have to choose the leftmost closing parenthesis.

1)
"(((())))"
Returns: 24

In each removal we can choose any closing parenthesis we want. Note that these count as distint choices, even though all choices lead to the same string. Thus, there are 4*3*2*1 = 24 different sequences of removals that change s into an empty string.

2)
"((()()()))"
Returns: 54

Below is one of the 54 possible sequences of removals. Remember that in each step we also remove the first opening parenthesis. Remove the fourth closing parenthesis: "(()()())" Remove the second closing parenthesis: "()(())" Remove the first closing parenthesis: "(())" Remove the second closing parenthesis: "()" Remove the first closing parenthesis: ""

3)
"(())(())(())"
Returns: 8
4)
"((((())((((((((((()((((((()))))())))))()))))))))))"
Returns: 948334170

Don't forget about the mod.

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

Coding Area

Language: C++17 · define a public class ParenthesisRemoval with a public method int countWays(string s) · 92 test cases · 2 s / 256 MB per case

Submitting as anonymous