PROBLEM LINK:
Division 1
Division 2
Video Editorial
Author: Naman Jain
Tester: Rahul Dugar
Editorialist: Ritesh Gupta
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming, Binary Search
PROBLEM:
You are given N bracket sequences. You have to find the smallest prefix that can be selected such that there exists a valid subset of this prefix which can be used to produce a balanced bracket sequence.
QUICK EXPLANATION:
- First, we normalize the given strings. To do so, we remove any two adjacent characters if first one is open bracket and second one is close bracket. Do this until there is no such pair.
- Now, strings can be expressed as some or zero number of close brackets followed by some or zero number of open brackets.
- We can apply Binary Search over the length of the array of strings to find the answer.
- For each value in binary search, we divide those strings which are present in that prefix, into two groups. One group contains all the strings which have more open brackets then close brackets and rest are present in the second group.
- Now, we can use dynamic programming to find whether it is possible to form a sequence of open brackets of length len only using sequences from the first group for each len from 1 to 10000 (look for the constraints for the problem, this the maximum length possible). Also, find the same with the close brackets from the second group.
- If there exists some sequence of length len for which both open and close sequences are possible then we can say that we can select some subset of strings from this prefix to form the balanced bracket sequence.
EXPLANATION:
We can say that there is no need to keep the balanced substrings of the original string. So, we need to remove them first. To do that, we need to find two adjacent characters of some string and remove them if the first one is an open bracket and the second one is a closed bracket. We do this over a string until either staging is empty or there is know valid pair of adjacent characters of this type.
After this, each string can be expressed as a set of close brackets (0 or more) followed by a set of open brackets (0 or more).
Let’s say that we can choose a subset of first m strings to form a balanced string, then we can also choose the same subset from first m+x strings where 0 \le x \le n-m. This will satisfy the binary search property, so we can use binary search to find the minimum length of prefix that needs to be considered to validate the condition given in the problem.
But how can we find whether there exists a subset of string from a given string? It could be achieved by dynamic programming. We first need to divide the normalised stings into two groups. One group contains all the strings which have more open brackets then close brackets and rest are present in the second group.
As we divided the groups into logical separation so that by selecting some of the strings from the first group, we can say that it should produce some bracket sequence which has only open brackets in it and vice-versa for the second group.
With dynamic programming, for each len from 0 to 10000, we are finding whether, it is possible to construct a string of only open brackets of length len using zero or more strings from the first group and same form second group but trying to construct a string of only close brackets.
Then we try to find whether there exists some len such that both only open bracket and only close bracket sequence is possible to form with the length len.
In dynamic programming, we are creating a 2D table T to compute and store the answer. A cell in table i.e. T[i][j] where 1 \le i \le length of group, we are considering and 0 \le j \le 10000, represent whether it is possible to construct a only open bracket sequence from first i strings and has a size equal to j.
To calculate a cell value, we can say that:
- If we don’t consider the current string then the answer is from the previous state with 1 less i value but same j value, i.e. T[i][j] = T[i-1][j]
- Else if we are considering this string then T[i][j] = T[i][j-x] where x is the absolute difference between open and close brackets of the sequence. If j < x then we don’t compute it as it is not possible and if j == x then the answer should be true. why?
TIME COMPLEXITY:
TIME: O(N^3 * logN)
SPACE: O(N^3)
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> ostream& operator<<(ostream &os, vector<T> V) {
os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
return os << "(" << P.first << "," << P.second << ")";}
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 1
#endif
#define vi vector<int>
#define pii pair<int, int>
#define vpii vector< pii >
#define I insert
#define pb push_back
#define F first
#define S second
#define ll long long
#define ld long double
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define endl "\n"
// const int mod=1e9+7;
// inline int mul(int a,int b){return (a*1ll*b)%mod;}
// inline int add(int a,int b){a+=b;if(a>=mod)a-=mod;return a;}
// inline int sub(int a,int b){a-=b;if(a<0)a+=mod;return a;}
// inline int power(int a,int b){int rt=1;while(b>0){if(b&1)rt=mul(rt,a);a=mul(a,a);b>>=1;}return rt;}
// inline int inv(int a){return power(a,mod-2);}
// inline void modadd(int &a,int &b){a+=b;if(a>=mod)a-=mod;}
const int M = 100*100+15;
pii get(string &s){
int a=0, b=0;
for(auto z:s){
if(z=='('){
b++;
}
else {
if(b>0) b--;
else a++;
}
}
return {a, b};
}
int N;
vpii seq;
void calc(vpii &p, vector<bool> &dp){
dp[0] = true;
for(auto z:p){
int d = z.S - z.F;
for(int i = (M-1)-d; i>=z.F; i--)
dp[i+d] = dp[i+d] | dp[i];
}
dp[0] = 0;
}
bool check(int m){
vpii p[2];
for(int i=0;i<m;i++){
int a, b; tie(a, b) = seq[i];
if(a==0 && b==0) return true;
if(a < b) p[0].pb({a, b});
else if(a > b) p[1].pb({b, a});
}
sort(p[0].begin(), p[0].end());
sort(p[1].begin(), p[1].end());
vector<bool> dp1(M, 0), dp2(M, 0);
calc(p[0], dp1);
calc(p[1], dp2);
bool ans = false;
// int sam = -1;
for(int i=1; i<M; i++){
// if((sam==-1) && (dp1[i] && dp2[i])) sam = i;
ans |= (dp1[i] && dp2[i]) ;
}
// if(ans) trace(m, sam);
return ans;
}
void solve(){
cin>>N; seq.clear();
for(int i=0;i<N;i++){
string s; cin>>s;
seq.pb(get(s));
}
int lo = 1, hi = N;
int ans = -1;
while(lo <= hi){
int mid = (lo+hi)/2;
// trace(mid);
if(check(mid)){
ans = mid;
hi = mid-1;
}
else lo = mid+1;
}
cout<<ans<<"\n";
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<setprecision(25);
int T; cin>>T;
while(T--) solve();
}
Tester's Solution
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
//#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
bitset<20005> dp,dp2;
pii a[205];
bool yes(int n) {
dp.reset();
vector<pii> gogo(a+1,a+n+1);
sort(all(gogo),[](pii a, pii b){
if((a.fi>a.se)!=(b.fi>b.se))
return (a.fi>a.se)>(b.fi>b.se);
if(a.fi>a.se)
return a.se<b.se;
else
return a.fi>b.fi;
});
for(auto i:gogo) {
dp2=dp;
dp2>>=i.se;
dp2<<=i.fi;
dp|=dp2;
if(i.se==0)
dp[i.fi]=1;
}
return dp[0];
}
void solve() {
int n;
cin>>n;
int ans=-1;
fr(i,1,n) {
string s;
cin>>s;
if(ans!=-1)
continue;
int mm=0;
int ma=0,mi=0;
for(char i:s) {
if(i=='(')
mm++;
else
mm--;
mi=min(mi,mm);
}
reverse(all(s));
mm=0;
for(char i:s) {
if(i=='(')
mm++;
else
mm--;
ma=max(ma,mm);
}
mi*=-1;
trace(ma,mi);
a[i]={ma,mi};
}
a[n+1]={0,0};
int lo=1,hi=n+1,mid=(lo+hi)/2;
while(lo<hi) {
if(yes(mid)) {
hi=mid;
} else
lo=mid+1;
mid=(lo+hi)/2;
}
ans=mid;
if(mid==n+1)
ans=-1;
cout<<ans<<endl;
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(8);
// int t=readIntLn(1,10);
int t;
cin>>t;
fr(i,1,t)
solve();
// assert(getchar()==EOF);
return 0;
}