I was attempting the C question and eventually looked up the editorial as my own method was failing pretests.
The editorial is based on a formula which is without any proof.
If possible can anybody guide me as to how they came up with it?
This is my submission:
/*author - Ashutosh Chitranshi*/
#include<bits/stdc++.h>
using namespace std;
#pragma GCC push_options
#pragma GCC optimize ("unroll-loops")
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
#define pow2(x) ((x)*(x))
#define ll long long
#define ld long double
#define eb emplace_back
#define pb push_back
#define pf push_front
#define mod 1000000007
#define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
#define mp make_pair
#define ff first
#define ss second
#define null NULL
#define all(c) (c).begin(),(c).end()
#define nl "\n"
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vi > vvi;
typedef vector< vl > vvl;
typedef pair< int,int > ii;
typedef pair< ll,ll> pll;
typedef map< ll,ll> mll;
typedef map< int,int> mii;
ll hash1[300005];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll n;
cin >> n;
string ar[n];
for(int i=0;i<n;i++)
cin >> ar[i];
for(int i=0;i<n;i++)
{
ll count = 0ll;
for(int j=0;j<ar[i].size();j++)
{
if(ar[i][j] == '(')
count++;
else
count--;
if(count < 0)
break;
}
if(count >= 0)
hash1[count]++;
}
ll ans = 0ll;
for(int i=0;i<n;i++)
{
ll count = 0ll;
for(int j=ar[i].size()-1;j>=0;j--)
{
if(ar[i][j] == ')')
count++;
else
count--;
if(count<0)
break;
}
if(count>=0)
ans += hash1[count];
}
cout << ans << nl;
return 0;
}
If any string has more closing bracket in prefix then opening brackets or more opening brackets in suffix then closing bracket in suffix then this string can not be concatenated with any other string in order to make a correct bracket sequence.
First iterate through all strings and for each string that obeys the above condition on prefix store its difference of opening and closing brackets.
Now iterate through all strings from right to left and check for each string if it obeys the condition on suffix you can concatenate it with all strings having same number of extra opening bracket as it has closing brackets.
1 Like
Thanks. I understood it now. The editorial too has done it on similar lines but in a fashionable manner 
1 Like