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;
}

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;
}

SPOJ - ETF - Euler Totient Function


Problem Link: https://www.spoj.com/problems/ETF/en/



Code: 

#include <bits/stdc++.h>

using namespace std;

#define mx 1000002
int phi[mx];

int main()
{
    memset(phi,0,sizeof(phi));
    phi[1]=1;
    for(int i=2;i<=mx;i++)
    {

        if(phi[i]==0)
        {
            phi[i]=i-1;
            for(int j=i<<1;j<=mx;j+=i)
            {
                if(!phi[j])
                {
                    phi[j]=j;
                }
                phi[j]=(phi[j]/i)*(i-1);
                //cout<<phi[j]<<endl;
            }
        }
    }
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        cout<<phi[n]<<endl;
    }
    return 0;

}

SPOJ - DIVSUM2 - Divisor Summation (Hard)


Problem Link: https://www.spoj.com/problems/DIVSUM2/en/


Code: 

#include <bits/stdc++.h>

using namespace std;

#define mx 100000008
#define ll long long

bitset <mx> b;
vector <ll> v;
void seive()
{
    b.set();
    b[0]=b[1]=false;
    for(ll i=0;i<mx;i++)
    {
        if(b[i])
        {
            v.push_back(i);
            for(ll j=i*i;j<=mx;j+=i)
                b[j]=false;
        }
    }
}


long long power(long long a, long long b)
{
    if(b==0)
        return 1;
    if(b==1)
        return a;
    long long res=1;
    while(b--)
        res*=a;
    return res;
}
int main()
{
    int t;
    seive();
    cin>>t;
    while(t--)
    {
        long long n,res=1,f;
        cin>>n;
        f=n;
        for(ll i=0;i<v.size()&&(v[i]*v[i])<=n;i++)
        {
            if(n%v[i]==0)
            {
                int cnt=0;
                while(n%v[i]==0)
                {
                    cnt++;
                    n/=v[i];
                }
                cnt++;
                res*=(((power(v[i],cnt))-1)/(v[i]-1));
            }
        }
        if(n!=1)
            res*=(1+n);
        cout<<res-f<<endl;
    }
    return 0;

}

SPOJ - DIVSUM - Divisor Summation


Problem Link: https://www.spoj.com/problems/DIVSUM/en/

Code: 

#include <bits/stdc++.h>

using namespace std;

#define mx 500002

char a[mx];
vector <int> v;

void sieve()
{
    memset(a,0,sizeof(a));
    for(int i=4;i<=mx;i+=2)
        a[i]=1;
    for(int i=3;i<=sqrt(mx);i+=2)
    {
        if(a[i]==0)
        {
             for(int j=i*i;j<=mx;j+=i)
                a[j]=1;
        }

    }
    v.push_back(2);
    for(int i=3;i<mx;i+=2)
    {
        if(a[i]==0)
            v.push_back(i);
    }
}

int main()
{
    int t;
    sieve();
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int f=n;
        long long res=1;
        for(int i=0;v[i]<=sqrt(n);i++)
        {

            if(n%v[i]==0)
            {
                long long p=1,temp=1;
                while(n%v[i]==0)
                {
                    n/=v[i];
                    p*=v[i];
                    temp+=p;
                }
                res*=temp;
            }
        }
        if(n!=1)
        {
            res*=(1+n);
        }
        res-=f;
        cout<<res<<endl;
    }
    return 0;

}

SPOJ - NDIV - n-divisors

Idea: Find Out the number of divisors(NOD) using prime factorization.Use Seive for finding prime number upto sqrt(10^9).

Code First Then See Solution

Code: 

#include <bits/stdc++.h>

using namespace std;

#define mx 3200

int a[mx+10];
vector <int> v;

void seive()
{
   memset(a,0,sizeof(a));
   for(int i=2;i<=sqrt(mx);i++)
   {
       if(a[i]==0)
       {
           for(int j=i*i;j<=mx;j+=i)
            a[j]=1;
       }
   }
   v.push_back(2);
   for(int i=3;i<=mx;i+=2)
   {
       if(a[i]==0)
        v.push_back(i);
   }
}

int main()
{
    int a,b,n;
    seive();
    cin>>a>>b>>n;
    int res=0,sum;
    for(int i=a;i<=b;i++)
    {
        int temp=i;
        sum=1;
        for(int j=0;j<v.size()&&v[j]<=sqrt(temp);j++)
        {
            if(temp%v[j]==0)
            {
                int cnt=0;
                while(temp%v[j]==0)
                {
                    cnt++;
                    temp/=v[j];
                }
                sum*=(cnt+1);
            }
        }
        if(temp!=1)
        {
            sum*=2;
        }
        if(sum==n)
            res++;
    }
    cout<<res<<endl;
    return 0;

}

Spoj - FACT0- Integer Factorization

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

Idea : Simple Prime factorization problem.Do not use Sieve or you will get TLE.

Code First Then See Solution

Code:

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int main()

{

    ll n;

    while(cin>>n)

    {

        if(n==0)

            break;

        ll cnt=0;

        while(n%2==0)

        {

            cnt++;

            n/=2;

        }

        if(cnt>0)

            cout<<"2"<<"^"<<cnt<<" ";

        ll x=3;

        while(x*x<=n)

        {

            cnt=0;

            while(n%x==0)

            {

                cnt++;

                n/=x;

            }

            if(cnt>0)

                cout<<x<<"^"<<cnt<<" ";

            x+=2;

        }

        if(n!=1)

            cout<<n<<"^"<<1<<endl;

        else

            cout<<endl;

    }

    return 0;

}

Spoj -TDPRIMES - Printing some primes

Idea: Use Bitwise Seive.

Code First Then See Solution

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

using namespace std;
#define mx 100000000

int a[(mx>>5)+2];

bool status(int n,int pos)
{
    return bool(n&1<<pos);
}

int sett(int n,int pos)
{
    return n=n|(1<<pos);
}

int main()
{
    int n= 100000000;
    vector <int> v;
    for(int i=3;i<=sqrt(n);i+=2)
    {
        if(status(a[i>>5],i&31)==false)
        {
            for(int j=i*i;j<=n;j+=i)
            {
                a[j>>5]=sett(a[j>>5],j&31);
            }
        }
    }
    v.push_back(2);
    for(int i=3;i<=n;i+=2)
    {
        if(status(a[i>>5],i&31)==false)
            v.push_back(i);
    }
    for(int i=0;i<=v.size();i+=100)
        cout<<v[i]<<endl;
    return 0;
}

Spoj - LCMSUM - LCM Sum

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

Idea : 

Code First Then See Solution

Code: 

#include <bits/stdc++.h>
using namespace std;

#define mx 1000008
#define ll long long

long long  a[mx+10];
long long res[mx+10];


void phi()
{
   memset(a,0,sizeof(a));
   a[1]=1;
   for(int i=2;i<=mx;i++)
   {
       if(a[i]==0)
       {
           a[i]=i-1;
           for(int j=i<<1;j<=mx;j+=i)
           {
               if(a[j]==0)
               {
                   a[j]=j;
               }
               a[j]=a[j]/i;
               a[j]*=(i-1);
           }
       }
   }
   //memset(res,0,sizeof(res));
   for(ll i=1;i<=mx;i++)
   {
       for(ll j=i;j<=mx;j+=i)
       {
           res[j]+=(i*a[i]);
       }
   }
}



int main()
{
    int t,f=0;
    //seive();
    phi();
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        long long sum=0;
        sum=res[n];
        sum++;
        sum*=n;
        sum/=2;
        cout<<sum<<endl;
    }
    return 0;
}

Spoj-PSYCHON-Psycho

 Spoj - PSYCHON - Psycho

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


Explanation : First prime factorize the number and then check  each power of prime.Find "is even power is strictly greater than odd power".It can be done without prime factorization.Think about it!


Code First Then See Solution

Code :


#include <bits/stdc++.h>

using namespace std;

#define mx 10000040

bool a[mx];

vector <int> v;

void sieve()
{
    memset(a,true,sizeof(a));
    for(int i=4;i<=mx;i+=2)
        a[i]=false;
    for(int i=3;i<=sqrt(mx);i+=2)
    {
        if(a[i]==true)
        {
            for(int j=i*i;j<=mx;j+=i)
            {
               a[j]=false;
            }
        }
    }
    v.push_back(2);
    for(int i=3;i<=mx;i+=2)
    {
        if(a[i]==true)
            v.push_back(i);
    }
}

int main()
{
    int t;
    sieve();
    //cin>>t;
    scanf("%d",&t);
    while(t--)
    {
        int n,even=0,odd=0;
        //cin>>n;
        scanf("%d",&n);
        //if(n==0||n==1)
           // printf("Ordinary Number\n");
        for(int i=0;v[i]<=sqrt(n);i++)
        {
            if(n%v[i]==0)
            {
                int coun=0;
                while(n%v[i]==0)
                {
                    n/=v[i];
                    coun++;
                }
                if(coun%2==0)
                   even++;
                else
                    odd++;
            }
        }
        if(n>1)
            odd+=1;
        if(even>odd)
            printf("Psycho Number\n");
        else
            printf("Ordinary Number\n");
    }
    return 0;
}