SpojOJ - BRCKTS - Brackets

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

IDEA: This is a simple segment tree problem. All we have to do is find out how to store value in segment tree. As, there are two  types of brackets, we can store them by denoting 1 and -1 respectively. When traversing from leaf node to upper node all we need to calculate sum and left minimum value to ensure this sequence is balanced or not.

CODE: 

#include <bits/stdc++.h>

using namespace std;

int a[30022];
struct node{
    int sum,left;
};
node st[200022];

node nnode(int val)
{
    node x;
    x.sum=val;
    x.left=val;
    //cout<<x.sum<<" "<<x.left<<endl;
    return x;
}

node mergest(node x,node y)
{
    node z;
    z.sum= x.sum+y.sum;
    z.left= min(x.left,x.sum+y.left);
    //cout<<z.sum<<" "<<z.left<<endl;
    return z;
}

void update(int s,int e,int n,int k)
{
    if(s==e)
    {
        if(a[s]==1)
            a[s]=-1;
        else
            a[s]=1;
        st[n]=nnode(a[s]);
        return;
    }
    int mid=(s+e)/2;
    if(k<=mid)
        update(s,mid,n*2,k);
    else
        update(mid+1,e,n*2+1,k);
    st[n]=mergest(st[n*2],st[n*2+1]);
}

void build(int s,int e,int n)
{
    if(s==e)
    {
       st[n]=nnode(a[s]);
       return ;
    }
    int mid=(s+e)/2;
    build(s,mid,n*2);
    build(mid+1,e,n*2+1);
    st[n]=mergest(st[n*2],st[n*2+1]);
}
int main()
{
    int t=10;
    while(t--)
    {
        cout<<"Test "<<10-t<<":"<<endl;
        int n,k;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            char x;
            cin>>x;
            if(x=='(')
                a[i]=1;
            else
                a[i]=-1;
        }
        build(1,n,1);
        //int k;
        cin>>k;
        for(int i=0;i<k;i++)
        {
            int f;
            cin>>f;
            if(f==0)
            {
                if(st[1].sum==0&&st[1].left==0)
                    cout<<"YES"<<endl;
                else
                    cout<<"NO"<<endl;
            }
            else
            {
                update(1,n,1,f);
            }
        }
    }
    return 0;
}

SpojOJ - GSS1 - Can you answer queris 1

Problem link : https://www.spoj.com/problems/GSS1/

IDEA: To solve this problem first we need to think where we can we get the maximum value in a range.Segment tree makes the problem easier to solve. But storing values in node is the tricky tasks here. Here each node must store more than one value. Maximum value in a range can be in left side or in right side or in both side. So, we will store four informtion in a node. They are total, left sum, right sum, best sum.Best value among these four value will be the answer.

Code:

#include <bits/stdc++.h>

#define min -9999999
#define mx1 (1<<16)
#define mx2 mx1<<2
#define endl '\n'

using namespace std;


struct val
{
    long total,lsum,rsum,best;
};

val *segment = new val[mx2];
int *a = new int[mx1];

int maxof(int f, int g)
{
    if(f>=g)
        return f;
    else
        return g;
}

void simp(int pos)
{
    segment[pos].total = segment[2*pos+1].total+segment[2*pos+2].total;
    segment[pos].lsum = maxof(segment[2*pos+1].lsum,segment[2*pos+1].total+segment[2*pos+2].lsum);
    segment[pos].rsum = maxof(segment[2*pos+2].rsum,segment[2*pos+2].total+segment[2*pos+1].rsum);
    segment[pos].best = maxof(maxof(segment[2*pos+1].best,segment[2*pos+2].best),segment[2*pos+1].rsum+segment[2*pos+2].lsum);
}

void built(int lo,int hi,int  pos)
{
    if(lo==hi)
    {
        segment[pos].total= a[lo];
        segment[pos].lsum= a[lo];
        segment[pos].rsum= a[lo];
        segment[pos].best= a[lo];
        return;
    }
    int mid= lo+(hi-lo)/2;
    built(lo,mid,2*pos+1);
    built(mid+1,hi,2*pos+2);
    simp(pos);
}

val query(int qlo,int qhi,int lo,int hi,int pos)
{
    if(qlo>hi||qhi<lo)
    {
         return (val)
         {
             0,
             min,
             min,
             min
         };
    }
    if(qlo<=lo&&qhi>=hi)
    {
        return segment[pos];
    }
    int mid = lo+(hi-lo)/2;
    val left=query(qlo,qhi,lo,mid,2*pos+1);
    val right = query(qlo,qhi,mid+1,hi,2*pos+2);
    val pr;
    pr.total = left.total+right.total;
    pr.lsum= maxof(left.lsum,left.total+right.lsum);
    pr.rsum= maxof(right.rsum,right.total+left.rsum);
    pr.best= maxof(maxof(left.best,right.best),left.rsum+right.lsum);
    return pr;
}




int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    built(0,n-1,0);
    int q;
    cin>>q;
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        x--,y--;
        val res= query(x,y,0,n-1,0);
        int ans=maxof(maxof(res.best,res.total),maxof(res.lsum,res.rsum));
        cout<<ans<<endl;
    }
    return 0;
}

SPOJ - RMQSQ - Range Minimum Query

Problem Link: https://www.spoj.com/problems/RMQSQ/

IDEA: Use sparse table to do this problem. Simple sparse table implementation.


CODE:

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define sf scanf(a)

int st[100008][27];

void precompute(int a[],int n, int k)
{
    for(int i=0;i<n;i++)
    {
        st[i][0]=a[i];
    }

    for(int j=1;j<=k;j++)
    {
        for(int i=0;i+(1<<j)<=n;i++)
        {
            st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
        }
    }
}


int main()
{
    int n;
    cin>>n;
    int a[n+5];
    for(int i=0;i<n;i++)
        cin>>a[i];
    int log[n+5];
    log[1]=0;
    for(int i=2;i<=n;i++)
        log[i]=log[i/2]+1;
    int k=log[n]+1;
    precompute(a,n,k);
    int q;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        int l,r;
        ll sum=0;
        cin>>l>>r;
        int x=log[r-l+1];
        sum=min(st[l][x],st[r-(1<<(x))+1][x]);
        cout<<sum<<endl;
    }
    return 0;
}

LightOJ - 1112 - Curious Robin Hood

Problem link: http://www.lightoj.com/volume_showproblem.php?problem=1112

IDEA: This problem can be solved using BIT. There are three type of query in this problem. First one is point update, second one is also point update, third one is range query. BIT has two functions. One is point update and another is range query.
Before using these functions we need to initialize the tree with zero value.Then update with the array value.As,BIT tree works when its initial values are zero.

CODE: 

#include <bits/stdc++.h>

using namespace std;

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

int tree[100008];
int a[100008];



void update(int n,int idx,int val)
{
    idx++;
    while(idx<=n)
    {
        tree[idx]+=val;
        idx+=idx & (-idx);
    }
}

int query(int idx)
{
    int sum=0;
    idx++;
    while(idx>0)
    {
        sum+=tree[idx];
        idx-=idx & (-idx);
    }
    return sum;
}

void BIT(int n)
{
    for(int i=0;i<n;i++)
    {
        update(n,i,a[i]);
    }
}

int main()
{
    int t,z=0;
    sf(t);
    while(t--)
    {
        z++;
        int n,q;
        //cin>>n>>q;
        sf(n);
        sf(q);
        ms(tree,0);
        for(int i=0;i<n;i++)
            sf(a[i]);
        BIT(n);
        LINE_PRINT_CASE;
        loop(i,q)
          {
              /*for(int i=1;i<=n;i++)
              cout<<tree[i]<<" ";
              cout<<endl;
              */
              int x,y,z;
              sf(x);
              if(x==1)
              {
                 sf(y);
                 int ans=query(y);
                 int f= query(y-1);
                 ans=ans-f;
                 int l=((-1)*ans);
                 update(n,y,l);
                 printf("%d\n",ans);
              }
              else if(x==2)
              {
                  sf(y);
                  sf(z);
                  update(n,y,z);
              }
              else
                {
                   sf(y);
                   sf(z);
                   int ans=query(z);
                   ans-=query(y-1);
                   printf("%d\n",ans);
                }
          }
    }
    return 0;
}

LightOJ - 1424 - New Land

Problem Link: http://lightoj.com/volume_showproblem.php?problem=1424

IDEA: Its like e histogram problem.We just need to make it as a histogram by storing value in a array.


CODE: 

#include <bits/stdc++.h>

using namespace std;

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

int histogram(int a[],int m)
{
    int i=0;
    stack <int> st;
    int mx=0;
    while(i<m)
    {
        if(st.empty()||a[st.top()]<=a[i])
        {
            st.push(i++);
        }
        else
        {
            int top= st.top();
            st.pop();
            int ans= a[top]*(st.empty() ? i: i-st.top()-1);
            mx=max(ans,mx);
        }
    }
    while(!st.empty())
    {
        int top = st.top();
        st.pop();
        int ans= a[top]*(st.empty() ? i : i-st.top()-1);
        mx= max(ans,mx);
    }
    return mx;
}

int main()
{
    int t,z=0;
    cin>>t;
    while(t--)
    {
        z++;
        int n,m;
        cin>>n>>m;
        char ar[n+2][m+2];
        for(int i=0;i<n;i++)
        {
            cin>>ar[i];
        }
        int b[m+4]={0};
        int mx=0;
        for(int i=0;i<n;i++)
        {
            int k=0;
            for(int j=0;j<m;j++)
            {
                b[k]=(ar[i][j]=='1')? 0 : b[k]+1;
                k++;
            }
        int ans = histogram(b,m);
        mx=max(ans,mx);
        }
     PRINT_CASE;
     cout<<mx<<endl;
    }

    return 0;
}

SPOJ -  HISTOGRA - Largest Rectangle in a Histogram

Problem link: https://www.spoj.com/problems/HISTOGRA/

IDEA :  For a particular point of the array we need find how much distance to its right and to its left it can take. Actually, we need to find minimum value to its right. To find this we can use stack.if the value of a particular index is less than the previous one which is in stack we need to pop the previous element from the stack and find its total rectangular value.



CODE : 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

int main()
{
    /*int t,x=0;
    cin>>t;
    */
    while(true)
    {
        ll n;
        cin>>n;
        if(n==0)
            return 0;
        ll a[n+5];
        for(int i=0;i<n;i++)
            cin>>a[i];
        stack <ll> st;
        ll i=0;
        long long mx=0;
        while(i<n)
        {
            if(st.empty()||a[st.top()]<=a[i])
            {
                st.push(i);
                i++;
            }
            else
            {
                ll top =st.top();
                st.pop();
                long long ans= a[top]*(st.empty()? i: i-st.top()-1);
                mx=max(ans,mx);
            }
        }
        while(!st.empty())
        {
            ll top=st.top();
            st.pop();
            long long ans=a[top]*(st.empty() ? i: i-st.top()-1);
            mx=max(ans,mx);
        }
     //cout<<"Case "<<x<<": "<<mx<<endl;
     cout<<mx<<endl;
    }
    return 0;
}

LightOJ - 1083 - Histogram

Problem Link: http://lightoj.com/volume_showproblem.php?problem=1083

Idea: For a particular point of the array we need find how much distance to its right and to its left it can take. Actually, we need to find minimum value to its right. To find this we can use stack.if the value of a particular index is less than the previous one which is in stack we need to pop the previous element from the stack and find its total rectangular value.

CODE :

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t,x=0;
    cin>>t;
    while(t--)
    {
        x++;
        int n;
        cin>>n;
        int a[n+5];
        for(int i=0;i<n;i++)
            cin>>a[i];
        stack <int> st;
        int i=0;
        long long mx=0;
        while(i<n)
        {
            if(st.empty()||a[st.top()]<=a[i])
            {
                st.push(i);
                i++;
            }
            else
            {
                int top =st.top();
                st.pop();
                long long ans= a[top]*(st.empty()? i: i-st.top()-1);
                mx=max(ans,mx);
            }
        }
        while(!st.empty())
        {
            int top=st.top();
            st.pop();
            long long ans=a[top]*(st.empty() ? i: i-st.top()-1);
            mx=max(ans,mx);
        }
     cout<<"Case "<<x<<": "<<mx<<endl;
     //cout<<mx<<endl;
    }
    return 0;
}