Two Bracket Sequences
Contest: Codeforces Round 605 (Div. 3)
Difficulty rating: 2200
Tags: dp, strings, two pointers

You are given two bracket sequences (not necessarily regular) $$$s$$$ and $$$t$$$ consisting only of characters '(' and ')'. You want to construct the shortest regular bracket sequence that contains both given bracket sequences as subsequences (not necessarily contiguous).

Recall what is the regular bracket sequence:

- () is the regular bracket sequence;
- if $$$S$$$ is the regular bracket sequence, then ($$$S$$$) is a regular bracket sequence;
- if $$$S$$$ and $$$T$$$ regular bracket sequences, then $$$ST$$$ (concatenation of $$$S$$$ and $$$T$$$) is a regular bracket sequence.

Recall that the subsequence of the string $$$s$$$ is such string $$$t$$$ that can be obtained from $$$s$$$ by removing some (possibly, zero) amount of characters. For example, "coder", "force", "cf" and "cores" are subsequences of "codeforces", but "fed" and "z" are not.

Input format:
The first line of the input contains one bracket sequence $$$s$$$ consisting of no more than $$$200$$$ characters '(' and ')'.

The second line of the input contains one bracket sequence $$$t$$$ consisting of no more than $$$200$$$ characters '(' and ')'.

Output format:
Print one line — the shortest regular bracket sequence that contains both given bracket sequences as subsequences (not necessarily contiguous). If there are several answers, you can print any.

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

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

Example output:
(())()()

Example input:
)
((

Example output:
(())

Editorial:
Firstly, notice that the length of the answer cannot exceed $$$400$$$ ($$$200$$$ copies of ()). Now we can do some kind of simple dynamic programming. Let $$$dp_{i, j, bal}$$$ be the minimum possible length of the prefix of the regular bracket sequence if we are processed first $$$i$$$ characters of the first sequence, first $$$j$$$ characters of the second sequence and the current balance is $$$bal$$$. Each dimension of this dp should have a size nearby $$$200 + \varepsilon$$$.
The base of this dp is $$$dp_{0, 0, 0} = 0$$$, all other values $$$dp_{i, j, bal} = +\infty$$$.
Transitions are very easy: if we want to place the opening bracket, then we increase $$$i$$$ if the $$$i$$$-th character of $$$s$$$ exists and equals '(', the same with the second sequence and $$$j$$$, the balance increases by one, and the length of the answer increases by one. If we want to place the closing bracket, then we increase $$$i$$$ if the $$$i$$$-th character of $$$s$$$ exists and equals ')', the same with the second sequence and $$$j$$$, the balance decreases by one, and the length of the answer increases by one. Note that the balance cannot be greater than $$$200$$$ or less than $$$0$$$ at any moment.
Don't forget to maintain parents in this dp to restore the actual answer!
The last problem that can be unresolved is how to write this dp? The easiest way is bfs, because every single transition increases our answer by one. Then we can restore answer from the state $$$dp_{|s|, |t|, 0}$$$. You can write it recursively, but I don't sure this will look good. And you also can write it just with nested loops, if you are careful enough.
Time complexity: $$$O(|s| \cdot |t| \cdot max(|s|, |t|))$$$.
If you know the faster solution, please share it!