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;
    } 
}
The third problemBRCKTS, 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:
  1. The number of unmatched open parenthesis in this range
  2. The number of unmatched closed parenthesis in this range


Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts