1
$\begingroup$

Given $n$ strings consisting only of '$($' and '$)$', how one can compute the length of the longest string that can be built by concatenating a subset of these strings in some order such that the resulting string is a balanced parenthesis?

Example: If we have the strings $\{"(()",")(",")","(("\}$, one can build the string $"(())()"$ which has length 6. We cannot construct a longer one from the previous set, thus the answer is 6.

In general, the answer is always even, and always $\geq 0$ because we can always take the empty set.

Problem source: North American Invitational Programming Contest (NAPIC) 2017, Problem A.

$\endgroup$
  • $\begingroup$ Thanks @D.W. ! Nope, each string can only be used once. Actually, I'm looking for something that can process queries of size roughly n=300 per second. currently, I'm just doing a brute force search by taking one string at a time and either adding it to the left/right of the current string or not adding it at all and maintaining two variables to detect if the resulting string is balanced... but this too slow. No I wasn't looking at this from the regular language or context-free grammar point of view. I'll try to think about it this way maybe ill find something useful. $\endgroup$ – cave_93 Apr 17 '17 at 0:35
  • $\begingroup$ Their website says they'll post judges data soon: naipc.uchicago.edu/2017/results.html. Maybe they'll include solutions. $\endgroup$ – D.W. Apr 18 '17 at 21:36
  • $\begingroup$ Great, ill be looking for that Thanks. $\endgroup$ – cave_93 Apr 18 '17 at 21:43
  • $\begingroup$ Solutions are now posted: serjudging.vanb.org/?p=1050. If you're particularly enterprising, you could read the source code from the sample solutions and see if you can work out the ideas behind their solutions. $\endgroup$ – D.W. Jul 18 '17 at 20:34
  • $\begingroup$ Great I'll take a look at it! $\endgroup$ – cave_93 Jul 27 '17 at 7:04
1
$\begingroup$

First, let's remark that the order in which you put the selected strings is not significant as long as it is valid. That means that you can put the strings in a canonical order and you know that the solution is a subsequence of that sequence. The canonical order I suggest is first the strings which increase the number of opened parenthesis (with D.W. triplet notation, the triplets $\langle i,j,\ell \rangle$ for which $j>i$) tied resolved by increasing $i$, then those which don't change the number of opened parenthesis ($i=j$) then those which decrease the number of opened parenthesis($i>j$) this time solving the tie by decreasing $i$.

Then you apply the favorite technique of programming contests: dynamic programming. You are filling an array of $n$ columns. An entry $c,r$ of $\ell$ states that with the $c$ first strings in our canonical order, you can have $r$ opened parenthesis pending with a total length of $\ell$. This is filled using the content of the column $c-1$ with the initial column stating that with no strings you have a $0$ opened parenthesis pending and a length of $0$. You have to pay attention to avoid entries which would need to have more opened parenthesis than available, and when an entry is reachable with two lengths to keep the longest one.

You avoid the exponential behavior because you know that the strings have a bounded length of 300 (thus you can't have more than $300\; c$ opened parenthesis after $c$ columns instead of the $2^c$ entries which would have been possible without that bound) and thus you are sure that after the ninth or so column, you'll have duplicate entries.

$\endgroup$
0
$\begingroup$

I don't know of any algorithm whose worst-case running time is reasonable. I list below an approach that almost works, but becomes slow when we add logic to ensure that no string is used more than once. Perhaps you can find a way to improve it.

Treat two strings $x,y$ as equivalent (written $x \sim y$) if you can obtain one from the other by repeatedly removing or inserting $()$. For instance, $()( \sim ( \sim (()$.

Now, every string of parenthesis is either (a) equivalent to $)^i (^j$ for some $i,j \in \mathbb{N}$, or (b) cannot appear as a substring of any string with balanced parentheses. In case (b), there's no way to extend it to a solution to the problem, so such strings can be ignored, and we can focus on case (a).

We'll identify each string of parentheses with the tuple $\langle i,j,\ell \rangle$, where the string is equivalent to $)^i (^j$ and $\ell$ is the length of the string. Build an (implicitly-represented) graph corresponds to all valid sequences. We'll basically do pruned search in this graph.

In particular, we'll imagine a graph with one vertex for each valid sequence, and with the edge $u \to v$ if the sequence $v$ can be obtained from $u$ by appending one of the $n$ strings to $u$. Now, you can search the graph to find all vertices that are reachable from $\epsilon$ (the empty sequence of length 0). We're looking for the longest configuration of the form $\langle 0,0,\ell \rangle$ (i.e., the one where $\ell$ is as large as possible).

You can use any graph reachability algorithm, such as BFS. However as a heuristic I would suggest prioritizing exploration of longer configurations first, e.g., using a priority queue that is keyed on $\ell$. (Equivalently, you can think of this as using Dijkstra's algorithm where the length of each edge is the number of symbols appended -- the amount that it increases the length of the sequence.)

The problem with this approach is that it might end up using some of the $n$ strings more than once. Here is one way to fix that: now a configuration is given by $\langle i,j,\ell,S \rangle$, where $S$ represents the subset of $n$ strings that were used to construct this string. Unfortunately, now there can be exponentially many configurations.

A possible advantage of this approach is that you don't try to explore all orderings: you can prune sequences can't possibly be present in any valid answer, and thus possibly explore fewer than all possible subsets and orders. That said, this could still take exponential time in the worst case, so it might fail to be feasible.

This approach is asymptotically slightly better than the brute-force approach of exhaustively trying all possible sequences. The brute-force algorithm takes $O(n!) = O(2^{n \log n + O(n)})$ time. The approach I list here takes $O(n^3 2^n) = O(2^{n + O(\lg n)})$ time, which is better... but still exponential, alas.

$\endgroup$
  • $\begingroup$ Thanks for the answer, unfortunately this is still exponential. I need something that takes $O(n^3)$ max. Maybe the representation that you mentioned can be used to implement a dynamic programming solution instead of a graph search somehow? $\endgroup$ – cave_93 Apr 17 '17 at 23:04
-1
$\begingroup$

Your problem is $\text{NP}$-hard. It is an optimization version of the following decision problem. \begin{array}{|l|} \hline \textbf{Decision problem }\mathcal{P}\textbf{:}\\ \text{Given }n\text{ strings consisting only of `(' and `)', does there exist a subset of strings}\\ \text{which when concatenated in some order yield a string with balanced parenthesis?}\\ \hline \end{array}

I will now prove that Problem $\mathcal{P}$ is $\text{NP}$-hard.


We reduce subset sum problem which is known to be $\text{NP}$-complete to Problem $\mathcal{P}$.

Subset Sum Problem [NP-Complete]: Let $S=\{a_1, \cdots, a_k\}$ be the finite set of (including negative) integers. We need to decide whether there exists a subset $R \subseteq S$ such that sum of elements in $R$ is zero.

Reduction to Problem $\mathcal{P}$: We encode all $a_i \in S$ to strings of parenthesis in the following manner.

  • If $a_i = +m$, then its string encoding is $\text{Encode}(a_i) = `` \underbrace{((\cdots(}_{m \text{ times}} "$
  • If $a_i = -m$, then its string encoding is $\text{Encode}(a_i) =`` \underbrace{))\cdots)}_{m \text{ times}} "$

Now we encode sum operation. Let $S' = \{a_1, a_2, \cdots a_q \} \subseteq S$ be any non-empty set such that $a_1 \geq a_2 \geq \cdots \geq a_q$. Then sum over $S'$, $\Sigma \ S' = \text{Encode}(a_1) \circ \text{Encode}(a_2) \circ \dots \circ \text{Encode}(a_q)$, where $\circ$ is a string concatenation operation. With this encoding, following invariant property holds: Sum of a value $(i-j)$ is encoded as a string of the form $`` (^i \ )^j "$. Thus, the sum is zero iff parenthesis are balanced.

You can convince yourself that this reduction is polynomial one. This proves NP-hardness of your optimization problem. One way you can solve your problem is by encoding it in SAT or Integer Linear Programs. Then you can use state of art solvers like Z3, LP_SOLVE or GLPK to get a solution.

$\endgroup$
  • $\begingroup$ I believe there might be questions like why above encoding is polynomial? Such suspicion may be because an integer 'm' requiring 'log m' bits is encoded into 'm' bit string. This appears to be exponential encoding, and not polynomial. Resolution to this is we compress string "(^m" as a tuple [m, (] which says input '(' occurs 'm' times. Tuple [m, (] takes (log m + O(1)) bits, instead of full 'm' bits. $\endgroup$ – Devendra Bhave Apr 19 '17 at 11:01
  • $\begingroup$ Indeed this is a hint how to solve a problem. Subset sum might have good algorithms if the numbers given are in unary encoding. DP?.. $\endgroup$ – Eugene May 19 '17 at 10:15
  • $\begingroup$ The proof is faulty. This reduction doesn't run in polynomial time; if the number $m$ appears in the subset-sum instance, then its representation takes $\lg m$ bits, but the string encoding of it takes $m$ bits, which is exponentially large. To put it another way, you have reduced unary subset-sum to $\mathcal{P}$, but unary subset-sum isn't NP-hard (as far as we know). Binary subset-sum is NP-hard, but you haven't shown a reduction from binary subset-sum to $\mathcal{P}$. Therefore, this isn't a valid proof that $\mathcal{P}$ is NP-hard. $\endgroup$ – D.W. Jul 18 '17 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.