SPOJ 61. Brackets Solution

www.spoj.com/problems/BRCKTS/
This is another problem on Segment Trees. Although this is a basic/easy level problem.
In input a string of brackets will be given. The brackets can be open brackets or close brackets. 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 . 

This means that the string can be of form 1.)  ()()   2.) (())   3.)   ((())) ,etc
But not of the form 1.)  )(  2.)  ))((   3.)  ())(()
If the string is of first form answer will be YES else if of second form answer will be NO.

#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 300005

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;
    }
}
int main() {
    int stlen, m, k;
  
    for(int i = 1; i<=10; i++){
        printf("Test %d:\n",i);
        scanf("%d",&stlen);
        scanf("%s", str);
        stlen--;
        build_tree(1,0,stlen);
        scanf("%d",&m);
        while(m--){
            scanf("%d",&k);
            if(k==0){
                if(str[0]==')'){
                    cout<<"NO\n";
                }
                else{
                //    cout<<sum[1].open_brackets<<" "<<sum[1].close_brackets;
                    if(sum[1].close_brackets==0&&sum[1].open_brackets==0){
                        printf("YES\n");
                    }
                    else{
                        printf("NO\n");
                    }
                }
              
            }
            else{
                update_tree(1,0,stlen,k-1);
            }
        }
    }
    return 0;
}

Read More

Unable to scan WhatsApp QR code ?

As you know that WhatsApp has released a web-version for its android, windows and ios WhatsApp app.
It is available on https://web.whatsapp.com/ . 

But some users are not able to scan the QR code. So if you are one of them, you may try some of these steps -

1) Update your WhatsApp to the latest version availabe. This will most probably solve the issue.

2) Hold your phone still for some seconds. This may also be issue. So just hold your phone still for some seconds and let the QR code scanner scan the QR code from the website.

3) Don't scan QR code from a third party app. It will not work. Use only WhatsApp to scan QR code.
Third party apps can also steal your data so beware.

4) If none of the above options worked it may be because your phone is old. Apparently web based version  is only working on new phones. It will not work on devices that have display smaller than 4 inch screen. Like with Sony Xperia Go, Samsung Galaxy Y, Samsung Galaxy Ace, etc. So if your phone's screen is smaller than 4 inch either let WhtasApp solve the issue or buy a new phone :P

Read More