johnchen902's blog

Super Parentheses Matching Problem
By johnchen902, 10 years ago, In English

I ran across this problem several months ago, but I can't think up with an algorithm fast enough:

You're given a string S (|S| <= 500000) consisting of '(', ')' and '?', where '?' can (and must) be changed to either ( or ).

If the ith question mark is changed to '(', you'll get a penalty of L[i] (L[i] is in the range of int).

If the ith question mark is changed to ')', you'll get a penalty of R[i] (R[i] is in the range of int).

Given S, L and R, is it possible to produce a valid (matching) parentheses sequence? And if yes, what is minimum penalty you must pay?  

The time limit is 0.2s and the memory limit is 64Mib.

Samples:

S="(())"       L={}           R={}            -> result=0
S="(??)"       L={1,10}       R={10,100}      -> result=20
S="?????)))))" L={2,2,2,2,2}  R={1,1,1,1,1}   -> result=10
S="(((((?"     L={2147483647} R={-2147483648} -> result=impossible

When I first encountered this problem, I came up with a Θ(n2) dynamic programming solution. Of course, that leads to TLE. Code

Last week, I came up with a greedy solution. Unfortunately, it was still a Θ(n2) solution. Code

After several months of struggle, I decided to ask you smart folks to help me. Can you came up with a solution?

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Take a look at 3D - Least Cost Bracket Sequence.

→ Reply
»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

We can convert the rules for validity of a sequence of parentheses into "we have an array of weights L[i] - R[i], pick K of them such that there are at least A[i] of them among the first i positions and their sum is maximum".

This can be solved in time with sweepline greedy. Just store yet unused costs up to the current index and when you need more of them used, then use the smallest ones.

→ Reply