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)
Limits
Time limit (s): 2.000
Memory limit (MB): 256
Stack limit (MB): 256
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 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)2003, TopCoder, Inc. All rights reserved.
---------------------------------------EDITORIAL----------------------------------------------------------
DP IMPLEMENTATION OF THIS PROBLEM IS VERY TRICKY ,
IN DP IMPLEMENTATION WE ARE JUST TRYING TO CREATE ALL POSSIBLE
STRINGS WHICH ARE VALID ( MEANS AT EACH STEP WE EITHER ADD A ( OR A CLOSE ) , BUT THE WAY WHICH WE ARE DOING THIS WILL NEVER LEAD TO TO ANY REPETIVE STRING ,,,,
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 ii to a position in ss. When we decide to add a "(" to the subsequence, find the smallest position jj greater than or equal to ii such that s[j]s[j] is "(" then move ii to j+1j+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)f(o,i) that will give us the number of ways to complete a subsequence with oo open brackets if we can only use characters in ss after index ii:
When o=0o=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 jj such that: s[j]s[j] is "(" and j≥ij≥i. Then we can continue adding characters to the subsequence but this time the number of open brackets increased and ii changed to j+1j+1: There are f(⊕1,j+1)f(⊕1,j+1) ways to complete the subsequence after this step.
If o≠0o≠0 we can decide to close a bracket by adding a ")" character. Find the smallest jj such that s[j]s[j] is ")" and j≥ij≥i. This adds f(o−1,j+1)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)f(o,i) has O(n2)O(n2) possible states. In each state, we might need an O(n)O(n) loop to find the smallest position of the "(" and ")" characters. The total time complexity is O(n3)O(n3), very appropriate for n≤100n≤100.
----------------------------------------------CODE----------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
typedef long long int lli;
lli dp[105][105];
int n;
string s;
int next_idx(int cur, char c)
{
// cout<<" cur pos "<<cur<<" search for "<<c<<endl;
int len=s.length();
for(int i=cur;i<len;i++)
{
if(s[i]==c)
{
// cout<<" found at "<<i<<endl;
return i;
}
}
return -1;
}
int solve(int opens,int idx)
{
// cout<<" opens "<<opens<<" idx "<<idx<<endl;
if(idx==n)
{
if(opens==0) return 1;
else return 0;
}
if(opens>n/2) return 0;
else if(dp[opens][idx]!=-1)
{
return dp[opens][idx];
}
else
{
lli ret=0;
if(opens==0) ret++;
if(opens>0)
{
int np=next_idx(idx,')');
if(np!=-1)
{
ret=(ret+solve(opens-1,np+1))%mod;
}
}
int np=next_idx(idx,'(');
if(np!=-1)
{
ret=(ret+solve(opens+1,np+1))%mod;
}
dp[opens][idx]=ret;
return ret;
}
}
int count(string ss)
{
s=ss;
memset(dp,-1,sizeof dp);
int ans=solve(0,0);
// cout<<ans<<endl;
return ans-1;// removing empty string from answer ...
}
int main()
{
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
n=s.length();
cout<<count(s)<<endl;;
}
}
======= HOW IT IS WORKING AND WITHOUT REPEAT OF STRING ===============
LET US TAKE AN EXAMPLE
()())
AS IN THE ABOVE APPROACH WE ARE JUST TRYING TO CRATE ALL POSSIBLE STRING OF LENGTH n FRO M THE GIVEN STRING
OUR WHEN WE START INITIALLY AND WE TRY TO MAKE A STRING ()
THAN THIS APPROACH ALWAYS CHOSE 1 ST AND 2ND CHARACTER
TO MAKE () IT WILL NEVER PICK 3RD AND 4T CHARACTER
SINCE WE ALWAYS PIC CHARACTER FROM NEAREST j WHICH >=i
SO AS WE ARE TRYING TO CREATE STRING SO FOR ANY STRING WE CAN EITHER
NOT FORM IT FROM THE GIVEN STRING OR WE CAN ALWAYS FORM IN A SINGLE WAY ACCORDING OUT APPROACH .......
No comments:
Post a Comment