Problem Statement for BracketSequenceDiv2

Problem Statement      Correct bracket 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 bracket sequence can be derived using the above rules. Examples of correct bracket sequences include "", "()", "()()()", "(()())", and "(((())))". A string T is called a subsequence of a string S if we can erase some (possibly none or all) characters of S to obtain T. For example, "bdf" is a subsequence of "abcdefg". You are given a String s that consists of the characters '(' and ')' only. Let X be the number of different non-empty subsequences of s that are correct bracket sequences. Note that each distinct subsequence should only be counted once, even if it can be obtained from s in multiple ways. (See the examples for clarification.) Compute and return the value (X modulo 1,000,000,007).   Definition      Class: BracketSequenceDiv2 Method: count Parameters: String Returns: int Method signature: int count(String s) (be sure your method is public)        Constraints - s will contain between 1 and 100 characters, inclusive. - Each character in s will be '(' or ')'.   Examples 0)      "(())(" Returns: 2 Correct non-empty bracket subsequences are "()" and "(())". 1)      "())" Returns: 1 Only "()" is suitable. 2)      ")(((" Returns: 0 There are no non-empty correct bracket subsequences. 3)      "()()()()()()()()(())))(()()()()))())" Returns: 364675 4)      "()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()" Returns: 122826009 Do not forget to take answer modulo 1,000,000,007. This DP opened up a new dimension for me. The way we look at solving the DP, heres the cool blog by Vexorian That we need to count the unique subsequences makes things more complicated because we don't want to count duplicates. To work around this, imagine if we were generating the subsequence and then checking if it is possible to find the subsequence in the string. Imagine we had a subsequence like "(())()" to check if it is a possible subsequence of s${\displaystyle s}$ we can begin with its first character "(" and find the left-most position j${\displaystyle j}$ of "(" in s${\displaystyle s}$. Then we continue with the second character which is another "(" and find the left-most position after j${\displaystyle j}$ that is equal to "(" and so and so until we find all the characters in the subsequence in s${\displaystyle s}$ or until we run out of positions of s${\displaystyle s}$ Dynamic programming In order to use that logic we would have to generate the subsequence step by step. We begin with an empty string and add "(" or ")" in each step, making sure the subsequence is a correct bracket sequence. We also start with a pointer i${\displaystyle i}$ to a position in s${\displaystyle s}$. When we decide to add a "(" to the subsequence, find the smallest position j${\displaystyle j}$ greater than or equal to i${\displaystyle i}$ such that s[j]${\displaystyle s\left[j\right]}$ is "(" then move i${\displaystyle i}$ to j+1${\displaystyle j+1}$. The same with ")". This would look like a backtracking problem. We can find a dynamic programming approach by noticing that, in order to make sure the subsequence is a valid bracket sequence, we don't need to remember all the contents of the subsequence, just the number of open brackets. So if the characters currently in the subsequence are: "(()((()", then we only need to know there are 3 open bracket. With this in mind we can create a function f(o,i)${\displaystyle f(o,i)}$ that will give us the number of ways to complete a subsequence with o${\displaystyle o}$ open brackets if we can only use characters in s${\displaystyle s}$ after index i${\displaystyle i}$: When o=0${\displaystyle o=0}$, we already found a valid subsequence, because all the brackets are closed. We can also decide to add a "(" to the subsequence. Find the left-most position j${\displaystyle j}$ such that: s[j]${\displaystyle s\left[j\right]}$ is "(" and j≥i${\displaystyle j\ge i}$. Then we can continue adding characters to the subsequence but this time the number of open brackets increased and i${\displaystyle i}$ changed to j+1${\displaystyle j+1}$: There are f(⊕1,j+1)${\displaystyle f(\oplus 1,j+1)}$ ways to complete the subsequence after this step. If o≠0${\displaystyle o\ne 0}$ we can decide to close a bracket by adding a ")" character. Find the smallest j${\displaystyle j}$ such that s[j]${\displaystyle s\left[j\right]}$ is ")" and j≥i${\displaystyle j\ge i}$. This adds f(o−1,j+1)${\displaystyle f(o-1,j+1)}$ new ways to complete the subsequence. The sum of those 3 cases is the result. In some cases, the "(" or ")" characters cannot be found in the string so we ignore them. The function f(o,i)${\displaystyle f(o,i)}$ has O(n2)${\displaystyle O\left(n^2\right)}$ possible states. In each state, we might need an O(n)${\displaystyle O\left(n\right)}$ loop to find the smallest position of the "(" and ")" characters. The total time complexity is O(n3)${\displaystyle O\left(n^3\right)}$, very appropriate for n≤100${\displaystyle n\le 100}$. #include<bits/stdc++.h> using namespace std; #define mod 1000000007 #define ll long long int  int  dp[110][110]; int getnext(string s,int idx,int ch,int l) {     int i;   for(i=idx;i<l;i++)   {        if(s[i]==ch)                {             return i;  }   }   return i; } int solve(int op,int idx,string s,int l) { //cout<<"op  idx "<<op<<" "<<idx<<endl;    if(idx==l)    {      if(op==0)      return 1;      return 0; } if(dp[op][idx]!=-1) return dp[op][idx]; int ret=0; if(op==0) ret++; int poso=getnext(s,idx,'(',l); // cout<<"for idx "<<idx<<" "<<poso<<endl; if(poso<l) { // cout<<"caleed "<<endl; ret+=solve(op+1,poso+1,s,l);     ret%=mod; }   int pose=getnext(s,idx,')',l); // cout<<" of idx "<<idx<<" "<<pose<<endl; if(op>=1 && pose<l) { // cout<<"clled close "<<endl;   ret+=solve(op-1,pose+1,s,l);   ret%=mod; } dp[op][idx]=ret; return ret; } int count(string s) {   int l=s.length();   memset(dp,-1,sizeof(dp));   int idx=0;   while(s[idx]!='(')   idx++;   if(idx==l)   return 0;   return solve(1,idx+1,s,l);  }#include<bits/stdc++.h> using namespace std; #define mod 1000000007 #define ll long long int  int  dp[110][110]; int getnext(string s,int idx,int ch,int l) {     int i;   for(i=idx;i<l;i++)   {        if(s[i]==ch)                {             return i;  }   }   return i; } int solve(int op,int idx,string s,int l) { //cout<<"op  idx "<<op<<" "<<idx<<endl;    if(idx==l)    {      if(op==0)      return 1;      return 0; } if(dp[op][idx]!=-1) return dp[op][idx]; int ret=0; if(op==0) ret++; int poso=getnext(s,idx,'(',l); // cout<<"for idx "<<idx<<" "<<poso<<endl; if(poso<l) { // cout<<"caleed "<<endl; ret+=solve(op+1,poso+1,s,l);     ret%=mod; }   int pose=getnext(s,idx,')',l); // cout<<" of idx "<<idx<<" "<<pose<<endl; if(op>=1 && pose<l) { // cout<<"clled close "<<endl;   ret+=solve(op-1,pose+1,s,l);   ret%=mod; } dp[op][idx]=ret; return ret; } int count(string s) {   int l=s.length();   memset(dp,-1,sizeof(dp));   int idx=0;   while(s[idx]!='(')   idx++;   if(idx==l)   return 0;   return solve(1,idx+1,s,l);  }