Code Library

1.Miscellaneous Code
Contest Template
Simple Pointer Code
First Input With Buffer
Add Two Big Number
Upper Bound & Lower Bound
BigInteger Template
Multiplication of a large number with a integer
Backtracking (Permutation Generator)
Checking Palindromes of All Sub-string
2.Number Theory
Bigmod
Bigmod(Bitwise)
Prime Generation
Sieve-1(for prime check)
Sieve-2(for distinct prime factor)
Sieve-3(for sum of distinct prime factor)
Sieve-4(for number of divisor-1)
Sieve-5(for number of divisor-2)
Sieve-6(for sum of divisor)
Extended Euclid

3.Graph Theory
Depth-First Search(DFS)
Dijkstra
Dijkstra With Printing Path
Minimum Spanning Tree(MST-Prims)
Minimum Spanning Tree(MST-Kruskal)
Topological Sort(In-degree Solution)
Topological Sort(DFS Solution)
Strongly Connected Components(SCC)
Articulation Point
Articulation Bridge
Lowest Common Ancestor

4.Sorting
Bubble Sort
Insertion Sort
Selection Sort
Merge Sort
Quick Sort

5.Data Structures
Binary Search
Trie-1
Trie-2
Histogram With Stack
Segment Tree-1
Segment Tree-2
Segment Tree-3
Segment Tree-4(With Lazy)
Segment Tree-5(With Lazy)
Segment Tree-6(With Lazy)
Binary Indexed Tree
Union-Find(Cycle Checking)
KMP
Suffix Array

6.Dynamic Programming
Coin Change

7.Matrix
Matrix Multiplication
Matrix Exponentiation-1
Matrix Exponentiation-2
Matrix Exponentiation-3
Matrix Exponentiation-4(with precalculate)
8.Geometry
Segment Intersection
Point Existence Checking in a Polygon
Determining Is a point is Inside or Outside a Convex Polygon
Area of Polygon

9. Combinatorics & Counting
NCR(Binomial Cofficient-01)
NCR(Binomial Cofficient-02)

Contest Template[Index ]

/**********************************************************************
   *                   Solved By : Md Abdul Alim                      *
   *                   My Team Name: BUBT ILLUSION                    *
   *                   My Blog: codesea.wordpress.com                 *
   *                   Facebook: https://www.facebook.com/alim14      *
   *                   Bangladesh University of Business & Technology *
   *********************************************************************/
#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<bitset>
#include<list>
#include<iomanip>
#include<string>
#include<climits>
#include <sstream>
#include <fstream>
#include<cctype>
#include<time.h>
#include<assert.h>
#include<set>
#include <numeric>
#include <functional>
#include<cstring>
#include<cmath>
#include<iterator>
#include <memory.h>
#include<utility>
#include <ctime>
#include<algorithm>
#define read freopen("input.txt","r",stdin)
#define write freopen("output.txt","w",stdout)
#define all(v) v.begin(),v.end()
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define maxall(v) *max_element(all(v))
#define minall(v) *min_element(all(v))
#define pb push_back
#define mk make_pair
#define SORT(v) sort(all(v))
#define UN(v) SORT(v), (v).erase(unique(all(v)),v.end())
#define common(a,b) SORT(a), SORT(b), a.erase(set_intersection(all(a),all(b),a.begin()),a.end())
#define uncommon(a,b) SORT(a), SORT(b), a.erase(set_symmetric_difference(all(a),all(b),a.begin()),a.end())
#define FILL(a,d) memset(a,d,sizeof(a))
#define LL long long
#define ULL unsigned long long
#define PI 2*acos(0.0)
#define pi pair<int,int>
#define E 2.7182818284
#define EPS 1e-9
using namespace std;
inline void S( int &n )//fast input function
{
    n=0;
    int ch=getchar();
    int sign=1;
    while( ch < '0' || ch > '9' )
    {
        if(ch=='-')sign=-1;
        ch=getchar();
    }

    while(  ch >= '0' && ch <= '9' )
        n = (n<<3)+(n<<1) + ch-'0', ch=getchar();
    n=n*sign;
}
//int rrr[]={1,0,-1,0};int ccc[]={0,1,0,-1}; //4 Direction
//int rrr[]={1,1,0,-1,-1,-1,0,1};int ccc[]={0,1,1,1,0,-1,-1,-1};//8 direction
//int rrr[]={2,1,-1,-2,-2,-1,1,2};int ccc[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
//int rrr[]={2,1,-1,-2,-1,1};int ccc[]={0,1,1,0,-1,-1}; //Hexagonal Direction
//int month[]={31,28,31,30,31,30,31,31,30,31,30,31}; //month

int binary_to_decimal(string s)   //ex:000101
{
    int i,j,n=s.size();
    int sum=0;
    for(i=n-1,j=0;i>=0;i--,j++)
    {
        if(s[i]=='1')
            sum=sum+(1<<j);
    }
    return sum;
}

int main()
{
    cout<<"BUBT ILLUSION"<<endl;
}

Simple Pointer Code[Index ]

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

int main()
{
    int *a,b=10;
    a=&b;
    cout<<*a<<endl;
    b=20;
    cout<<*a<<endl;
}

/*
Output:
10
20
*/

Bigmod[Index ]

#include<bits/stdc++.h>
using namespace std;
const int inf=1000000007;
long long int bigmod(int b,int p,int m)
{
    if(p==0) return 1;
    long long res=bigmod(b,p/2,m);
    res=(res*res)%m;
    if(p%2==1)
    res=(res*b)%m;
    return res;
}
int main()
{
    int b,p,m;
    while(cin>>b>>p>>m)
    {
        cout<<bigmod(b,p,m)<<endl;;
    }
    return 0;
}

Bigmod(Bitwise)[Index ]

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

LL bigmod(LL b,LL p,LL m)
{
    LL res=1;
    while(p)
    {
        if(p&1) res=(res*b)%m;
        b=(b*b)%m;
        p=p>>1;
    }
    return res%m;
}
int main()
{
    cout<<bigmod(2,3,5)<<endl;
}

Prime Generation[Index ]

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

bool a[100000009];
int p[5800009];
void sieve()
{
    long long i,j,k=0; a[0]=1; a[1]=1; p[0]=2;
    for(i=3;i<=100000006;i=i+2)
    {
        if(a[i]==0)
        {
            p[++k]=i;
            for(j=i*i;j<=100000006;j=j+2*i)
                a[j]=1;
        }
    }
}

int main()
{
    sieve();
    cout<<k<<endl;
    for(int i=0;i<=10000;i++)
    printf("%d ",p[i]);
    puts("");
    return 0;
}

Depth-First Search(DFS)[Index ]

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

/*
1) graph[u][v]=1, if there is an edge between u and v.
2) color[x]=0 means the color of node x is WHITE and we haven't visited the node yet.
3) color[x]=1 means the color of node x is GRAY and this node is Discovered.
   that means we have just visited x, but we haven't visited all descendants of x.
4) color[x]=2 means the color of node x is BLACK and this node is Finished.
   that means we have visited all descendants of x.
5) t means time
6) discovery_time[x]=t1 means the time(t1) when node x is first processed.
7) finishing_time[x]=t1 means the time(t1) when the descendants of node x is finished.
*/
int graph[105][105];
int color[105];
int discovery_time[105];
int finishing_time[105];
int t=0;
int node;

void dfs(int u)
{
    color[u]=1;
    discovery_time[u]=++t;
    for(int v=1;v<=node;v++)
    {
        if(graph[u][v]&&color[v]==0)
            dfs(v);
    }
    color[u]=2;
    finishing_time[u]=++t;
}

int main()
{
    int i,j,k,edge,m,d,x,y;
    while(cin>>node>>edge)
    {
        memset(graph,0,sizeof(graph));
        memset(color,0,sizeof(color));
        t=0;
        for(i=1;i<=edge;i++)
        {
            cin>>x>>y;
            graph[x][y]=1;
        }
        dfs(1);
        for(i=1;i<=node;i++)
            printf("%d %d %d\n",i,discovery_time[i],finishing_time[i]);
    }
    return 0;
}

Dijkstra[Index ]


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

int dist[10009];
const int inf=100000007;

int main()
{
    int i,j,k,n,m,d,x,y,z,source,node,edge,destination;
    while(cin>>node>>edge)
    {
        vector<pair<int,int> >adj[10009];
        for(i=0;i<edge;i++)
        {
            cin>>x>>y>>z;
            adj[x].push_back(make_pair(y,z));
            adj[y].push_back(make_pair(x,z));
        }
        cin>>source>>destination;
        priority_queue<pair<int,int> >pq;
        for(i=0;i<=10002;i++)
        dist[i]=inf;
        dist=0;
        pq.push(make_pair(0,source));
        while(!pq.empty())
        {
            pair<int,int>p=pq.top(),pp;
            pq.pop();
            int cost=p.first*-1;
            int u=p.second;
            for(i=0;i<adj[u].size();i++)
            {
                pp=adj[u][i];
                int v=pp.first;
                if(dist[v]>cost+pp.second)
                {
                    dist[v]=cost+pp.second;
                    pq.push(make_pair(-dist[v],v));
                }
            }
        }
        printf("%d\n",dist[destination]);
    }
    return 0;
}

Minimum Spanning Tree(MST-Prims)[Index ]


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

bool visited[10009];

int main()
{
    int i,j,k,n,m,d,e,x,y,z;
    while(cin>>n>>e)
    {
        memset(visited,0,sizeof(visited));
        vector<pair<int,int> >adj[10009];
        for(i=0;i<e;i++)
        {
            cin>>x>>y>>z;
            adj[x].push_back(make_pair(y,z));
            adj[y].push_back(make_pair(x,z));
        }
        int start=1;
        visited[start]=1;
        priority_queue<pair<int,pair<int,int> > >pq;
        for(i=0;i<adj[1].size();i++)
        {
            pair<int,int>p=adj[1][i];
            pq.push(make_pair(-p.second,make_pair(1,p.first)));
        }
        long long cost=0;
        while(!pq.empty())
        {
            pair<int,pair<int,int> >p=pq.top();
            int u=p.second.first;
            int v=p.second.second;
            int cc=p.first*-1;
            if(visited[u]&&visited[v]) pq.pop();
            else
            {
                cost=cost+cc;
                visited[v]=1;
                for(i=0;i<adj[v].size();i++)
                {
                    pair<int,int>pp=adj[v][i];
                    pq.push(make_pair(-pp.second,make_pair(v,pp.first)));
                }
            }
        }
        cout<<cost<<endl;
    }
    return 0;
}

Minimum Spanning Tree(MST-Kruskal)[Index ]


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

//krushkal

int pr[10009];
struct info
{
    int u,v,w;
};

bool better(info x,info y)
{
    if(x.w<y.w) return 1;
    return 0;
}

int find(int r)
{
    if(pr[r]==r) return r;
    return find(pr[r]);
}

int main()
{
    int i,j,k,node,edge,m,d,x,y,z;
    while(cin>>node>>edge)
    {
        info p[100009];
        for(i=0;i<edge;i++)
            cin>>p[i].u>>p[i].v>>p[i].w;
        sort(p,p+edge,better);
        for(i=1;i<=node;i++)
            pr[i]=i;
        int co=0;
        long long cost=0;
        for(i=0;i<edge;i++)
        {
            int u=find(p[i].u);
            int v=find(p[i].v);
            if(u!=v)
            {
                pr[u]=v;
                co++;
                cost=cost+p[i].w;
                if(co==node-1) break;
            }
        }
        cout<<cost<<endl;
    }
    return 0;
}

Topological Sort(In-degree Solution)[Index ]


/*
Uva Problem 10305 -Ordering Tasks,11686 - Pick up sticks
Topological Sort(Indegree Solution)
*/

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

int indegree[109];

int main()
{
    int i,j,k,n,m,d,node,edge,x,y;
    while(cin>>node>>edge)
    {
        if(node==0&&edge==0) break;
        memset(indegree,0,sizeof(indegree));
        vector<int>adj[109];
        for(i=0;i<edge;i++)
        {
            cin>>x>>y;
            indegree[y]++;
            adj[x].push_back(y);
        }
        queue<int>q;
        for(i=1;i<=node;i++)
        {
            if(indegree[i]==0) q.push(i);
        }
        vector<int>topo;
        while(!q.empty())
        {
            int ff=q.front();
            q.pop();
            topo.push_back(ff);
            int sz=adj[ff].size();
            for(i=0;i<sz;i++)
            {
                int u=adj[ff][i];
                indegree[u]--;
                if(indegree[u]==0) q.push(u);
            }
        }
        //if node!=topo.size(), then no solution exists. Because an cycle occurs.
        int sz=topo.size();
        cout<<topo[0];
        for(i=1;i<sz;i++)
            cout<<" "<<topo[i];
        puts("");
    }
    return 0;
}

Topological Sort(DFS Solution)[Index ]


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

int graph[109][109];
int visited[109];
vector<int>v;
int n,e;
void dfs(int u)
{
    if(visited[u]) return;
    visited[u]=1;
    for(int i=1;i<=n;i++)
    {
        if(graph[u][i]) dfs(i);
    }
    v.push_back(u);
}

int main()
{
    int i,j,k,m,d,x,y;
    while(cin>>n>>e)
    {
        if(n==0&&e==0) break;
        memset(graph,0,sizeof(graph));
        memset(visited,0,sizeof(visited));
        for(i=0;i<e;i++)
        {
            cin>>x>>y;
            graph[x][y]=1;
        }
        for(i=1;i<=n;i++)
        {
            if(visited[i]==0)
                dfs(i);
        }
        printf("%d",v[n-1]);
        for(i=n-2;i>=0;i--)
            printf(" %d",v[i]);
            puts("");
        v.clear();
    }
    return 0;
}

Strongly Connected Components(SCC)[Index ]


/*
Related Problem: Uva 11838 - Come and Go, 11709 - Trust groups
*/

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

vector<int>adj[2009];
vector<int>radj[2009];
int visited[2009];
vector<int>v;
int node,edge;
void dfs(int u)
{
    if(visited[u]) return;
    visited[u]=1;
    int sz=adj[u].size();
    for(int i=0;i<sz;i++)
    {
        int x=adj[u][i];
        if(visited[x]==0) dfs(x);
    }
    v.push_back(u);
}
void adfs(int u)
{
    if(visited[u]) return;
    visited[u]=1;
    int sz=radj[u].size();
    for(int i=0;i<sz;i++)
    {
        int x=radj[u][i];
        if(visited[x]==0) adfs(x);
    }
}

int main()
{
    int i,j,k,m,d,x,y,z;
    while(cin>>node>>edge)
    {
        if(node==0&&edge==0) break;
        memset(visited,0,sizeof(visited));
        for(i=0;i<edge;i++)
        {
            cin>>x>>y;
            adj[x].push_back(y);
            radj[y].push_back(x);
        }
        for(i=1;i<=node;i++)
        {
            if(visited[i]==0)
                dfs(i);
        }
        int co=0;
        int sz=v.size();
        reverse(v.begin(),v.end());
        memset(visited,0,sizeof(visited));
        for(i=0;i<sz;i++)
        {
            if(visited[v[i]]==0)
            {
                co++;
                adfs(v[i]);
            }
        }
        printf("SCC=%d\n",co);
        v.clear();
        for(i=0;i<2002;i++)
            adj[i].clear();
        for(i=0;i<2002;i++)
            radj[i].clear();
    }
    return 0;
}

Sieve-1(for prime check)[Index ]

/**  Algo: Sieve for prime check
   Complexity:O(NloglogN)
   Execution Time: 300ms(N=10^7)
   Here, a[i]=0, if i is prime.
         a[i]=1, if i is not prime.
**/

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

bool a[10000009];
void sieve_for_primecheck()
{
    long long i,j,sq=sqrt(10000000);
    for(i=4;i<=10000000;i=i+2)
        a[i]=1;
    for(i=3;i<=sq;i=i+2)
    {
        if(a[i]==0)
        {
            for(j=i*i;j<=10000000;j=j+2*i)
                a[j]=1;
        }
    }
}

int main()
{
    int i,j,k,n,m,d;
    sieve_for_primecheck();
    for(i=1;i<=30;i++)
        printf("%d %d\n",i,a[i]);
}

Sieve-2(for distinct prime factor)[Index ]

/**  Algo: Sieve for distinct prime factor
   Complexity:O(NloglogN)
   Execution Time: 180ms(N=10^6)
   Here, a[i]=k, then i has k distinct prime factor
**/

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

int a[1000099];
void sieve_for_distinct_prime_factor()
{
    long long i,j;
    for(i=2;i<=1000000;i++)
    {
        if(a[i]==0)
        {
            for(j=i;j<=1000000;j=j+i)
                a[j]++;
        }
    }
}

int main()
{
    int i,j,k,n,m,d;
    sieve_for_distinct_prime_factor();
    for(i=1;i<=30;i++)
        printf("%d %d\n",i,a[i]);
}

Sieve-3(for sum of distinct prime factor)[Index ]

/**  Algo: Sieve for sum of distinct prime factor
   Complexity:O(NloglogN)
   Execution Time: 161ms(N=10^6)
   Here, a[i]=k means sum of distinct prime factor of i is k
**/

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

int a[1000099];
void sieve_for_sum_of_distinct_prime_factor()
{
    long long i,j;
    for(i=2;i<=1000000;i++)
    {
        if(a[i]==0)
        {
            for(j=i;j<=1000000;j=j+i)
                a[j]=a[j]+i;
        }
    }
}

int main()
{
    int i,j,k,n,m,d;
    sieve_for_sum_of_distinct_prime_factor();
    for(i=1;i<=20;i++)
        printf("Sum of distinct prime factor of %d is %d\n",i,a[i]);
}

Sieve-4(for number of divisor-1)[Index ]

/**  Algo: Sieve for number of divisor
   Complexity:O(NloglogN)
   Execution Time: 318ms(N=10^6)
   Here, nod[i]=k means i has k divisors
**/

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

bool a[1000099];
int nod[1000099];
void sieve_for_number_of_divisor()
{
    LL i,j; nod[2]=2;
    for(i=2;i<=1000000;i++)
    {
        if(a[i]==0)
        {
            nod[i]=2;
            for(j=i+i;j<=1000000;j=j+i)
            {
                a[j]=1;
                int co=0;
                int temp=j;
                while(temp%i==0)
                {
                    co++;
                    temp=temp/i;
                }
                nod[j]=nod[j]*(co+1);
            }
        }
    }
}

int main()
{
    int i,j,k,n,m,d;
    for(i=1;i<=1000000;i++)
        nod[i]=1;
    sieve_for_number_of_divisor();
    for(i=1;i<=20;i++)
    {
        printf("%d has %d divisors\n",i,nod[i]);
    }
    return 0;
}

Sieve-5(for number of divisor-2)[Index ]

/**  Algo: Sieve for number of divisor
   Complexity:O(NloglogN)
   Execution Time: 287ms(N=10^6)
   Here, a[i]=k means i has k+1 divisors
**/

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

int a[1000099];

void sieve_for_number_of_divisor()
{
    int i,j;
    for(i=2;i<=1000000;i++)
    {
        for(j=i;j<=1000000;j=j+i)
            a[j]++;
    }
}

int main()
{
    int i,j,k,n,m,d;
    sieve_for_number_of_divisor();
    for(i=1;i<=20;i++)
        printf("%d has %d divisor\n",i,a[i]+1);
    return 0;
}

Sieve-6(for sum of divisor)[Index ]

/**  Algo: Sieve for sum of divisor
   Complexity:O(NloglogN)
   Execution Time: 287ms(N=10^6)
   Here, a[i]=k means sum of divisors of i is  k+1
**/

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

int a[1000099];

void sieve_for_sum_of_divisor()
{
    int i,j;
    for(i=2;i<=1000000;i++)
    {
        for(j=i;j<=1000000;j=j+i)
            a[j]=a[j]+i;
    }
}

int main()
{
    int i,j,k,n,m,d;
    sieve_for_sum_of_divisor();
    for(i=1;i<=20;i++)
        printf("SOD of %d is %d\n",i,a[i]+1);
    return 0;
}

Bubble Sort[Index ]

/*
Algorithm: Bubble Sort
Complexity: O(n^2)
*/
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int i,j,k,n,m,d,a[100];
    while(cin>>n)
    {
        for(i=0;i<n;i++)
            cin>>a[i];
        for(i=0;i<n-1;i++)
        {
            for(j=0;j<n-2-i;j++)
            {
                if(a[j]>a[j+1])
                    swap(a[j],a[j+1]);
            }
        }
        for(i=0;i<n;i++)
            cout<<a[i]<<" ";
        puts("");
    }
    return 0;
}

Insertion Sort[Index ]

/*
Algorithm: Insertion Sort
Complexity: O(n^2)
*/
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int i,j,k,n,d,a[109];
    while(cin>>n)
    {
        for(i=0;i<n;i++)
            cin>>a[i];
        for(i=1;i<n;i++)
        {
            int val=a[i];
            for(j=i-1;j>=0;j--)
            {
                if(a[j]>val)
                    swap(a[j],a[j+1]);
            }
        }
        for(i=0;i<n;i++)
            cout<<a[i]<<" ";
        puts("");
    }
    return 0;
}

Selection Sort[Index ]

/*
Algorithm: Selection Sort
Complexity: O(n^2)
*/
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int i,j,k,n,m,d,a[1009];
    while(cin>>n)
    {
        for(i=0;i<n;i++)
            cin>>a[i];
        for(i=0;i<n-1;i++)
        {
            int min=i;
            for(j=i+1;j<n;j++)
            {
                if(a[j]<a[min])
                    min=j;
            }
            swap(a[min],a[i]);
        }
        for(i=0;i<n;i++)
            cout<<a[i]<<" ";
        puts("");
    }
    return 0;
}

Merge Sort[Index ]

/*
Algorithm: Merge Sort
Complexity: O(nlogn)
*/
#include<bits/stdc++.h>
using namespace std;

int a[1009];

void Merge(int left_begin,int left_end,int right_begin,int right_end)
{
    int pos=0,pp=left_begin;
    int temp[right_end-left_begin+3];
    while(left_begin<=left_end&&right_begin<=right_end)
    {
        if(a[left_begin]<=a[right_begin])
            temp[pos++]=a[left_begin++];
        else temp[pos++]=a[right_begin++];
    }
    while(left_begin<=left_end) temp[pos++]=a[left_begin++];
    while(right_begin<=right_end) temp[pos++]=a[right_begin++];
    for(int i=0;i<pos;i++)
        a[pp+i]=temp[i];
    return;
}

void MergeSort(int left,int right)
{
    int mid=(left+right)>>1;
    if(left<right)
    {
        MergeSort(left,mid);
        MergeSort(mid+1,right);
        Merge(left,mid,mid+1,right);
    }
}

int main()
{
    int i,j,k,n,m,d;
    while(cin>>n)
    {
        for(i=0;i<n;i++)
            cin>>a[i];
        MergeSort(0,n-1);
        for(i=0;i<n;i++)
            printf("%d ",a[i]);
        printf("\n");
    }
    return 0;
}

Quick Sort[Index ]

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

int a[109];

void quicksort(int first,int last)
{
    int pivot,j,temp,i;

    if(first<last)
    {
         pivot=first;
         i=first;
         j=last;

        while(i<j)
        {
             while(a[i]<=a[pivot]&&i<last)
                 i++;
             while(a[j]>a[pivot])
                 j--;
             if(i<j)
            {
                 temp=a[i];
                  a[i]=a[j];
                  a[j]=temp;
             }
         }
         temp=a[pivot];
         a[pivot]=a[j];
         a[j]=temp;
         quicksort(first,j-1);
         quicksort(j+1,last);

    }
}
int main()
{
  int i,j,k,n,m,d;
  while(cin>>n)
  {
      for(i=0;i<n;i++)
        cin>>a[i];
      quicksort(0,n-1);
      for(i=0;i<n;i++)
        printf(" %d",a[i]);
        puts("");
  }
  return 0;
}

Trie-1[Index ]

/*
Given N strings of a dictionary and Q queries. In each queries you have have to say
whether a string is FOUND or NOT FOUND in this dictionary.
*/

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

struct node
{
    bool endmark;
    node *next[28];
    node()
    {
        endmark=false;
        for(int i=0;i<26;i++)
            next[i]=NULL;
    }
};

node *root;

void insert(string s)
{
    node *curr=root;
    int sz=s.size();
    for(int i=0;i<sz;i++)
    {
        int id=s[i]-'a';
        if(curr->next[id]==NULL)
            curr->next[id]=new node();
        curr=curr->next[id];
    }
    curr->endmark=true;
}

bool find(string s)
{
    node *curr=root;
    int sz=s.size();
    for(int i=0;i<sz;i++)
    {
        int id=s[i]-'a';
        if(curr->next[id]==NULL) return false;
        curr=curr->next[id];
    }
    return curr->endmark;
}

void del(node *curr)
{
    for(int i=0;i<26;i++)
    {
        if(curr->next[i])
            del(curr->next[i]);
    }
    delete(curr);
}

int main()
{
    int i,j,k,n,m,d,q;
    string s;
    while(cin>>n>>q)
    {
        root=new node();  // we have created root node.
        for(i=0;i<n;i++)
        {
            cin>>s;
            insert(s);
        }
        for(i=0;i<q;i++)
        {
            cin>>s;
            if(find(s)==true) puts("Found");
            else puts("Not Found");
        }
        del(root);  // The whole trie is deleted
    }
    return 0;
}

Trie-2[Index ]

/*
Given a array with N integers. You have to output the maximum value if we perform
XOR operation between any two numbers of the array.
*/

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

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

int Off(int n,int pos)
{
    return n=n&~(1<<pos);
}

bool Check(int n,int pos)
{
    return (bool) (n&(1<<pos));
}
struct node
{
    node *next[3];
    node()
    {
        for(int i=0;i<2;i++)
            next[i]=NULL;
    }
};
node *root;

void insert(int n)
{
    node *curr=root;
    int id;
    for(int i=31;i>=0;i--)
    {
        if(Check(n,i)) id=1;
        else id=0;
        if(curr->next[id]==NULL) curr->next[id]=new node();
        curr=curr->next[id];
    }
}

int find(int n)
{
    node *curr=root;
    int ans=0;
    for(int i=31;i>=0;i--)
    {
        if(Check(n,i))
        {
            if(curr->next[0])
            {
                curr=curr->next[0];
                ans=On(ans,i);
            }
            else curr=curr->next[1];
        }
        else
        {
            if(curr->next[1])
            {
                curr=curr->next[1];
                ans=On(ans,i);
            }
            else curr=curr->next[0];
        }
    }
    return ans;
}

void del(node *curr)
{
    for(int i=0;i<2;i++)
    {
        if(curr->next[i])
            del(curr->next[i]);
    }
    delete(curr);
}
int main()
{
    int i,j,k,n,m,a[100009];
    while(cin>>n)
    {
        root=new node();
        for(i=0;i<n;i++)
        {
            cin>>a[i];
            insert(a[i]);
        }
        int max_xor=0;
        for(i=0;i<n;i++)
        {
            max_xor=max(max_xor,find(a[i]));
        }
        cout<<max_xor<<endl;
        del(root);
    }
    return 0;
}

Segment Intersection[Index ]

// A C++ program to check if two given line segments intersect
//Useful Links:http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
#include<bits/stdc++.h>
using namespace std;

struct info
{
    int x;
    int y;
};

// Given three collinear points p, q, r, the function checks if
// point q lies on line segment 'pr'
bool onSegment(info p, info q, info r)
{
    if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
        q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
       return true;

    return false;
}

// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are collinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(info p, info q, info r)
{
    // See 10th slides from following link for derivation of the formula
    // http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);

    if (val == 0) return 0;  // collinear

    return (val > 0)? 1: 2; // clock or counterclock wise
}

// The main function that returns true if line segment 'p1q1'
// and 'p2q2' intersect.
bool doIntersect(info p1, info q1, info p2, info q2)
{
    // Find the four orientations needed for general and
    // special cases
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    // General case
    if (o1 != o2 && o3 != o4)
        return true;

    // Special Cases
    // p1, q1 and p2 are collinear and p2 lies on segment p1q1
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;

    // p1, q1 and p2 are collinear and q2 lies on segment p1q1
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;

    // p2, q2 and p1 are collinear and p1 lies on segment p2q2
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;

     // p2, q2 and q1 are collinear and q1 lies on segment p2q2
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

    return false;
}

// Driver program to test above functions
int main()
{
    info p1 = {1, 1}, q1 = {10, 1};
    info p2 = {1, 2}, q2 = {10, 2};

    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

    p1 = {10, 0}, q1 = {0, 10};
    p2 = {0, 0}, q2 = {10, 10};
    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

    p1 = {-5, -5}, q1 = {0, 0};
    p2 = {1, 1}, q2 = {10, 10};
    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";
    return 0;
}

/*output

No
Yes
No
*/

Point Existence Checking in a Polygon[Index ]

/*
    Algorithm Used:
    Useful Links: http://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/
    http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=575
*/

// A C++ program to check if a given point lies inside a given polygon
// Refer http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
// for explanation of functions onSegment(), orientation() and doIntersect()
#include<bits/stdc++.h>
using namespace std;

// Define Infinite (Using INT_MAX caused overflow problems)
#define INF 30000

struct info
{
    int x;
    int y;
};

// Given three colinear points p, q, r, the function checks if
// point q lies on line segment 'pr'
bool onSegment(info p, info q, info r)
{
    if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
            q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
        return true;
    return false;
}

// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(info p, info q, info r)
{
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);

    if (val == 0) return 0;  // colinear
    return (val > 0)? 1: 2; // clock or counterclock wise
}

// The function that returns true if line segment 'p1q1'
// and 'p2q2' intersect.
bool doIntersect(info p1, info q1, info p2, info q2)
{
    // Find the four orientations needed for general and
    // special cases
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    // General case
    if (o1 != o2 && o3 != o4)
        return true;

    // Special Cases
    // p1, q1 and p2 are colinear and p2 lies on segment p1q1
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;

    // p1, q1 and p2 are colinear and q2 lies on segment p1q1
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;

    // p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;

     // p2, q2 and q1 are colinear and q1 lies on segment p2q2
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

    return false; // Doesn't fall in any of the above cases
}

// Returns true if the point p lies inside the polygon[] with n vertices
bool isInside(info polygon[], int n, info p)
{
    // There must be at least 3 vertices in polygon[]
    if (n < 3)  return false;

    // Create a point for line segment from p to infinite
    info extreme = {INF, p.y};

    // Count intersections of the above line with sides of polygon
    int count = 0, i = 0;
    do
    {
        int next = (i+1)%n;

        // Check if the line segment from 'p' to 'extreme' intersects
        // with the line segment from 'polygon[i]' to 'polygon[next]'
        if (doIntersect(polygon[i], polygon[next], p, extreme))
        {
            // If the point 'p' is colinear with line segment 'i-next',
            // then check if it lies on segment. If it lies, return true,
            // otherwise false
            if (orientation(polygon[i], p, polygon[next]) == 0)
               return onSegment(polygon[i], p, polygon[next]);

            count++;
        }
        i = next;
    } while (i != 0);

    // Return true if count is odd, false otherwise
    return count&1;  // Same as (count%2 == 1)
}

// Driver program to test above functions
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int i,j,k,n,m,d;
    while(cin>>n)
    {
        if(n==0) break;
        info poly[1009];
        for(i=0;i<n;i++)
        cin>>poly[i].x>>poly[i].y;
        info ppp;
        cin>>ppp.x>>ppp.y;
        if(isInside(poly,n,ppp)) puts("T");
        else puts("F");
    }
    return 0;
}

Histogram With Stack[Index ]

/*
Algorithm Used: Stack
Useful Links: http://www.geeksforgeeks.org/largest-rectangle-under-histogram/
http://lightoj.com/volume_showproblem.php?problem=1083
*/

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

int main()
{
    int i,j,k,n,m,d,h[30009],tp,left_smallest,right_smallest,area_with_tp,t=0,test;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            cin>>h[i];
        stack<int>st;
        i=1;
        int mx_area=0;
        while(i<=n)
        {
            if(st.empty()) st.push(i++);
            else if(h[i]>=h[st.top()]) st.push(i++);
            else
            {
                tp=st.top();
                st.pop();
                if(st.empty()) left_smallest=0;
                else left_smallest=st.top();
                right_smallest=i;
                area_with_tp=h[tp]*(right_smallest-left_smallest-1);
                mx_area=max(mx_area,area_with_tp);
            }
        }
        while(!st.empty())
        {
            tp=st.top();
            st.pop();
            if(st.empty()) left_smallest=0;
            else left_smallest=st.top();
            right_smallest=i;
            area_with_tp=h[tp]*(right_smallest-left_smallest-1);
            mx_area=max(mx_area,area_with_tp);
        }
        printf("Case %d: %d\n",++t,mx_area);
    }
    return 0;
}

Segment Tree-1[Index ]

/*
Given an array with N elements, indexed from 1 to N. Now you will
be given some queries in the form I J, your task is to find the
minimum value from index I to J.
    Algorithm Used: Segment Tree
    Useful Links: http://lightoj.com/volume_showproblem.php?problem=1082
*/

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int inf=1000000000;

int tree[1000006];
int a[100005];
void init(int node,int b,int e)
{
    if(b==e)
    {
        tree[node]=a[b];
        return;
    }
    int left=node<<1;
    int right=left+1;
    int mid=(b+e)/2;
    init(left,b,mid);
    init(right,mid+1,e);
    tree[node]=min(tree[left],tree[right]);
}
int query(int node,int b,int e,int i,int j)
{
    if(i>e||j<b) return inf;
    if(b>=i&&e<=j) return tree[node];
    int left=node<<1;
    int right=left+1;
    int mid=(b+e)/2;
    int p1=query(left,b,mid,i,j);
    int p2=query(right,mid+1,e,i,j);
    return min(p1,p2);
}
int main()
{
    int i,j,k,n,d,test,t=0,q,u,v;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d%d",&n,&q);
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
            init(1,1,n);
            printf("Case %d:\n",++t);
        while(q--)
        {
            scanf("%d%d",&u,&v);
            printf("%d\n",query(1,1,n,u,v));
        }
    }
    return 0;
}

Segment Tree-2[Index ]

/*
1.      0 x y v - you have to add v to all numbers in
        the range of x to y (inclusive), where x and y are
        two indexes of the array.
2.      1 x y - output a line containing a single integer
        which is the sum of all the array elements between
        x and y (inclusive).
    Algorithm Used: Segment Tree
    Useful Links: http://lightoj.com/volume_showproblem.php?problem=1164
*/

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int inf=1000000007;

struct info
{
    long long sum,add;
};

info tree[400050];

void update(LL node,LL b,LL e,LL i,LL j,LL value)
{
    if(b>j||e<i) return;
    if(b>=i&&e<=j)
    {
        tree[node].sum+=value*(e-b+1);
        tree[node].add+=value;
        return;
    }
    LL left=node<<1;
    LL right=left+1;
    LL mid=(b+e)>>1;
    update(left,b,mid,i,j,value);
    update(right,mid+1,e,i,j,value);
    tree[node].sum=tree[left].sum+tree[right].sum+(e-b+1)*tree[node].add;
}

long long query(LL node,LL b,LL e,LL i,LL j,LL carry)
{
    if(b>j||e<i) return 0;
    if(b>=i&&e<=j)
        return tree[node].sum+carry*(e-b+1);
    LL left=node<<1;
    LL right=left+1;
    LL mid=(b+e)>>1;
    long long p1=query(left,b,mid,i,j,carry+tree[node].add);
    long long p2=query(right,mid+1,e,i,j,carry+tree[node].add);
    return p1+p2;
}
int main()
{
    LL i,j,k,n,m,d,t=0,test,op,x,y,value,q;
    scanf("%lld",&test);
    while(test--)
    {
        scanf("%lld%lld",&n,&q);
//        for(i=1;i<=3*n;i++)
//        {
//            tree[i].sum=0;
//            tree[i].add=0;
//        }
        memset(tree,0,sizeof(tree));
        printf("Case %lld:\n",++t);
        while(q--)
        {
            scanf("%lld",&op);
            if(op==0)
            {
                scanf("%lld%lld%lld",&x,&y,&value);
                update(1,1,n,x+1,y+1,value);
//                for(i=1;i<=25;i++)
//                    printf("tree%d=%d\n",i,tree[i].sum);
            }
            else
            {
                scanf("%lld%lld",&x,&y);
                printf("%lld\n",query(1,1,n,x+1,y+1,0));
            }
        }
    }
    return 0;
}

First Input With Buffer[Index ]

/*
    Algorithm Used:
    Useful Links:
*/

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

const int maxBufSize = (1 << 23);
struct Input
{
    int bufSize, bufEnd, bufPos;
    char buffer[maxBufSize];
    void grabBuffer() {
        bufSize = (maxBufSize); bufPos = 0;
        bufEnd = fread(buffer, sizeof (char), bufSize, stdin);
        buffer[bufEnd] = '\0';
    }
    bool bufEof() {return bufPos == bufEnd;}
    int getChar() {return buffer[bufPos++];}
    void skipWS() {
        while ((buffer[bufPos] == '\n' ||
            buffer[bufPos] == ' ' || buffer[bufPos] == '\t'))
            bufPos++;
    }
    int next_u32() {
        int n = 0, x; skipWS();
        bool neg=false;
        if (  ( x = getChar() )=='-'  ){
            neg=true;
            x=getChar();
        }

        for (; x <= '9' && x >= '0'; x = getChar())
            n = (n << 3) + (n << 1) + (x - '0');
        if ( neg )return -n;
        else return n;
    }
    inline bool isWhiteSpace(char x) {
        return x == ' ' || x == '\n' || x == '\t';
    }
    char rChar() {skipWS(); return getChar();}
}zz;
int main()
{
    zz.grabBuffer();
    int i,j,k,n,m,d,test;
    test=zz.next_u32();
    while(test--)
    {
        n=zz.next_u32();
        printf("%d\n",n);
    }
    return 0;
}

Articulation Point[Index ]

/*
Algorithm: Articulation Point
Problem: Lightoj-1063

An Articulation point in a connected graph is a vertex that,
if delete, would break the graph into two or more pieces.

Input: An undirected graph G(V,E)
Output: Number of Articulation Point
*/

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

int node,edge;
vector<int>adj[10009];
int discovery[10009];
int low[10009];
int cnt[10009];
int art[10009];
int tt=0;

void articulation_point(int u,int parent)
{
    discovery[u]=++tt;
    low[u]=discovery[u];
    int sz=adj[u].size();
    for(int i=0;i<sz;i++)
    {
        int v=adj[u][i];
        if(low[v]==-1) // a tree-edge
        {
            articulation_point(v,u);
            cnt[u]++;
            low[u]=min(low[u],low[v]);
            if(low[v]>=discovery[u])
                art[u]=1;
        }
        else if(v!=parent) //a back-edge
            low[u]=min(low[u],discovery[v]);
    }
}

int main()
{
    int i,j,k,n,m,test,t=0,x,y;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d%d",&node,&edge);
        tt=0;
        memset(low,-1,sizeof(low));
        memset(cnt,0,sizeof(cnt));
        memset(art,0,sizeof(art));
        memset(discovery,0,sizeof(discovery));
        for(i=0;i<edge;i++)
        {
            scanf("%d%d",&x,&y);
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        for(i=1;i<=node;i++)
        {
            if(low[i]==-1)
            {
                articulation_point(i,i);
                if(cnt[i]==1)
                    art[i]=0;
            }
        }
        int ans=0;
        for(i=1;i<=node;i++)
        {
            if(art[i]) ans++;
        }
        printf("Case %d: %d\n",++t,ans);
        for(i=0;i<=10004;i++)
            adj[i].clear();
    }
    return 0;
}

Matrix Multiplication[Index ]

/*
Algorithm: Matrix Multiplication
mult() is a function that receives two matrix
and return their multiplication.
*/

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

struct matrix
{
    int a[5][5];
    int row,col;
};

matrix mult(matrix x,matrix y)
{
    matrix r;
    r.row=x.row;
    r.col=y.col;
    for(int i=0;i<r.row;i++)
    {
        for(int j=0;j<r.col;j++)
        {
            int sum=0;
            for(int k=0;k<x.col;k++)
            {
                sum=sum+x.a[i][k]*y.a[k][j];
            }
            r.a[i][j]=sum;
        }
    }
    return r;
}

int main()
{
    int i,j,k,n,m,d;
    matrix p,q;
    p.a[0][0]=1;
    p.a[0][1]=2;
    p.a[0][2]=3;
    p.a[1][0]=4;
    p.a[1][1]=5;
    p.a[1][2]=6;

    q.a[0][0]=4;
    q.a[0][1]=2;
    q.a[1][0]=6;
    q.a[1][1]=1;
    q.a[2][0]=3;
    q.a[2][1]=4;
    p.row=2;
    p.col=3;
    q.row=3;
    q.col=2;
    matrix ans=mult(p,q);
    for(i=0;i<ans.row;i++)
    {
        for(j=0;j<ans.col;j++)
        {
            printf("%d ",ans.a[i][j]);
        }
        printf("\n");
    }
}

Articulation Bridge[Index ]

/*
Algorithm: Articulation Bridge
Problem: Lightoj-1026

An Articulation bridge in a connected graph is an edge that,
if delete, would break the graph into two or more pieces.

Input: An undirected graph G(V,E)
Output: Number of Articulation Bridge and Show the edges
*/

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

struct info
{
    int x,y;
};
info p[100009];

int node,edge;
vector<int>adj[100009];
int discovery[10009];
int low[10009];
int tt=0;
int kk=0;

bool better(info r1,info r2)
{
    if(r1.x<r2.x) return 1;
    if(r1.x==r2.x&&r1.y<r2.y) return 1;
    return 0;
}

void articulation_bridge(int u,int parent)
{
    discovery[u]=++tt;
    low[u]=discovery[u];
    int sz=adj[u].size();
    for(int i=0;i<sz;i++)
    {
        int v=adj[u][i];
        if(low[v]==-1) // a tree-edge
        {
            articulation_bridge(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>discovery[u])
            {
                int temp1=u,temp2=v;
                if(temp1>=temp2) swap(temp1,temp2);
                p[kk].x=temp1;
                p[kk].y=temp2;
                kk++;
            }
        }
        else if(v!=parent) //a back-edge
            low[u]=min(low[u],discovery[v]);
    }
}

int main()
{
    int i,j,k,n,m,test,t=0,x,y,q;
    string s;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d%d",&node,&edge);
        tt=0; kk=0;
        memset(low,-1,sizeof(low));
        memset(discovery,0,sizeof(discovery));
        for(i=0;i<edge;i++)
        {
            scanf("%d%d",&x,&y);
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        for(i=1;i<=node;i++)
        {
            if(low[i]==-1)
                articulation_bridge(i,i);
        }
        sort(p,p+kk,better);
        printf("Case %d:\n%d critical links\n",++t,kk);
        for(i=0;i<kk;i++)
        {
            printf("%d - %d\n",p[i].x,p[i].y);
        }
        for(i=0;i<=100004;i++)
            adj[i].clear();
    }
    return 0;
}

Matrix Exponentiation-1[Index ]


/*
Algorithm: Matrix Exponentiation
Problem: http://uva.onlinejudge.org/external/106/10689.html
f(0) = a
f(1) = b
f(n) = f(n-1) + f(n-2), n > 1
Given the values of a, b, you have to find the last m digits of f(n), where 1<=m<=4
*/
#include<bits/stdc++.h>
using namespace std;
#define LL long long

LL aa,bb,nn,mm;
LL mod;

struct matrix
{
    LL a[5][5];
    LL row,col;
};

matrix identity_matrix,base;
void f()
{
    identity_matrix.row=2;
    identity_matrix.col=2;
    base.row=2;
    base.col=2;
    for(LL i=0;i<2;i++)
    {
        for(LL j=0;j<2;j++)
        {
            if(i==j) identity_matrix.a[i][j]=1;
            else identity_matrix.a[i][j]=0;
            base.a[i][j]=1;
        }
    }
    base.a[1][1]=0;
}

matrix mult(matrix x,matrix y)
{
    matrix r;
    r.row=x.row;
    r.col=y.col;
    for(LL i=0;i<r.row;i++)
    {
        for(LL j=0;j<r.col;j++)
        {
            LL sum=0;
            for(LL k=0;k<x.col;k++)
            {
                sum=sum+x.a[i][k]*y.a[k][j];
            }
            r.a[i][j]=sum%mod;
        }
    }
    return r;
}

matrix bigmod(matrix b,LL p)
{
    if(p==0) return identity_matrix;
    if(p==1) return b;
    if(p%2==1) return mult(b,bigmod(b,p-1));
    matrix res=bigmod(b,p/2);
    res=mult(res,res);
    return res;
}

int main()
{
    LL i,j,k,n,m,d,test,t=0;
    f();
    scanf("%lld",&test);
    while(test--)
    {
        scanf("%lld%lld%lld%lld",&aa,&bb,&nn,&mm);
        mod=1;
        for(i=0;i<mm;i++) mod=mod*10;
        matrix mat=bigmod(base,nn-1);
        matrix pp;
        pp.row=2; pp.col=1;
        pp.a[0][0]=bb; pp.a[1][0]=aa;
        mat=mult(mat,pp);
        printf("%lld\n",mat.a[0][0]);
    }
    return 0;
}

Matrix Exponentiation-2[Index ]


/*
Algorithm: Matrix Exponentiation
Problem: Lightoj-1096
f(n)=a*f(n-1)+b*f(n-3)+c, if(n > 2)
    =0, if(n ≤ 2)
*/

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

int mod=10007;
struct matrix
{
    int mat[5][5];
    int row,col;
    matrix(){}
    matrix(int x,int y)
    {
        row=4; col=4;
        memset(mat,0,sizeof(mat));
        mat[0][0]=x; mat[0][2]=y;
        mat[0][3]=mat[1][0]=mat[2][1]=mat[3][3]=1;
    }
};

matrix mult(matrix &x,matrix &y)
{
    matrix r;
    r.row=x.row;
    r.col=y.col;
    for(int i=0;i<r.row;i++)
    {
        for(int j=0;j<r.col;j++)
        {
            int sum=0;
            for(int k=0;k<x.col;k++)
                sum=sum+x.mat[i][k]*y.mat[k][j];
            r.mat[i][j]=sum%mod;
        }
    }
    return r;
}

matrix bigmod(matrix b,int p)
{
    if(p==1) return b;
    matrix res=bigmod(b,p>>1);
    res=mult(res,res);
    if(p&1) res=mult(res,b);
    return res;
}

int main()
{
    int i,j,k,n,m,d,test,t=0,a,b,c;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d%d%d%d",&n,&a,&b,&c);
        if(n<3)
        {
            printf("Case %d: 0\n",++t);
            continue;
        }
        matrix base(a,b);
        matrix xx=bigmod(base,n-2);
        int ans=(xx.mat[0][3]*c)%mod;
        printf("Case %d: %d\n",++t,ans);
    }
    return 0;
}

Union-Find(Cycle Checking)[Index ]


/*
Algorithm: Union Find
Problem: Given a graph G(V,E). You have to say whether
         the graph is a tree or not.
*/
#include<bits/stdc++.h>
using namespace std;

int pr[10009];
bool flag=0;

int find_parent(int u)
{
    if(pr[u]==u) return u;
    return pr[u]=find_parent(pr[u]);
}

void Union(int x,int y)
{
    int px=find_parent(x);
    int py=find_parent(y);
    if(px!=py) pr[px]=py;
    if(px==py) flag=1;  // if px==py that means the parent of x and y is same
                        // Hence cycle exist in this graph
}

int main()
{
    int i,j,k,node,edge,x,y;
    while(cin>>node>>edge)
    {
        for(i=0;i<10005;i++)
            pr[i]=i;
        flag=0;
        for(i=0;i<edge;i++)
        {
            cin>>x>>y;
            Union(x,y);
        }
        if(flag) puts("NO");
        else puts("YES");
    }
    return 0;
}

Matrix Exponentiation-3[Index ]


/*
Algorithm: Matrix Exponentiation
Problem  : http://uva.onlinejudge.org/external/125/12593.html
Hints:   F(n,k)=F(n-1,k-1)
         F(n,1)=F(n-1,2)+F(n-1,3)+......+F(n-1,k)
         where F(n,k)=Number of Macaws of exactly k-year in n-th year.
*/

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

LL kk;
LL mod=10007;

struct matrix
{
    LL mat[104][104];
    LL row,col;
    matrix(){};
    matrix(LL k)
    {
        row=k; col=k;
        memset(mat,0,sizeof(mat));
        for(LL i=0;i<k-1;i++)
            mat[i][i+1]=1;
        for(LL i=1;i<k-1;i++)
            mat[k-1][i]=1;
    }
    void identity(LL k)
    {
        row=k; col=k;
        memset(mat,0,sizeof(mat));
        for(LL i=0;i<k;i++)
            mat[i][i]=1;
    }
};

matrix mult(matrix &x,matrix &y)
{
    matrix r;
    r.row=x.row;
    r.col=y.col;
    for(LL i=0;i<r.row;i++)
    {
        for(LL j=0;j<r.col;j++)
        {
            LL sum=0;
            for(LL k=0;k<x.col;k++)
                sum=sum+x.mat[i][k]*y.mat[k][j];
            r.mat[i][j]=sum%mod;
        }
    }
    return r;
}

matrix bigmod(matrix b,LL p)
{
    matrix res;
    res.identity(kk);
    while(p)
    {
        if(p&1) res=mult(res,b);
        b=mult(b,b);
        p=p>>1;
    }
    return res;

}

void Print(matrix x)
{
    for(LL i=0;i<x.row;i++)
    {
        for(LL j=0;j<x.col;j++)
            printf("%lld ",x.mat[i][j]);
        puts("");
    }
}

int main()
{
    LL i,j,k,n,m,d,test,t=0;
    scanf("%lld",&test);
    while(test--)
    {
        scanf("%lld%lld",&n,&k);
        k++;
        kk=k;
        matrix base(k);
        matrix xx=bigmod(base,n-1);
        //Print(xx);
        LL ans=0;
        for(i=1;i<k;i++)
            ans=(ans+xx.mat[i][k-1])%mod;
        printf("Case %lld: %lld\n",++t,(ans*2)%mod);
    }
    return 0;
}

Matrix Exponentiation-4(with precalculate)[Index]


/*
Algorithm: Matrix Exponentiation with Pre-calculation
Problem: http://www.spoj.com/problems/FLIB/
Discussion: http://codeforces.com/blog/entry/12260#comments
*/

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

LL mod=1000000007;

struct matrix
{
    LL mat[4][4];
    LL row,col;
    void init()
    {
        row=3; col=3;
        mat[1][0]=mat[2][0]=0;
        mat[0][0]=1;
        mat[2][2]=2;
        mat[0][2]=mat[1][2]=mat[2][1]=3;
        mat[0][1]=mat[1][1]=5;
    }
    void identity()
    {
        row=3; col=3;
        memset(mat,0,sizeof(mat));
        for(LL i=0;i<3;i++)
            mat[i][i]=1;
    }
};

matrix pre_calculate[55];
LL have[55];

matrix mult(matrix &x,matrix &y)
{
    matrix r;
    r.row=x.row;
    r.col=y.col;
    for(LL i=0;i<r.row;i++)
    {
        for(LL j=0;j<r.col;j++)
        {
            LL sum=0;
            for(LL k=0;k<x.col;k++)
                sum=sum+x.mat[i][k]*y.mat[k][j];
            r.mat[i][j]=sum%mod;
        }
    }
    return r;
}

matrix bigmod(matrix b,LL p)
{
    if(p==1) return b;
    matrix res=bigmod(b,p>>1);
    res=mult(res,res);
    if(p&1) res=mult(res,b);
    return res;
}
void calc()
{
    have[0]=1;
    for(LL i=1;i<=51;i++)
        have[i]=have[i-1]*2;
    matrix base;
    base.init();
    LL dd=1;
    for(LL i=0;i<=51;i++)
    {
        if(dd==1)  pre_calculate[i+1]=base;
        else pre_calculate[i+1]=bigmod(base,dd);
        dd=dd*2;
    }
}

int main()
{
    LL i,j,k,n,m,d,test,t=0;
    calc();
    scanf("%lld",&test);
    while(test--)
    {
        scanf("%lld",&n);
        if(n==0)
        {
            printf("0\n");
            continue;
        }
        if(n==1)
        {
            printf("2\n");
            continue;
        }
        n--;
        matrix xx;
        xx.identity();
        for(i=51;i>=0;i--)
        {
            if(have[i]<=n)
            {
                n=n-have[i];
                xx=mult(xx,pre_calculate[i+1]);
            }
        }
        LL res=(xx.mat[0][0]*2+xx.mat[0][1]*2+xx.mat[0][2])%mod;
        printf("%lld\n",res);
    }
    return 0;
}

KMP[Index]


/*
Algorithm: KMP
Some Definition:
1) lps[k]=v, longest prefix ans suffix of first k characters
   where prefix=suffix
2) q= Number of characters matched
*/

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

int lps[100009];

void prefix_function(char *p)
{
    int m=strlen(p+1);
    lps[1]=0;
    int q=0;
    for(int k=2;k<=m;k++)
    {
        while(q>0&&p[q+1]!=p[k])
            q=lps[q];
        if(p[q+1]==p[k]) q++;
        lps[k]=q;
    }
}

int match(char *t, char *p)
{
    int n=strlen(t+1);
    int m=strlen(p+1);
    int co=0;
    int q=0;
    for(int i=1;i<=n;i++)
    {
        while(q>0&&t[i]!=p[q+1])
            q=lps[q];
        if(t[i]==p[q+1]) q++;
        if(q==m)
        {
            co++;
            q=lps[q];
        }
    }
    return co;
}

int main()
{
    int i,j,k,d;
    char s1[100009],s2[100009];
    while(scanf("%s%s",s1+1,s2+1)==2)
    {
        prefix_function(s2);
        int ans=match(s1,s2);
        printf("Number of substrings matched=%d\n",ans);
    }
    return 0;
}

Add Two Big Number[Index]


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

string bignumadd(string x,string y)
{
    string add="";
    int nn=x.size();
    int mm=y.size();
    reverse(x.begin(),x.end());
    reverse(y.begin(),y.end());
    if(nn<mm)
    {
        for(int i=0;i<mm-nn;i++)
            x=x+'0';
    }
    else
    {
        for(int i=0;i<nn-mm;i++)
            y=y+'0';
    }
    int carry=0;
    nn=max(nn,mm);
    for(int i=0;i<nn;i++)
    {
        int d=(x[i]-'0')+(y[i]-'0')+carry;
        if(d<10)
        {
            char ch=d+'0';
            add=add+ch;
            carry=0;
        }
        else
        {
            if(i==nn-1)
            {
                char ch=d%10+'0';
                add=add+ch+'1';
                continue;
            }
            carry=1;
            char ch=d%10+'0';
            add=add+ch;
        }
    }
    reverse(add.begin(),add.end());
    return add;
}

int main()
{
    string s1,s2;
    while(cin>>s1>>s2)
    {
        string ans=bignumadd(s1,s2);
        cout<<ans<<endl;
    }
    return 0;
}

Segment Tree-3[Index]

/*
SPOJ Problem: GSS1
Problem Summary: You are given a sequence A[1], A[2], ..., A[N].
( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows:
Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }.
Given M queries, your program must output the results of these queries.
*/

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define max3(a,b,c) max(a,max(b,c))
#define max4(a,b,c,d) max(max(a,b),max(c,d))

int inf=1500008;

struct info
{
    int segsum,leftsum,rightsum,maxsum;
};

info tree[200009];
int a[50009];

info merge(info l,info r)
{
    info ret;
    ret.segsum=l.segsum+r.segsum;
    ret.leftsum=max4(l.segsum,l.leftsum,l.segsum+r.leftsum,l.segsum+r.segsum);
    ret.rightsum=max4(r.segsum,r.rightsum,r.segsum+l.rightsum,r.segsum+l.segsum);
    ret.maxsum=max3(l.maxsum,r.maxsum,l.rightsum+r.leftsum);
    return ret;
}

void init(int node,int b,int e)
{
    if(b==e)
    {
        tree[node].leftsum=a[b];
        tree[node].rightsum=a[b];
        tree[node].maxsum=a[b];
        tree[node].segsum=a[b];
        return;
    }
    int left=node<<1;
    int right=left+1;
    int mid=(b+e)>>1;
    init(left,b,mid);
    init(right,mid+1,e);
    tree[node]=merge(tree[left],tree[right]);
}

info query(int node,int b,int e,int i,int j)
{
    info ret;
    if(b>j||e<i)
    {
        ret.leftsum=-inf;
        ret.rightsum=-inf;
        ret.segsum=-inf;
        ret.maxsum=-inf;
        return ret;
    }
    if(b>=i&&e<=j) return tree[node];
    int left=node<<1;
    int right=left+1;
    int mid=(b+e)>>1;
    info p1=query(left,b,mid,i,j);
    info p2=query(right,mid+1,e,i,j);
    ret=merge(p1,p2);
    return ret;

}

int main()
{
    int i,j,k,n,m,d,test,t=0,x,y,q;
    while(scanf("%d",&n)==1)
    {
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        init(1,1,n);
        scanf("%d",&q);
        while(q--)
        {
            scanf("%d%d",&x,&y);
            info ans=query(1,1,n,x,y);
            printf("%d\n",ans.maxsum);
        }
    }
    return 0;
}

Segment Tree-4(With Lazy)[Index]

/*
Algorithm Used: Segment Tree With Lazy Propagation
Problem Link: http://codeforces.com/contest/52/problem/C
*/

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

const LL inf = (1LL<<62);

struct data
{
    LL lazy, mn;
};

LL a[200001];
data tree[200000*4];

void init(LL node, LL b,LL e)
{
    if(b == e)
    {
        tree[node].lazy = 0;
        tree[node].mn = a[b];
        return;
    }
    LL left=node<<1,right=(node<<1)+1,mid=(b+e)>>1;
    init(left,b,mid);
    init(right,mid+1,e);
    tree[node].mn = min(tree[left].mn+tree[left].lazy,tree[right].mn+tree[right].lazy);
}

void push(LL node)
{
    LL left=node<<1,right=(node<<1)+1;
    tree[left].lazy += tree[node].lazy;
    tree[right].lazy += tree[node].lazy;
    tree[node].lazy = 0;
}

void update(LL node, LL b, LL e, LL i, LL j, LL val)
{
    if( b > j || e < i ) return;
    if( b >= i && e <= j )
    {
        tree[node].lazy += val; return;
    }
    LL left=node<<1,right=(node<<1)+1,mid=(b+e)>>1;
    push(node);
    update(left,b,mid,i,j,val);
    update(right,mid+1,e,i,j,val);
    tree[node].mn = min(tree[left].mn+tree[left].lazy,tree[right].mn+tree[right].lazy);
}

LL query(LL node ,LL b, LL e, LL i, LL j)
{
    if( b > j || e < i ) return inf;
    if( b >= i && e <= j )
    {
        return tree[node].lazy + tree[node].mn;
    }
    LL left=node<<1,right=(node<<1)+1,mid=(b+e)>>1;
    push(node);
    LL ret = min( query(left,b,mid,i,j),query(right,mid+1,e,i,j) );
    tree[node].mn = min(tree[left].mn+tree[left].lazy,tree[right].mn+tree[right].lazy);
    return ret;
}

int main()
{
    LL i,j,k,n,m,d,q;
    int x,y,z;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    init(1,1,n);
    cin>>q;
    getchar();
    char s[30];
    while(q--)
    {
        gets(s);
        d=sscanf(s,"%d%d%d",&x,&y,&z);
        LL ans;
        x++; y++;
        if(d==2)
        {
            if(y<x) ans=min(query(1,1,n,x,n),query(1,1,n,1,y));
            else ans=query(1,1,n,x,y);
            cout<<ans<<"\n";
        }
        else
        {
            if(y<x)
            {
                update(1,1,n,x,n,z);
                update(1,1,n,1,y,z);
            }
            else update(1,1,n,x,y,z);
        }
    }
    return 0;
}

Segment Tree-5(With Lazy)[Index]

/*
Algorithm Used: Segment Tree with Lazy Propagation
Problem Link: http://lightoj.com/volume_showproblem.php?problem=1183
*/

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

struct info
{
    int lazy,sum;
};

info tree[400009];

void init(int node,int b,int e)
{
    if(b==e)
    {
        tree[node].lazy=-1;
        tree[node].sum=0;
        return;
    }
    int left=node<<1,right=(node<<1)+1,mid=(b+e)>>1;
    init(left,b,mid);
    init(right,mid+1,e);
    tree[node].sum=tree[left].sum+tree[right].sum;
}

void push(int node,int b,int e)
{
    int left=node<<1,right=(node<<1)+1,mid=(b+e)>>1;
    tree[left].lazy=tree[node].lazy;
    tree[left].sum=(mid-b+1)*tree[node].lazy;
    tree[right].lazy=tree[node].lazy;
    tree[right].sum=(e-mid)*tree[node].lazy;
    tree[node].lazy=-1;
}

void update(int node,int b,int e,int i,int j,int val)
{
    if(b>j||e<i) return;
    if(b>=i&&e<=j)
    {
        tree[node].lazy=val;
        tree[node].sum=(e-b+1)*val;
        return;
    }
    if(tree[node].lazy!=-1) push(node,b,e);
    int left=node<<1,right=(node<<1)+1,mid=(b+e)>>1;
    update(left,b,mid,i,j,val);
    update(right,mid+1,e,i,j,val);
    tree[node].sum=tree[left].sum+tree[right].sum;
}

int query(int node,int b,int e,int i,int j)
{
    if(b>j||e<i) return 0;
    if(b>=i&&e<=j&&tree[node].lazy!=-1)
    {
        return tree[node].sum;
    }
    if(tree[node].lazy!=-1) push(node,b,e);
    int left=node<<1,right=(node<<1)+1,mid=(b+e)>>1;
    int p1=query(left,b,mid,i,j);
    int p2=query(right,mid+1,e,i,j);
    tree[node].sum=tree[left].sum+tree[right].sum;
    return p1+p2;
}

int main()
{
    int i,j,k,n,m,d,x,y,z,test,t=0,q;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d%d",&n,&q);
        memset(tree,0,sizeof(tree));
        init(1,1,n);
        printf("Case %d:\n",++t);
        while(q--)
        {
            scanf("%d%d%d",&d,&x,&y);
            if(d==1)
            {
                scanf("%d",&z);
                update(1,1,n,x+1,y+1,z);
            }
            else
            {
                int ans=query(1,1,n,x+1,y+1);
                int pp=y-x+1;
                if(ans%pp==0) printf("%d\n",ans/pp);
                else
                {
                    int g=__gcd(ans,pp);
                    printf("%d/%d\n",ans/g,pp/g);
                }
            }
        }
    }
    return 0;
}

Extended Euclid[Index]


/*
Algorithm: Extended Euclid Algorithm
           d=ax+by where d=GCD(a,b)
*/

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

int x,y,d;

void ex_euclid(int a,int b)
{
    if(b==0)
    {
        x=1; y=0; d=a;
        return;
    }
    ex_euclid(b,a%b);
    int temp=x;
    x=y;
    y=temp-(a/b)*x;
}
int main()
{
    int i,j,k,n,m,a,b;
    while(cin>>a>>b)
    {
        ex_euclid(a,b);
        cout<<x<<" "<<y<<" "<<d<<endl;
    }
    return 0;
}

Suffix Array[Index]


/*
Algorithm: Suffix Array
           An straight-forward problem: SPOJ SARRAY
*/

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

struct info
{
    int x,y,indx;
};
struct data
{
    int rank,index;
};
info h[100009];
char s[100009];
int p[22][100009],n,stp;
bool better(info p1, info p2)
{
    if(p1.x<p2.x) return 1;
    if(p1.x==p2.x&&p1.y<p2.y) return 1;
    return 0;
}
bool better2(data p1, data p2)
{
    if(p1.rank<p2.rank) return 1;
    if(p1.rank==p2.rank&&p1.index<p2.index) return 1;
    return 0;
}
void Parse_Table()
{
    for(int i=0;i<n;i++)
    {
        if(s[i]>='0'&&s[i]<='9')
            p[0][i]=s[i]-'0';
        else p[0][i]=s[i]-'A'+11;
    }
    for(int i=1;;i++)
    {
        int len=(1<<i);
        for(int j=0;j<n;j++)
        {
            h[j].x=p[i-1][j];
            int k=j+len/2;
            if(k<n) h[j].y=p[i-1][k];
            else h[j].y=-1;
            h[j].indx=j;
        }
        sort(h,h+n,better);
        int co=0;
        for(int j=0;j<n;j++)
        {
            if(j>0&&h[j].x==h[j-1].x&&h[j].y==h[j-1].y)
            p[i][h[j].indx]=p[i][h[j-1].indx];
            else p[i][h[j].indx]=co++;

        }
        if(len>=n)
        {
            stp=i;
            break;
        }
    }
}

int main()
{
    int i,j,k,m,d,test,t=0;
    while(scanf("%s",s)==1)
    {
        stp=0;
        n=strlen(s);
        Parse_Table();
        data suffix_array[100009];
        for(i=0;i<n;i++)
        {
            suffix_array[i].rank=p[stp][i];
            suffix_array[i].index=i;
        }
        sort(suffix_array,suffix_array+n,better2);
        for(i=0;i<n;i++)
            printf("%d\n",suffix_array[i].index);
    }
    return 0;
}

Upper Bound & Lower Bound[Index]


#include<bits/stdc++.h>

using namespace std;

int main()
{
    int i,j,k,n,m,d,a[]={10,20,30,30,20,10,10,20};
    vector<int>v(a,a+8);
    sort(v.begin(),v.end()); // after sort, 10 10 10 20 20 20 30 30
    int p=21;
    int q=15;
    int x=lower_bound(v.begin(),v.end(),p)-v.begin();    //x=first position from left 

where a[x]>=p
    int y=upper_bound(v.begin(),v.end(),q)-v.begin()-1;  //y=last position from left where 

a[y]<=q
    cout<<x<<endl;
    cout<<y<<endl;
}

/*
So (x,y) creates a segment where a[x],a[x+1]....a[y] values exists
and a[i]>=p&&a[i]<=q where i=[x,y];
*/

BigInteger Template[Index]


#include<bits/stdc++.h>
using namespace std;
/*
	This template is collected.
*/
/****************** BIG INT LIBRARY *****************************
getint()               : makes a new Biginteger from a int
Bigint()               : Constructor
Bigint(string b)       : Constructs a Biginteger from a string
size()                 : returns length of Biginteger
inverseSign()          : return the inverse of Biginteger
normalize()            : removes leading 0 and changes the sign
operator=              : available for int/Biginteger
operator<              : available for int/Biginteger
operator==             : available for int/Biginteger
operator+              : available for int/Biginteger
operator-              : available for int/Biginteger
operator*              : available for int/Biginteger
operator/              : available for int/Biginteger
operator%              : available for int/Biginteger
print()                : prints the Biginteger
sqrt()                 : returns the sqrt in the neares int
******************************************************************/
#define BIT 10009
#define GRP     5
#define RADIX   100000  // 10^GRP
#define PI         2.0*acos(0.0)
typedef complex<long double> Complex;

unsigned revtab[65536];
char mid_man[4000000];  //modify this in case of mle
void init()
{
    for (int x = 0; x < 65536; x++)
    {
        int y = 0;
        for (int i = 0; i < 16; i++)y |= ((x >> i) & 1) << (15 - i);
        revtab[x] = y;
    }
}
void FFT(Complex *a, int N, int dir)
{
    int lgN;
    for (lgN = 1; (1 << lgN) < N; lgN++);
    assert((1 << lgN) == N);
    for (unsigned i = 0; i < N; i++)
    {
        unsigned j = ((revtab[i & 65535] << 16) | revtab[i >> 16]) >> (32 - lgN);
        if (i < j) swap(a[i], a[j]);
    }
    for (int s = 1; s <= lgN; s++)
    {
        int m = 1 << s, h = m/2;
        Complex w, w_m = exp(Complex(0, dir*2*PI/m));
        for (int k = 0; k < N; k += m)
        {
            w = 1;
            for (int j = 0; j < h; j++)
            {
                Complex t = w * a[k+h+j];
                a[k+h+j] = a[k+j] - t;
                a[k+j] += t;
                w *= w_m;
            }
        }
    }
}
void parse(vector<Complex> &v, const char *s)
{
    int n = strlen(s);
    int m = (n + GRP-1) / GRP;
    v.resize(m);
    for (int i = 0; i < m; i++)
    {
        int b = n - GRP * i, x = 0;
        for (int a = max(0, b - GRP); a < b; a++)x = x * 10 + s[a] - '0';
        v[i] = x;
    }
}
void Extract(const vector<Complex> &v,int signa,int signb)
{
    int i, N = v.size();
    vector<long long> digits(N + 1, 0);
    long double err = 0;
    for (i = 0; i < N; i++)
    {
        long long x = (long long)(v[i].real() + 0.5);
        err = max(err, abs(x - v[i].real()));
        err = max(err, abs(v[i].imag()));
        digits[i] = x;
    }
    long long c = 0;
    for (i = 0; i < N; i++)
    {
        c += digits[i];
        digits[i] = c % RADIX;
        c /= RADIX;
    }
    assert(c == 0);
    for (i = N - 1; i > 0 && digits[i] == 0; i--);
    int idx = 0,blen = 0;
    char buff[30];
    sprintf(buff, "%lld", digits[i]);
    if(signa != signb) mid_man[idx++] = '-';
    while(buff[blen] != '\0')mid_man[idx++] = buff[blen++];
    for (i--; i >= 0; i--)
    {
        sprintf(buff, "%.*lld", GRP, digits[i]);
        blen=0;
        while(buff[blen] != '\0') mid_man[idx++] = buff[blen++];
    }
    mid_man[idx] = '\0';
}
void mul(string &xx,string &yy,int signa,int signb)
{
    vector<Complex> A, B;
    parse( A, xx.c_str() );
    parse( B, yy.c_str() );
    int N = 1;
    while (N < max(A.size(), B.size())) N *= 2;
    N *= 2;
    A.resize(N);
    B.resize(N);
    FFT( &A[0], N, +1 );
    FFT( &B[0], N, +1 );
    for (int i = 0; i < N; i++) A[i] *= B[i];
    FFT( &A[0], N, -1);
    for (int i = 0; i < N; i++) A[i] /= N;
    Extract( A, signa, signb );
}
template<class T> string toString(T n)
{
    ostringstream ost;
    ost << n;
    ost.flush();
    return ost.str();
}
int iniflag;
struct Bigint
{
    // representations and structures
    string a; // to store the digits
    int sign; // sign = -1 for negative numbers, sign = 1 otherwise

    void getInt()
    {
        a.clear();
        char ch;
        while(true)
        {
            ch=getchar();
            if(ch=='\n' || ch==' ')break;
            a.push_back(ch);
        }
        (*this) = a;
    }

    // constructors
    Bigint()
    {
        if(!iniflag)
        {
            init();    // default constructor
            iniflag=1;
        }
    }
    Bigint( string b )
    {
        if(!iniflag)
        {
            init();
            iniflag=1;
        }
        (*this) = b;   // constructor for string
    }

    // some helpful methods
    int size()
    {
        return a.size();
    }
    Bigint inverseSign()
    {
        Bigint ret;
        ret.a = this->a;
        ret.sign = sign * -1;
        return ret;
    }
    // changes the sign
    Bigint normalize( int newSign )    // removes leading 0, fixes sign
    {
        for( int i = a.size() - 1; i > 0 && a[i] == '0'; i-- )a.erase(a.begin() + i);
        sign = ( a.size() == 1 && a[0] == '0' ) ? 1 : newSign;
        return (*this);
    }

    void operator = ( int b )
    {
        (*this)=toString(b);
    }
    // assignment operator
    void operator = ( string b )
    {
        a = b[0] == '-' ? b.substr(1) : b;
        reverse( a.begin(), a.end() );
        sign = ( b[0] == '-' ) ? -1 : 1;
    }

    // conditional operators
    bool operator < ( const Bigint &b ) const    // less than operator
    {
        if( sign != b.sign ) return sign < b.sign;
        if( a.size() != b.a.size() )return sign == 1 ? a.size() < b.a.size() : a.size() > 

b.a.size();
        for( int i = a.size() - 1; i >= 0; i-- ) if( a[i] != b.a[i] )return sign == 1 ? a

[i] < b.a[i] : a[i] > b.a[i];
        return false;
    }
    bool operator < ( const int &b ) const
    {
        return (*this) < toString(b);
    }
    bool operator == ( const Bigint &b ) const    // operator for equality
    {
        return a == b.a && sign == b.sign;
    }
    bool operator == ( const long long &b ) const
    {
        return (*this) == toString(b);
    }

    // mathematical operators
    Bigint operator + ( Bigint b )    // addition operator overloading
    {
        if( sign != b.sign )
        {
            if((*this) < b)return b - (*this).inverseSign();
            return (*this) - b.inverseSign();
        }
        Bigint c;
        for(int i = 0, carry = 0; i<a.size() || i<b.size() || carry; i++ )
        {
            carry+=(i<a.size() ? a[i]-48 : 0)+(i<b.a.size() ? b.a[i]-48 : 0);
            c.a += (carry % 10 + 48);
            carry /= 10;
        }
        return c.normalize(sign);
    }
    Bigint operator + ( long long b )
    {
        return (*this) + toString(b);
    }

    Bigint operator - ( Bigint b )    // subtraction operator overloading
    {
        if( sign != b.sign ) return (*this) + b.inverseSign();
        int s = sign;
        sign = b.sign = 1;
        Bigint c;
        if( (*this) < b )
        {
            c = ((b - (*this)).inverseSign()).normalize(-s);
            sign = b.sign = s;
            return c;
        }
        for( int i = 0, borrow = 0; i < a.size(); i++ )
        {
            borrow = a[i] - borrow - (i < b.size() ? b.a[i] : 48);
            c.a += borrow >= 0 ? borrow + 48 : borrow + 58;
            borrow = borrow >= 0 ? 0 : 1;
        }
        sign = b.sign = s;
        return c.normalize(s);
    }
    Bigint operator - ( long long  b )
    {
        return (*this) - toString(b);
    }

    Bigint operator * ( Bigint b )    // multiplication operator overloading
    {
        reverse( a.begin(), a.end() );
        reverse( b.a.begin(), b.a.end() );
        mul(a,b.a,this->sign,b.sign);
        reverse( a.begin(), a.end() );
        reverse( b.a.begin(), b.a.end() );
        return Bigint((string)mid_man);
    }
    Bigint operator * ( long long b )
    {
        return (*this) * toString(b);
    }

    Bigint operator / ( Bigint b )    // division operator overloading BI/BI
    {
        if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 );
        Bigint c("0"), d;
        for( int j = 0; j < a.size(); j++ ) d.a += "0";
        int dSign = sign * b.sign;
        b.sign = 1;
        for( int i = a.size() - 1; i >= 0; i-- )
        {
            c.a.insert( c.a.begin(), '0');
            c = c + a.substr( i, 1 );
            while( !( c < b ) ) c = c - b, d.a[i]++;
        }
        return d.normalize(dSign);
    }
    Bigint operator / ( long long n )    // division operator overloading BI/BI
    {
        reverse( a.begin(), a.end() );
        long long int rem = 0;
        int f = 1;
        int idx = 0;
        int len = a.length();
        for(int i = 0; i < len; i++)
        {
            rem = a[i]-'0' + rem * 10;
            if(rem/n != 0) f = 0;
            if(f == 0) mid_man[idx++] = ((char)((rem/n)+'0'));
            rem = rem % n;
        }
        if(f == 1) mid_man[idx++] = '0';
        mid_man[idx] = '\0';
        reverse( a.begin(), a.end() );
        return Bigint( (string)mid_man );
    }
    Bigint operator % ( Bigint b )    // modulo operator overloading
    {
        if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 );
        Bigint c("0");
        b.sign = 1;
        for( int i = a.size() - 1; i >= 0; i-- )
        {
            c.a.insert( c.a.begin(), '0');
            c = c + a.substr( i, 1 );
            while( !( c < b ) ) c = c - b;
        }
        return c.normalize(sign);
    }
    Bigint operator % ( long long n )   // modulo operator overloading
    {
        reverse( a.begin(), a.end() );
        long long int rem = 0;
        int idx = 0;
        int len = a.length();
        for(int i = 0; i < len; i++)
        {
            rem = a[i]-'0' + rem * 10;
            rem = rem % n;
        }
        reverse( a.begin(), a.end() );
        return Bigint( toString(rem) );
    }
    void print()
    {
        if( sign == -1 ) putchar('-');
        for( int i = a.size() - 1; i >= 0; i-- ) putchar(a[i]);
    }
    Bigint sqrt()
    {
        reverse( this->a.begin(), this->a.end() );
        string a=this->a;
        int idx=0;
        int n = a.size();
        bool f = n%2;
        n = (f) ? n+1 : n;
        vector <int> num (n, 0);
        int i;
        if (f)for (i = 0; i < n-1; i++) num[i+1] = a[i] - 48;
        else for (i = 0; i < n; i++) num[i] = a[i] - 48;
        n /= 2;
        vector <int> root(n, 0);
        vector <int> recieve;
        for (i = 0; i < n; i++)
        {
            recieve.push_back ( num[i*2] );
            recieve.push_back ( num[i*2+1] );
            vector <int> cand(i+1, 0);
            int tmp, ac = 0;
            for (int j = i; j > 0; j--)
            {
                tmp = root[j-1] * 2 + ac;
                cand[j] = tmp % 10;
                ac = tmp / 10;
            }
            if (ac) cand[0] += ac;
            int j;
            for (j = 9; j >= 0; j--)
            {
                int l = 2 * (i+1);
                vector <int>  m (l, 0);
                m[l - 1] = j * j;
                m[l - 2] = m[l - 1] / 10;
                m[l - 1] %= 10;
                int k, o;
                int ac = 0;
                for (k = l - 2, o = i; o >= 0 && k > 0; k--, o--)
                {
                    m[k] += cand[o] * j;
                    m[k-1] = m[k] / 10;
                    m[k] %= 10;
                }
                bool flag = 1;
                for (k = 0; k < l; k++)
                {
                    if (recieve[k] > m[k]) break;
                    if (recieve[k] < m[k])
                    {
                        flag = 0;
                        break;
                    }
                }
                if (flag)
                {
                    ac = 0;
                    for (k = l-1; k >= 0; k--)
                    {
                        tmp = recieve[k] - m[k] - ac;
                        if (tmp < 0)recieve[k] = tmp+10,ac = 1;
                        else recieve[k] = tmp;
                        ac = 0;
                    }
                    break;
                }
            }
            root[i] = j;
            mid_man[idx++] = (j+'0');
        }
        mid_man[idx] = '\0';
        reverse( this->a.begin(), this->a.end() );
        return Bigint( string(mid_man) );
    }
};
istream& operator >> (istream &in, Bigint &x)
{
    in >> x.a;
    x=Bigint(x.a);
    return in;
}
ostream& operator << (ostream &out, const Bigint &x)
{
    string p=x.a;
    reverse(p.begin(),p.end());
    if(x.sign==-1)p="-"+p;
    out << p;
    return out;
}

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    int test;
    cin>>test;
    while(test--)
    {
        Bigint A,B;
        cin>>A>>B;
        cout<<(A*B)<<endl;
        cout<<(A+B)<<endl;
        cout<<(A/B)<<endl;
        cout<<(A%B)<<endl;
    }
    return 0;
}

Multiplication of a large number with a integer[Index]


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

string multiply( string s, int b )
{
    /* multiplication when one is large number and other is integer.
      The result is stored in s in reverse order. */
    int carry = 0;
    for( int i = 0; i < s.size(); i++ )
    {
        carry += (s[i] - 48) * b;
        s[i] = ( carry % 10 + 48 );
        carry /= 10;
    }
    while( carry )
    {
        s += ( carry % 10 + 48 );
        carry /= 10;
    }
    return s;
}

int main()
{
    int test,i,j,d,n,t=0;
    while(cin>>n)
    {
        string ans="1";
        for(i=0;i<n;i++)
        {
            cin>>d;
            ans=multiply(ans,d);
        }
        reverse(ans.begin(),ans.end());
        cout<<ans<<endl;
    }
    return 0;
}

Binary Indexed Tree[Index]


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

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

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

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

int main()
{
    int i,j,k,q,m,d,test,t=0,x,y,z;
    scanf("%d",&test);
    while(test--)
    {
        memset(tree,0,sizeof(tree));
        scanf("%d%d",&n,&q);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&d);
            update(i,d);
        }
        printf("Case %d:\n",++t);
        while(q--)
        {
            scanf("%d",&d);
            if(d==1)
            {
                scanf("%d",&x);
                int ans=query(x+1)-query(x);
                printf("%d\n",ans);
                update(x+1,-ans);
            }
            else if(d==2)
            {
                scanf("%d%d",&x,&y);
                update(x+1,y);
            }
            else
            {
                scanf("%d%d",&x,&y);
                printf("%d\n",query(y+1)-query(x));
            }
        }
    }
    return 0;
}

Segment Tree-6(With Lazy)[Index]


/*
Problem : http://lightoj.com/volume_showproblem.php?problem=1135
*/

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

struct info
{
    int zero,one,two,lazy;
};

info tree[400009];

info Merge(info l,info r)
{
    info ret;
    ret.lazy=0;
    ret.one=l.one+r.one;
    ret.two=l.two+r.two;
    ret.zero=l.zero+r.zero;
    return ret;
}

void init(int node,int b,int e)
{
    if(b==e)
    {
        tree[node].lazy=0;
        tree[node].one=0;
        tree[node].two=0;
        tree[node].zero=1;
        return;
    }
    int left=node<<1; int right=left+1; int mid=(b+e)>>1;
    init(left,b,mid);
    init(right,mid+1,e);
    tree[node]=Merge(tree[left],tree[right]);
}

void PushDown(int node,int b,int e)
{
    int left=node<<1; int right=left+1; int mid=(b+e)>>1;
    tree[left].lazy+=tree[node].lazy;
    tree[right].lazy+=tree[node].lazy;
    if(tree[node].lazy%3==1)
    {
        int t1=tree[left].one;
        int t2=tree[left].two;
        tree[left].one=tree[left].zero;
        tree[left].zero=t2;
        tree[left].two=t1;

        t1=tree[right].one;
        t2=tree[right].two;
        tree[right].one=tree[right].zero;
        tree[right].zero=t2;
        tree[right].two=t1;
    }
    else if(tree[node].lazy%3==2)
    {
        int t1=tree[left].one;
        int t2=tree[left].two;
        tree[left].two=tree[left].zero;
        tree[left].one=t2;
        tree[left].zero=t1;

        t1=tree[right].one;
        t2=tree[right].two;
        tree[right].two=tree[right].zero;
        tree[right].one=t2;
        tree[right].zero=t1;
    }

    tree[node].lazy=0;
}

void update(int node,int b,int e,int i,int j)
{
    if(b>j||e<i) return;
    if(b>=i&&e<=j)
    {
        tree[node].lazy++;
        int t1=tree[node].one;
        int t2=tree[node].two;
        tree[node].one=tree[node].zero;
        tree[node].zero=t2;
        tree[node].two=t1;
        return;
    }
    int left=node<<1; int right=left+1; int mid=(b+e)>>1;
    if(tree[node].lazy) PushDown(node,b,e);
    update(left,b,mid,i,j);
    update(right,mid+1,e,i,j);
    tree[node]=Merge(tree[left],tree[right]);
}

int query(int node,int b,int e,int i,int j)
{
    if(b>j||e<i) return 0;
    if(b>=i&&e<=j) return tree[node].zero;
    int left=node<<1; int right=left+1; int mid=(b+e)>>1;
    if(tree[node].lazy) PushDown(node,b,e);
    int p1=query(left,b,mid,i,j);
    int p2=query(right,mid+1,e,i,j);
    tree[node]=Merge(tree[left],tree[right]);
    return p1+p2;
}

int main()
{
    int i,j,k,n,m,d,test,t=0,q,x,y;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d%d",&n,&q);
        init(1,1,n);
        printf("Case %d:\n",++t);
        while(q--)
        {
            scanf("%d%d%d",&d,&x,&y);
            if(d==0) update(1,1,n,x+1,y+1);
            else printf("%d\n",query(1,1,n,x+1,y+1));
        }
    }
    return 0;
}

Dijkstra With Printing Path[Index]


/*
    Algorithm: Dijkstra with Printing Path
    Straight-Forward Problem: http://codeforces.com/problemset/problem/20/C
*/

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

#define LL long long
LL dist[100009];
const LL inf=10000000000007;
LL parent[100009];

int main()
{
    LL i,j,k,n,m,d,x,y,z,source,node,edge,destination;
    while(cin>>node>>edge)
    {
        vector<pair<LL,LL> >adj[100009];
        for(i=0;i<edge;i++)
        {
            cin>>x>>y>>z;
            if(x==y) continue;
            adj[x].push_back(make_pair(y,z));
            adj[y].push_back(make_pair(x,z));
        }
        priority_queue<pair<LL,LL> >pq;
        vector<LL>path;
        for(i=0;i<=100002;i++)
        dist[i]=inf;
        dist[1]=0;
        source=1;
        destination=node;
        pq.push(make_pair(0,source));
        while(!pq.empty())
        {
            pair<LL,LL>p=pq.top(),pp;
            pq.pop();
            LL cost=p.first*-1;
            LL u=p.second;
            for(i=0;i<adj[u].size();i++)
            {
                pp=adj[u][i];
                LL v=pp.first;
                if(dist[v]>cost+pp.second)
                {
                    dist[v]=cost+pp.second;
                    parent[v]=u;
                    pq.push(make_pair(-dist[v],v));
                }
            }
        }
        if(dist[node]==inf) puts("-1");
        else
        {
            LL p=node;
            vector<LL>path;
            path.push_back(p);
            while(p!=1)
            {
                path.push_back(parent[p]);
                p=parent[p];
            }
            reverse(path.begin(),path.end());
            for(i=0;i<path.size();i++)
                cout<<path[i]<<" ";
            puts("");
        }
    }
    return 0;
}

Determining Is a point is Inside or Outside a Convex Polygon[Index]


/*
    Algorithm: This algorithm finds Is a point is inside a convex
    polygon or not.
    Note That:
            1) My algorithm assumes the points is given in
                CCW(Counter-Clock-Wise) direction.
            2) IsInConvex return true if Point P is inside the
                Polygon(Including edge), returns false otherwise.
            3) This algorithm only works for Convex Polygon.
            4) Complexity O(logN)
            5) Here V[] holds all the points of polygon.
*/

//Related Problem: http://codeforces.com/contest/166/problem/B
#include<bits/stdc++.h>
using namespace std;
#define LL long long

LL n,m;
struct Point
{
    LL x,y;
};
bool IsLeft(Point a,Point b,Point c)
{
    //checking if point c is left or right of line ab
    return ((a.x*b.y-b.x*a.y)+(b.x*c.y-c.x*b.y)+(c.x*a.y-a.x*c.y))>0;
}

LL TriangArea(Point a,Point b,Point c)
{
    return ((a.x*b.y-b.x*a.y)+(b.x*c.y-c.x*b.y)+(c.x*a.y-a.x*c.y));
}

bool IsInConvex(Point *v,Point p)
{
    /*
        Returns true if Point P is inside the Polygon V[].
        Otherwise returns false.
    */
	LL low=1,high=n-1;

	if(TriangArea(v[0],v[1],p)<0) return 0;
	if(TriangArea(v[n-1],v[0],p)<0) return 0;

	while(high-low>1)
	{
		LL mid=(low+high)/2;

		if(TriangArea(v[0],v[mid],p)>0) low=mid;
		else high=mid;
	}

	return TriangArea(v[low], v[high], p)>=0;
}

int main()
{
    LL i,j,k,d,test,aa,bb;
    Point a[100009];
    while(cin>>n)
    {
        for(i=0;i<n;i++)
        {
            cin>>aa>>bb;
            a[i].x=aa;
            a[i].y=bb;
        }
        cin>>m;
        for(i=0;i<m;i++)
        {
            cin>>aa>>bb;
            Point tt;
            tt.x=aa;
            tt.y=bb;
            if(IsInConvex(a,tt)) puts("Inside Convex Polygon");
            else puts("Outside Convex Polygon");
        }
    }
    return 0;
}

Area of Polygon[Index]


/*
    Area of a Polygon.
    Note That:
    1) Point p[] holds the points of the polygon.
    2) Points Must be Clock-Wise(CW) or Counter-Clock-Wise(CCW)
       direction.
*/

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

LL n,m;
struct Point
{
    LL x,y;
};

LL PolygonArea(Point *p)
{
    /*
        Actually this function returns area*2, so
        Actual Area=Return Value/2;
    */
    LL area=0;
    for(LL i=0;i<n;i++)
    {
        if(i==n-1) area=area+(p[i].x*p[0].y-p[0].x*p[i].y);
        else area=area+(p[i].x*p[i+1].y-p[i+1].x*p[i].y);
    }
    return abs(area);
}

int main()
{
    LL i,j,k,d,test,aa,bb;
    Point a[1009];
    while(cin>>n)
    {
        for(i=0;i<n;i++)
        {
            cin>>aa>>bb;
            a[i].x=aa;
            a[i].y=bb;
        }
        printf("Area of Polygon=%lld\n",PolygonArea(a));
    }
    return 0;
}

Backtracking (Permutation Generator)[Index]


/*
    Algorithm: Backtracking (Permutation Generator)
*/

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

bool taken[20];
int n;
vector<int>v;
void backtrack()
{
    if(v.size()==n)
    {
        printf("%d",v[0]);
        for(int i=1;i<v.size();i++)
            printf(" %d",v[i]);
        puts("");
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(taken[i]==0)
        {
            taken[i]=1;
            v.push_back(i);
            backtrack();
            taken[i]=0;
            v.pop_back();
        }
    }
}

int main()
{
    int i,j,k,m,d;
    while(scanf("%d",&n)==1)
    {
        backtrack();
    }
    return 0;
}

Coin Change[Index]


/*
    Problem: In a strange shop there are n types of coins of value A1, A2 ... An.
            You have to find the number of ways you can make K using the coins.
            Print the case number and the number of ways K can be made.
            Result can be large, so, print the result modulo 100000007.
            (LOJ-1232 - Coin Change (II))
    Algorithm: Dynamic Programming(Coin Change)
*/

#include<stdio.h>
long nways[10005];
int n,m;
int coins[105];
long coin_change(int n)
 {
     int i,taka;
     for(i=0;i<m;i++)
     {
         for(taka=1;taka<=n;taka++)
         {
             if(coins[i]<=taka)
             nways[taka]=nways[taka]%100000007+nways[taka-coins[i]]%100000007;
         }
     }
     return nways[n];
 }

int main()
{
    int i,count,t,test;
    scanf("%d",&test);
    for(t=1;t<=test;t++)
    {
        scanf("%d%d",&m,&n);
        nways[0]=1;
        for(i=1;i<=n;i++)
        nways[i]=0;
    for(i=0;i<m;i++)
    scanf("%d",&coins[i]);
    printf("Case %d: %ld\n",t,coin_change(n)%100000007);
    }
    return 0;
}

Checking Palindromes of All Sub-string[Index]


/*
    Problem: Given a sting S. Find all substring which are palindrome.
    Algorithm: Dynamic Programming
    Comment: dp[i][j]=1, if substring s[i,j] is palindrome
             dp[i][j]=0, if substring s[i,j] is not palindrome
*/

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

char s[1009];
bool dp[1009][1009];
int n;
void All_Pair_Palindrome_Check()
{
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++)
        dp[i][i]=1;
    for(int i=0;i<n-1;i++)
    {
        if(s[i]==s[i+1]) dp[i][i+1]=1;
    }
    for(int i=2;i<n;i++)
    {
        for(int j=0;j<n-i;j++)
        {
            int x=j,y=j+i;
            if(s[x]==s[y]&&dp[x+1][y-1]) dp[x][y]=1;
        }
    }
}
int main()
{
    int i,j,k,m,d,test;
    while(scanf("%s",s)==1)
    {
        n=strlen(s);
        All_Pair_Palindrome_Check();
        printf("The Substring Which Are Palindrome\n");
        for(i=0;i<n;i++)
        {
            for(j=0;j<n-i;j++)
            {
                int x=j,y=j+i;
                if(dp[x][y]) printf("%d %d\n",x+1,y+1);
            }
        }
    }
    return 0;
}

Lowest Common Ancestor[Index ]

/*
    Algorithm: LCA with Sparse Table
    Comment: sparse[i][j]=k means 2^j-th parent of node-i is k.
             parent[i]=j means j is the parent of node-i.
             level[i]=j means j is the level of node-i.
    Explanation: 1)http://www.shafaetsplanet.com/planetcoding/?p=1831
                 2)https://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
    Sample Input:
                9
                0 8
                0 3
                0 2
                0 1
                2 4
                4 5
                5 7
                5 6

                4
                3 2
                8 1
                7 6
                4 6
*/

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

int node;
int level[100009];
int sparse[100009][22]; //Sparse-Table
int parent[100009];
vector<int>adj[100009];
bool visited[100009];

void dfs(int x,int lev)
{
    if(visited[x]) return;
    visited[x]=1;
    level[x]=lev;
    for(int i=0;i<adj[x].size();i++)
    {
        int y=adj[x][i];
        parent[y]=x;
        if(visited[y]==0) dfs(y,lev+1);
    }
}
void lca_init()
{
    //we initialize every element in sparse-table with -1
    memset(sparse,-1,sizeof(sparse));

    ////the first ancestor of every node i is parent[i]
    for(int i=0;i<node;i++)
    sparse[i][0]=parent[i];

    //bottom up dynamic programing
    for(int j=1;(1<<j)<node;j++)
    {
        for(int i=0;i<node;i++)
        {
            if(sparse[i][j-1]!=-1)
                sparse[i][j]=sparse[sparse[i][j-1]][j-1];
        }
    }
}

int lca_query(int x,int y)
{
    //if x is situated on a higher level than y then we swap them
    if(level[x]<level[y]) swap(x,y);

    int log;
    //we compute the value of log(level[x])
    for(log =1;(1<<log)<=level[x];log++);
        log--;
    //taking x and y in same level
    for(int i=log;i>=0;i--)
    {
        if(level[x]-(1<<i)>=level[y])
            x=sparse[x][i];
    }
    if(x==y) return x;

    //we compute LCA(x, y) using the values in x
    for(int i=log;i>=0;i--)
    {
        if(sparse[x][i]!=-1&&sparse[x][i]!=sparse[y][i])
            x=sparse[x][i], y=sparse[y][i];
    }
    return parent[x];
}

int main()
{
    int i,j,k,n,m,d,test,x,y,q;
    while(scanf("%d",&node)==1)
    {
        for(i=0;i<node-1;i++)
        {
            scanf("%d%d",&x,&y);
            adj[x].push_back(y);
        }
        memset(visited,0,sizeof(visited));
        dfs(0,0);
        lca_init();
        scanf("%d",&q);
        while(q--)
        {
            scanf("%d%d",&x,&y);
            int lca=lca_query(x,y);
            printf("The Lowest Common Ancestor of node %d and node %d is %d\n",x,y,lca);
        }
    }
    return 0;
}

NCR(Binomial Cofficient-01)[Index ]

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

/*
When the result of NCR will fit in long long integer,
then we can use this code.
*/

LL NCR(int n,int r)
{
    if((n-r)<r) r=n-r;
    LL ret=1;
    for(int i=1;i<=r;i++,n--)
    {
        ret=ret*n;
        ret=ret/i;
    }
    return ret;
}

int main()
{
    int n,r;
    while(cin>>n>>r)
    {
        cout<<NCR(n,r)<<endl;
    }
    return 0;
}

NCR(Binomial Cofficient-02)[Index ]

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

/*
When the value of n will be less than 1000,
then we can calculate the value of NCR using DP.
*/

int dp[1009][1009];

void NCR()
{
    for(int n=0;n<=1000;n++)
    {
        for(int r=0;r<=1000;r++)
        {
            if(r==0) dp[n][r]=1;
            else if(r>n) dp[n][r]=0;
            else dp[n][r]=dp[n-1][r]+dp[n-1][r-1];
        }
    }
}

int main()
{
    int n,r;
    NCR();
    while(cin>>n>>r)
    {
        cout<<dp[n][r]<<endl;
    }
    return 0;
}

3 comments on “Code Library
  1. abm says:

    this is really awesome

  2. Anonymous says:

    nice

  3. Anonymous says:

    codemask give a treat for this awesome library. 😀

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: