Help in SPOJ ANARCO9A solution using DP.

general
, ,
1

[ANARCO9A][1]
I am trying to solve it using following recursion ->

Let S(k, open) be the number of min operations to balance the string
with |open| open brackets by the time we start at k.
Let current bracket be cur. We have several cases:

  1. open is 0, and cur = ‘}’, then we have to flip.
    S(k, open) = 1 + S(k+1, open+1)
    open is 0 and cur = ‘{’, then we cannot flip.
    S(k, open) = S(k+1, open+1)
  2. open > 0 and cur = ‘}’. We can use cur to close an open bracket, or
    flip it to add new open brackets.
    S(k, open) = min( S(k+1, open-1), 1 + S(k+1, open+1) )
  3. open > 0 and cur = ‘{’, then we have
    S(k, open) = min( S(k+1, open+1), 1 + S(k+1, open-1) )

SOURCE : [[source][2]]. but It doesn’t works for cases like -> ‘{{{}’ or ‘{{{}{{{}’

My Code ->


[3] can you help in this ?

Thanks :)


  [1]: http://www.spoj.com/problems/ANARC09A/
  [2]: http://abitofcs.blogspot.in/2014/10/a-bit-of-string-balancing-spoj-anarc09a.html
  [3]: http://ideone.com/V5mX51
2

hey here is a <a href “http://ideone.com/tEpmdJ” > link of your code where slight modification made compare both code and find error. this is your homework :stuck_out_tongue: :slight_smile:

If didn’t get ask.

1 Like
3

I tried to implement it with DP


[1]. But still it gives TLE, I don't know why it's getting TLE even when I used memoization. Any small hint ?? @paras885  

any help....... ?


  [1]: http://ideone.com/7bjOr8
4

bro plz check ur link it’s URL of this post(recursive :P).

5

got link to code :smiley: here it is if any one comes to this post in future → [tEpmdJ - Online C++ Compiler & Debugging Tool - Ideone.com