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?
Take a look at 3D - Least Cost Bracket Sequence.
Thank you for pointing it out!
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.