Massive Algorithms: SPOJ BRCKTS

SPOJ BRCKTS - Brackets

https://www.geeksforgeeks.org/range-queries-longest-correct-bracket-subsequence/
Range Queries for Longest Correct Bracket Subsequence

Given a bracket sequence or in other words a string S of length n, consisting of characters ‘(‘ and ‘)’. Find length of the maximum correct bracket subsequence of sequence for a given query range. Note: A correct bracket sequence is the one that have matched bracket pairs or which contains another nested correct bracket sequence. For e.g (), (()), ()() are some correct bracket sequence.

Examples:

Input : S = ())(())(())(
        Start Index of Range = 0, 
        End Index of Range = 11
Output : 10
Explanation:  Longest Correct Bracket Subsequence is ()(())(())

Input : S = ())(())(())(
        Start Index of Range = 1, 
        End Index of Range = 2
Output : 0

Segment Trees can be used to solve this problem efficiently

At each node of the segment tree, we store the following:

1) a - Number of correctly matched pairs of brackets.
2) b - Number of unused open brackets.  
3) c - Number of unused closed brackets.

(unused open bracket – means they can’t be matched with any closing bracket, unused closed bracket – means they can’t be matched with any opening bracket, for e.g S = )( contains an unused open and an unused closed bracket)

For each interval [L, R], we can match X number of unused open brackets ‘(‘ in interval [L, MID] with unused closed brackets ‘)’ in interval [MID + 1, R] where
X = minimum(number of unused ‘(‘ in [L, MID], number of unused ‘)’ in [MID + 1, R])
Hence, X is also the number of correctly matched pairs built by combination.
So, for interval [L, R]

1) Total number of correctly matched pairs becomes the sum of correctly matched pairs in left child and correctly matched pairs in right child and number of combinations of unused ‘(‘ and unused ‘)’ from left and right child respectively.

a[L, R] = a[L, MID] + a[MID + 1, R] + X

2) Total number of unused open brackets becomes the sum of unused open brackets in left child and unused open brackets in right child minus X (minus – because we used X unused ‘(‘ from left child to match with unused ‘) from right child).

a[L, R] = b[L, MID] + b[MID + 1, R] - X

3) Similarly, for ununsed closed brackets, following relation holds.

a[L, R] = c[L, MID] + c[MID + 1, R] - X

where a, b and c are the representations described above for each node to be stored in.

struct Node { 

    int pairs; 

    int open; // unused 

    int closed; // unused 

    Node() 

    { 

        pairs = open = closed = 0; 

    } 

}; 

// A utility function to get the middle index from corner indexes. 

int getMid(int s, int e) { return s + (e - s) / 2; } 

// Returns Parent Node after merging its left and right child 

Node merge(Node leftChild, Node rightChild) 

{ 

    Node parentNode; 

    int minMatched = min(leftChild.open, rightChild.closed); 

    parentNode.pairs = leftChild.pairs + rightChild.pairs + minMatched; 

    parentNode.open = leftChild.open + rightChild.open - minMatched; 

    parentNode.closed = leftChild.closed + rightChild.closed - minMatched; 

    return parentNode; 

} 

// A recursive function that constructs Segment Tree  

// for string[ss..se]. si is index of current node in 

// segment tree st 

void constructSTUtil(char str[], int ss, int se, Node* st, 

                                                 int si) 

{ 

    // If there is one element in string, store it in 

    // current node of segment tree and return 

    if (ss == se) { 

        // since it contains one element, pairs  

        // will be zero 

        st[si].pairs = 0; 

        // check whether that one element is opening  

        // bracket or not 

        st[si].open = (str[ss] == '(' ? 1 : 0); 

        // check whether that one element is closing 

        // bracket or not 

        st[si].closed = (str[ss] == ')' ? 1 : 0); 

        return; 

    } 

    // If there are more than one elements, then recur 

    // for left and right subtrees and store the relation 

    // of values in this node 

    int mid = getMid(ss, se); 

    constructSTUtil(str, ss, mid, st, si * 2 + 1); 

    constructSTUtil(str, mid + 1, se, st, si * 2 + 2); 

    // Merge left and right child into the Parent Node 

    st[si] = merge(st[si * 2 + 1], st[si * 2 + 2]); 

} 

/* Function to construct segment tree from given 

   string. This function allocates memory for segment  

   tree and calls constructSTUtil() to fill the  

   allocated memory */

Node* constructST(char str[], int n) 

{ 

    // Allocate memory for segment tree 

    // Height of segment tree 

    int x = (int)(ceil(log2(n))); 

    // Maximum size of segment tree 

    int max_size = 2 * (int)pow(2, x) - 1; 

    // Declaring array of structure Allocate memory 

    Node* st = new Node[max_size]; 

    // Fill the allocated memory st 

    constructSTUtil(str, 0, n - 1, st, 0); 

    // Return the constructed segment tree 

    return st; 

} 

/* A Recursive function to get the desired  

   Maximum Sum Sub-Array, 

The following are parameters of the function- 

st     --> Pointer to segment tree  

si --> Index of the segment tree Node  

ss & se  --> Starting and ending indexes of the  

             segment represented by 

                 current Node, i.e., tree[index] 

qs & qe  --> Starting and ending indexes of query range */

Node queryUtil(Node* st, int ss, int se, int qs, 

               int qe, int si) 

{ 

    // No overlap 

    if (ss > qe || se < qs) { 

        // returns a Node for out of bounds condition 

        Node nullNode; 

        return nullNode; 

    } 

    // Complete overlap 

    if (ss >= qs && se <= qe) { 

        return st[si]; 

    } 

    // Partial Overlap Merge results of Left 

    // and Right subtrees 

    int mid = getMid(ss, se); 

    Node left = queryUtil(st, ss, mid, qs, qe, si * 2 + 1); 

    Node right = queryUtil(st, mid + 1, se, qs, qe, si * 2 + 2); 

    // merge left and right subtree query results 

    Node res = merge(left, right); 

    return res; 

} 

/* Returns the maximum length correct bracket  

   subsequencebetween start and end 

   It mainly uses queryUtil(). */

int query(Node* st, int qs, int qe, int n) 

{ 

    Node res = queryUtil(st, 0, n - 1, qs, qe, 0); 

    // since we are storing numbers pairs 

    // and have to return maximum length, hence 

    // multiply no of pairs by 2 

    return 2 * res.pairs; 

}

https://www.geeksforgeeks.org/range-queries-longest-correct-bracket-subsequence-set-2/

Idea is based on the Post length of the longest valid balanced substring If we marked indexes of all Balanced parentheses/bracket in a temporary array (here we named it BCP[], BOP[] ) then we answer each query in O(1) time.
Algorithm :

stack is used to get the index of blanace Breacket
Travese a string from 0 ..to n
IF we seen a closing bracket, 
      ( i.e., str[i] = ')' && stack is not empty )
 
Then mark both "open & close" bracket indexs as 1 .
BCP[i] = 1; 
BOP[stk.top()] = 1;

And At lest stored cumulative sum of BCP[] & BOP[] 
Run a loop from 1 to n
BOP[i] +=BOP[i-1], BCP[i] +=BCP[i-1]

Now you can answer each query in O(1) time

(BCP[e] - (BOP[s-1] - BCP[s-1] ) )*2;

BOP[] stands for "Balanced open parentheses"  

BCP[] stands for "Balanced close parentheses" 

*/

// function for precomputation  

void constructBlanceArray( int BOP[] , int BCP[] ,  

                           char* str , int n ) 

{ 

    // Create a stack and push -1 as initial index to it. 

    stack<int> stk; 

    // Initialize result 

    int result = 0; 

    // Traverse all characters of given string 

    for (int i=0; i<n; i++) 

    { 

        // If opening bracket, push index of it 

        if (str[i] == '(') 

        stk.push(i); 

        else // If closing bracket, i.e.,str[i] = ')' 

        { 

            // If closing bracket, i.e.,str[i] = ')'  

            // && stack is not empty then mark both  

            // "open & close" bracket indexs as 1 . 

            // Pop the previous opening bracket's index 

            if (!stk.empty()) 

            { 

                BCP[i] = 1;  

                BOP[stk.top()] = 1; 

                stk.pop(); 

            } 

            // If stack is empty.  

            else

                BCP[i] = 0; 

        } 

    } 

    for( int i = 1 ; i < n; i++ ) 

    { 

        BCP[i] += BCP[i-1]; 

        BOP[i] += BOP[i-1]; 

    }  

} 

// Function return output of each query in O(1) 

int query( int BOP[] , int BCP[] ,  

           int s , int e ) 

{ 

    if( s != 0 )  

        return (BCP[e] - (BOP[s-1] - BCP[s-1] ) )*2; 

    else        

    return BCP[e]*2; 

}

https://www.spoj.com/problems/BRCKTS/

We will call a bracket word any word constructed out of two sorts of characters: the opening bracket "(" and the closing bracket ")". Among these words we will distinguish correct bracket expressions. These are such bracket words in which the brackets can be matched into pairs such that

every pair consists of an opening bracket and a closing bracket appearing further in the bracket word
for every pair the part of the word between the brackets of this pair has equal number of opening and closing brackets

On a bracket word one can do the following operations:

replacement -- changes the i-th bracket into the opposite one
check -- if the word is a correct bracket expression

Task

Write a program which

reads (from standard input) the bracket word and the sequence of operations performed,
for every check operation determines if the current bracket word is a correct bracket expression,
writes out the outcome (to standard output).

Input

Ten test cases (given one under another, you have to process all!). Each of the test cases is a series of lines. The first line of a test consists of a single number n (1<=n<=30000) denoting the length of the bracket word. The second line consists of n brackets, not separated by any spaces. The third line consists of a single number m -- the number of operations. Each of the following m lines carries a number k denoting the operation performed. k=0 denotes the check operation, k>0 denotes replacement of k-th bracket by the opposite.

Output

For every test case your program should print a line:
Test i:
where i is replaced by the number of the test and in the following lines, for every check operation in the i-th test your program should print a line with the word YES, if the current bracket word is a correct bracket expression, and a line with a word NO otherwise. (There should be as many lines as check operations in the test.)

Example

Input:
4
()((
4
4
0
2
0
[and 9 test cases more]
Output:
Test 1:
YES
NO
[and 9 test cases more]

http://codechrist.blogspot.com/2015/01/spoj-61-brackets-solution.html
struct DATA{
    int open_brackets;
    int close_brackets;
    DATA(){
        open_brackets=close_brackets = 0;
    }
};

DATA sum[4*MAX];
char str[MAX];

void build_tree(int node, int a, int b){
    if(a>b){
        return;
    }
    if(a==b){
        if(str[a]=='('){
            sum[node].open_brackets = 1;
            sum[node].close_brackets = 0;
        }
        else{
            sum[node].open_brackets = 0;
            sum[node].close_brackets = 1;
        }
    //    cout<<" sum["<<node<<"] "<<str[node]<<" "<<sum[node].open_brackets<<" "<<sum[node].close_brackets<<" ";
        return;
    }

    build_tree(2*node, a, (a+b)/2);
    build_tree((2*node)+1,((a+b)/2)+1, b);

    int ol = sum[2*node].open_brackets;
    int cl = sum[2*node].close_brackets;

    int orr = sum[2*node+1].open_brackets;
    int crr = sum[2*node+1].close_brackets;

    if(ol>=crr){
        sum[node].open_brackets = ol + orr - crr;
    }
    else {
        sum[node].open_brackets = orr;
    }
    if(ol<=crr){
        sum[node].close_brackets = cl+crr-ol;
    }
    else{
        sum[node].close_brackets = cl;
    }
//    cout<<" sum["<<node<<"] "<<str[node]<<" "<<sum[node].open_brackets<<" "<<sum[node].close_brackets<<" ";
}

void update_tree(int node, int a, int b, int val){
    if(a>b){
        return;
    }

    if(a==b){
        if(str[val]=='('){
            sum[node].open_brackets--;
            sum[node].close_brackets++;
            str[val] = ')';
        }
        else{
            sum[node].open_brackets++;
            sum[node].close_brackets--;
            str[val] = '(';
        }
        //cout<<str<<endl;
        return;
    }
    if(val <=(a+b)/2){
        update_tree(2*node, a, (a+b)/2,val);
     }
     else{
        update_tree((2*node)+1,((a+b)/2)+1, b,val);
    }

    int ol = sum[2*node].open_brackets;
    int cl = sum[2*node].close_brackets;
    int orr = sum[2*node+1].open_brackets;
    int crr = sum[2*node+1].close_brackets;

    if(ol>=crr){
        sum[node].open_brackets = ol + orr - crr;
    }
    else {
        sum[node].open_brackets = orr;
    }
    if(ol<=crr){
        sum[node].close_brackets = cl+crr-ol;
    }
    else{
        sum[node].close_brackets = cl;
    }
}

https://kartikkukreja.wordpress.com/2014/11/09/a-simple-approach-to-segment-trees/

The third problem: BRCKTS, we’ll look at is very different from the first two but the differences are only superficial since we’ll be able to solve it using the same structure. This problem gives a string containing parenthesis (open and closed), requires making updates to individual parenthesis (changing an open parenthesis to closed or vice versa), and checking if the whole string represents a correct parenthesization.
As it turns out, we need only 2 things in each segment tree node:

The number of unmatched open parenthesis in this range
The number of unmatched closed parenthesis in this range

SPOJ BRCKTS - Brackets

Task

Input

Output

Example

Labels

Popular Posts