JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums Tutorial Discussions Binary Indexed Trees Re: SPOJ:BRCKTS Revision History (2 edits)
Re: SPOJ:BRCKTS (response to post by NilayVaish)
I did this with a special kind of tree, described below. I don't know if it can be called Binary Indexed Tree, as I don't know what a BIT is. But its not a segment/interval tree.

Lets say you have an expression with N characters. Then make a tree with N nodes at the bottommost level. Each node represents a character. Then the level above it will have ceil(N/2) nodes. Each node in this level represents the concatenation of two nodes of the level below. Keep doing it. The topmost level will have 1 node that represents the whole string given to you.
             (())()((                   - Level 4 (1 node)
      (())              ()((            - Level 3 (2 nodes)
  ((       ))       ()       ((         - Level 2 (4 nodes)
(    (   )    )   (    )   (    (       - Level 1 (8 nodes)

Now each node stores two values, the no. of opening braces required to its left and the no. of closing braces required to its right to make the expression represented by it a valid expression. Its trivial for the bottommost nodes. Its (0,1) for and opening brace and (1,0) for a closing brace. Now figure out how will you use this values to find values at the levels above it! And then figure out how you can update this tree in O(log n). Check operation is trivial: The string is valid expression if the value at root node is (0,0).
Re: SPOJ:BRCKTS (response to post by NilayVaish)
I did this with a special kind of tree, described below. I don't know if it can be called Binary Indexed Tree, as I don't know what a BIT is. But its not a segment/interval tree.

Lets say you have an expression with N characters. Then make a tree with N nodes at the bottommost level. Each node represents a character. Then the level above it will have ceil(N/2) nodes. Each node in this level represents the concatenation of two nodes of the level below. Keep doing it. The topmost level will have 1 node that represents the whole string given to you.
             (())()((                   - Level 4 (1 node)
      (())              ()((            - Level 3 (2 nodes)
  ((       ))       ()       ((         - Level 2 (4 nodes)
(    (   )    )   (    )   (    (       - Level 1 (8 nodes)

Now each node stores two values, the no. of opening braces required to its left and the no. of closing braces required to its right to make the expression represented by it a valid expression. Its trivial for the bottommost nodes. Its (0,1) for and opening brace and (1,0) for a closing brace. Now figure out how will you use this values to find values at the levels above it! And then figure out how you can update this tree in O(log n).
Re: SPOJ:BRCKTS (response to post by NilayVaish)
I did this with a special kind of tree, described below. I don't know if it can be called Binary Indexed Tree, as I don't know what a BIT is. But its not a segment/interval tree.

Lets say you have an expression with N characters. Then make a tree with N nodes at the bottommost level. Each node represents a character. Then the level above it will have ceil(N/2) nodes. Each node in this level represents the concatenation of two nodes of the level below. Keep doing it. The topmost level will have 1 node that represents the whole string given to you.
             (())()((                   - Level 4 (1 node)
      (())              ()((            - Level 3 (2 nodes)
  ((       ))       ()       ((         - Level 2 (4 nodes)
(    (   )    )   (    )   (    (       - Level 1 (8 nodes)

Now each node stores two values, the no. of opening braces required to its left and the no. of closing braces required to its right to make the expression represented by it a valid expression. Its trivial for the bottommost nodes. Its (0,1) for and opening brace and (1,0) for a closing brace. Now figure out how will use this values to find values at the levels above it! And then figure out how you can update this tree in O(log n).