RBS
Contest: Educational Codeforces Round 115 (Rated for Div. 2)
Difficulty rating: 2400
Tags: binary search, bitmasks, brute force, data structures, dp

A bracket sequence is a string containing only characters "(" and ")". A regular bracket sequence (or, shortly, an RBS) is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example:

- bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)");
- bracket sequences ")(", "(" and ")" are not.

Let's denote the concatenation of two strings $$$x$$$ and $$$y$$$ as $$$x+y$$$. For example, "()()" $$$+$$$ ")(" $$$=$$$ "()())(".

You are given $$$n$$$ bracket sequences $$$s_1, s_2, \dots, s_n$$$. You can rearrange them in any order (you can rearrange only the strings themselves, but not the characters in them).

Your task is to rearrange the strings in such a way that the string $$$s_1 + s_2 + \dots + s_n$$$ has as many non-empty prefixes that are RBS as possible.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 20$$$).

Then $$$n$$$ lines follow, the $$$i$$$-th of them contains $$$s_i$$$ — a bracket sequence (a string consisting of characters "(" and/or ")". All sequences $$$s_i$$$ are non-empty, their total length does not exceed $$$4 \cdot 10^5$$$.

Output format:
Print one integer — the maximum number of non-empty prefixes that are RBS for the string $$$s_1 + s_2 + \dots + s_n$$$, if the strings $$$s_1, s_2, \dots, s_n$$$ can be rearranged arbitrarily.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first example, you can concatenate the strings as follows: "(" $$$+$$$ ")" $$$=$$$ "()", the resulting string will have one prefix, that is an RBS: "()".

In the second example, you can concatenate the strings as follows: "(" $$$+$$$ ")" $$$+$$$ "()()())" $$$+$$$ "(" $$$=$$$ "()()()())(", the resulting string will have four prefixes that are RBS: "()", "()()", "()()()", "()()()()".

The third and the fourth examples contain only one string each, so the order is fixed.

Example input:
2
(
)

Example output:
1

Example input:
4
()()())
(
(
)

Example output:
4

Editorial:
The constraint $$$n \le 20$$$ is a clear hint that we need some exponential solution. Of course, we cannot try all $$$n!$$$ permutations. Let's instead try to design a solution with bitmask dynamic programming.
A string is an RBS if its balance (the difference between the number of opening and closing brackets) is $$$0$$$, and the balance of its each prefix is non-negative. So, let's introduce the following dynamic programming: $$$dp_{m,b,f}$$$ is the greatest number of RBS-prefixes of a string if we considered a mask $$$m$$$ of strings $$$s_i$$$, the current balance of the prefix is $$$b$$$, and $$$f$$$ is a flag that denotes whether there already has been a prefix with negative balance. We can already get rid of one of the states: the current balance is uniquely determined by the mask $$$m$$$. So, this dynamic programming will have $$$O(2^{n+1})$$$ states.
To perform transitions, we need to find a way to recalculate the value of $$$f$$$ and the answer if we append a new string at the end of the current one. Unfortunately, it's too slow to simply simulate the process. Instead, for every string $$$s_i$$$, let's precalculate the value $$$go(s_i, f, x)$$$ — how does the flag and the answer change, if the current flag is $$$f$$$, and the current balance is $$$x$$$.
The resulting flag will be true in one of the following two cases:
• it is already true;
• the string we append creates a new prefix with non-positive balance.
The second case can be checked as follows: let's precalculate the minimum balance of a prefix of $$$s_i$$$; let it be $$$c$$$. If $$$x + c < 0$$$, the flag will be true.
Calculating how the answer changes is a bit trickier. If the current flag is already true, the answer doesn't change. But if it is false, the answer will increase by the number of new RBS-prefixes. If the balance before adding the string $$$s_i$$$ is $$$b$$$, then we get a new RBS-prefix for every prefix of $$$s_i$$$ such that:
• its balance is exactly $$$(-b)$$$ (to compensate the balance we already have);
• there is no prefix with balance $$$(-b-1)$$$ in $$$s_i$$$ before this prefix.
To quickly get the number of prefixes meeting these constraints, we can create a data structure that stores the following information: for every balance $$$j$$$, store a sorted vector of positions in $$$s_i$$$ with balance equal to $$$j$$$. Then, to calculate the number of prefixes meeting the constraints, we can find the first position in $$$s_i$$$ with balance equal to $$$(-b-1)$$$ by looking at the beginning of the vector for $$$(-b-1)$$$, and then get the number of elements less than this one from the vector for balance $$$(-b)$$$ by binary search.
These optimizations yield a solution in $$$O(2^n \log A + A \log A)$$$, although it's possible to improve to $$$O(2^n + A \log A)$$$ if you precalculate each value of $$$go(s_i, f, x)$$$ for every string $$$s_i$$$.