I'm trying to solve atcoder ABC167F. https://atcoder.jp/contests/abc167/tasks/abc167_f .↵
↵
I started by questioning what conditions decide whether a concatenation is valid. We start by defining sum of a bracketed sequence, which is ```count('(')-count(')')```. I then found the sum of every string, and the smallest sum of a prefix of the string. They are denoted by $sum$ and $mnprefix$ in my code. If my current string is valid which is equivalent to $mnprefix\ge 0$ and has a sum of $x$, then a concatenation is valid if and only if $x+mnprefix\ge 0$ and our new sequnce has a sum of $x+sum$. Let's say we have two strings $a$ and $b$. Let $a.sum$ denote the sum of $a$ and the rest of the notation is deductible.↵
↵
Let's say $a$ comes before $b$. Then the two conditions that need to be valid are $x\ge a.mnprefix$ and $x\ge b.mnprefix-a.sum$.↵
So we want $\max(a.mnprefix, b.mnprefix-a.sum)\le \max(b.mnprefix, a.mnprefix - b.sum)$ for $a$ to be chosen before $b$. However my proof has one flaw, which is that it doesn't account for transitivity. I don't know how to prove another string $c$ will not affect my result, and how do I know my comparator function is transitive, as each string doesn't have an exact value, and the comparator values are differing according to the string being compared to.↵
↵
If my solution is correct, can someone tell me if I have made an error in my implementation.↵
↵
<spoiler summary="My code">↵
```↵
#include <iostream>↵
#include <bits/stdc++.h>↵
#include <cmath>↵
#include <vector>↵
#define ll long long int↵
#define mp make_pair↵
#define pb emplace_back↵
#define vi vector<int>↵
using namespace std;↵
struct brackets{↵
int mnprefix, sum;↵
brackets(const string &s){↵
mnprefix=0;↵
sum=0;↵
for(int i=0;i<s.size();i++){↵
if(s[i]=='('){↵
sum++;↵
}↵
if(s[i]==')'){↵
--sum;↵
}↵
mnprefix=min(mnprefix, sum);↵
}↵
}↵
bool operator<(const brackets &y){↵
return max(mnprefix, y.mnprefix-sum) < max(y.mnprefix, mnprefix - y.sum);↵
}↵
};↵
void solve(){↵
int n;↵
cin>>n;↵
vector<brackets> seq;↵
for(int i=0;i<n;i++){↵
string s;↵
cin>>s;↵
seq.pb(brackets(s));↵
}↵
sort(seq.begin(), seq.end());↵
int currsum=0;↵
for(int i=0;i<n;i++){↵
if(currsum+seq[i].mnprefix<0){↵
cout<<"No\n";↵
return;↵
}↵
currsum+=seq[i].sum;↵
}↵
if(currsum!=0){↵
cout<<"No\n";↵
return;↵
}↵
cout<<"Yes\n";↵
}↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
solve();↵
}↵
//17/32 correct↵
```↵
</spoiler>↵
↵
Edit : nvm, I was using ```abs(mnprefix)``` in my calculation but not in my code.↵
↵
I started by questioning what conditions decide whether a concatenation is valid. We start by defining sum of a bracketed sequence, which is ```count('(')-count(')')```. I then found the sum of every string, and the smallest sum of a prefix of the string. They are denoted by $sum$ and $mnprefix$ in my code. If my current string is valid which is equivalent to $mnprefix\ge 0$ and has a sum of $x$, then a concatenation is valid if and only if $x+mnprefix\ge 0$ and our new sequnce has a sum of $x+sum$. Let's say we have two strings $a$ and $b$. Let $a.sum$ denote the sum of $a$ and the rest of the notation is deductible.↵
↵
Let's say $a$ comes before $b$. Then the two conditions that need to be valid are $x\ge a.mnprefix$ and $x\ge b.mnprefix-a.sum$.↵
So we want $\max(a.mnprefix, b.mnprefix-a.sum)\le \max(b.mnprefix, a.mnprefix - b.sum)$ for $a$ to be chosen before $b$. However my proof has one flaw, which is that it doesn't account for transitivity. I don't know how to prove another string $c$ will not affect my result, and how do I know my comparator function is transitive, as each string doesn't have an exact value, and the comparator values are differing according to the string being compared to.↵
↵
If my solution is correct, can someone tell me if I have made an error in my implementation.↵
↵
<spoiler summary="My code">↵
```↵
#include <iostream>↵
#include <bits/stdc++.h>↵
#include <cmath>↵
#include <vector>↵
#define ll long long int↵
#define mp make_pair↵
#define pb emplace_back↵
#define vi vector<int>↵
using namespace std;↵
struct brackets{↵
int mnprefix, sum;↵
brackets(const string &s){↵
mnprefix=0;↵
sum=0;↵
for(int i=0;i<s.size();i++){↵
if(s[i]=='('){↵
sum++;↵
}↵
if(s[i]==')'){↵
--sum;↵
}↵
mnprefix=min(mnprefix, sum);↵
}↵
}↵
bool operator<(const brackets &y){↵
return max(mnprefix, y.mnprefix-sum) < max(y.mnprefix, mnprefix - y.sum);↵
}↵
};↵
void solve(){↵
int n;↵
cin>>n;↵
vector<brackets> seq;↵
for(int i=0;i<n;i++){↵
string s;↵
cin>>s;↵
seq.pb(brackets(s));↵
}↵
sort(seq.begin(), seq.end());↵
int currsum=0;↵
for(int i=0;i<n;i++){↵
if(currsum+seq[i].mnprefix<0){↵
cout<<"No\n";↵
return;↵
}↵
currsum+=seq[i].sum;↵
}↵
if(currsum!=0){↵
cout<<"No\n";↵
return;↵
}↵
cout<<"Yes\n";↵
}↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
solve();↵
}↵
//17/32 correct↵
```↵
</spoiler>↵
↵
Edit : nvm, I was using ```abs(mnprefix)``` in my calculation but not in my code.↵
