Introduction to competitive programming

Trie can insert and search string in O(L) time where L is the length of string,this is much faster than hashtable and binary search tree implementations. Trie Node consist of a collection of Trie nodes and a boolean flag to check whether node is leaf or not.

Tutorial Links

Also Topcoder had excellent explanation about TRIE

Here is the C++ implementation of above Algorithm

/*
  TRIE implementation in C++
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ALPHABET_SIZE 26
using namespace std;
struct Node
{
 struct Node *child[ALPHABET_SIZE];
 bool isLeaf;
};
struct Node *createNode()
{
 Node *nw=new Node;
 for(int i=0;i<26;i++)
  nw->child[i]=NULL;
 nw->isLeaf=0;
 return nw;
}
void addWord(struct Node *root,string s)
{
 int len=s.length();
 struct Node *temp=root;
 for(int i=0;i<len;i++)
 {
  int c=s[i]-'a';
  if(temp->child[c]==NULL)
  {
   temp->child[c]=createNode();
  }
  temp=temp->child[c];
 }
 temp->isLeaf=1;
}
bool search(struct Node *root,string s)
{
 int len=s.length();
 struct Node *temp=root;
 for(int i=0;i<len;i++)
 {
  int c=s[i]-'a';
  if(temp->child[c]==NULL)
   return false;
  temp=temp->child[c];
 }
 if(temp->isLeaf)
  return true;
 else
  return false;
}
void printAllStrings(struct Node *root,string s)
{
 if(!root)
  return;
 if(root->isLeaf)
 {
  cout<<s<<"\n";
  return;
 }
 else
 {
  for(int i=0;i<26;i++)
  {
   if(root->child[i])
   {
 
    printAllStrings(root->child[i],s+(char)('a'+i));
   }
  }
 }
}
int main()
{
 struct Node *root=createNode();
 addWord(root,"abcd");
 addWord(root,"ace");
 if(search(root,"sai"))
  cout<<"Sai found\n";
 else
  cout<<"Sai not found\n";
 if(search(root,"abcd"))
  cout<<"abcd found\n";
 else
  cout<<"abcd not found\n";
 printAllStrings(root,"");
}
 

While learning Some advanced data structures I found Binary Index tree,One of the most intresting data Structure and easy to learn if we are familiar with some bit manipulation Techniques.

I found some tutorials on Internet with great Explanation.

Also Topcoder had excellent explanation about BIT

Here is the C++ implementation of above Algorithm

//C++ implementation of Binary Index Tree
//Array with N elements
//Construction of BIT
//Initialisation
//Updation
//Query Sum of elments in rangle l...r
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int a[100+1],BIT[100+1],n;
void init()//Initialisation of BIT
{
	for(int i=1;i<=n;i++)
	{
		int val=a[i];
		int idx=i;
		while(idx<=n)
		{
			BIT[idx]+=val;
			idx+=(idx & -idx);
		}
	}
	cout<<"After Initialisation \n";
	for(int i=1;i<=n;i++)
		cout<<BIT[i]<<" ";
	cout<<endl;
}
void update(int pos,int val)//Update the from that Position
{
	int idx=pos;
	while(idx<=n)
	{
		BIT[idx]+=val;
		idx+=(idx & -idx);
	}
	cout<<"After Updation \n";
	for(int i=1;i<=n;i++)
		cout<<BIT[i]<<" ";
	cout<<endl;
}
int query(int idx)
{
	int sum=0;
	while(idx>0)
	{
		sum+=BIT[idx];
		idx-=(idx & -idx);
	}
	return sum;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	memset(BIT,0,sizeof BIT);
	init();
	int q;
	cin>>q;	
	while(q--)
	{
		int t;
		cin>>t;
		if(t==1)
		{
			int x,val;
			cin>>x>>val;
			update(x,val);
		}
		else
		{
			int x,y;
			cin>>x>>y;
 
			cout<<query(y)-query(x-1)<<endl;
		}
 
	}
}

A node in a undirected graph is said to be an articulation point iff on removing the node disconnects the graph. Articulation Points are Vulnerabilities which on failure spits the network in to two or more components.

In the above graph on removing vertex A,B and G it will disconnect the graphs and hence they are Articulation Points.
In our Algorithm we use DFS to find the articulation points.Applying DFS on given graph we will get the DFS tree.
A vertex u in parent of vertex v,if u is adjacent to v i.e u is adjacent and discovered earlier than v.A leaf of DFS tree is never an articulation point
In DFS tree a vertex u is said to be an articulation point if any one of the following condition satisfies.
(a)u is the root of tree and it has more than one children.(Up on removing this vertex two disconnected components are formed).
(b)If any child of a node does not have back_edge to ancestor of its parent,then on removing disconnects the graph.
Handling first case is easy for every node count the child,if the node is the root and it have more than two children then it is the articulation point.
Second case is tricky.So we maintain a disc[] array to store the discovery time of each vertex.For every vertex rooted with u we need to find the earliest visited vertex so we maintain another array low[].

Here is the C++ implementation of above Algorithm

#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 102
vector<vector<int> >G(MAX);
int parent[MAX],low[MAX],disc[MAX],timer=0;
bool vis[MAX],ap[MAX];
void reset()
{
	for(int i=0;i<MAX;i++)
	{
		G[i].clear();
		vis[i]=false;
		ap[i]=false;
		parent[i]=-1;
	}
}
void dfs(int u)
{
	int child=0;
	vis[u]=true;
	disc[u]=low[u]=timer++;
	for(int i=0;i<G[u].size();i++)
	{	
 
		int v=G[u][i];
		if(!vis[v])
		{
			child++;
			parent[v]=u;
			dfs(v);
			low[u]=min(low[u],low[v]);
			if(parent[u]==-1 and child>1)
			{
			ap[u]=true;
			}
			if(parent[u]!=-1 and low[v]>=disc[u])	
			{	
			ap[u]=true;
			}
		}
		else if(v!=parent[u])
		{
			low[u]=min(low[u],disc[v]);
		}
	}
}
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	reset();
	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	cout<<"Articulation Points in Graph are \n";
	for(int i=0;i<n;i++)
	{
		if(!vis[i])
		dfs(i);
	}
	for(int i=0;i<n;i++)
	{
		if(ap[i])
		cout<<i<<" ";
	}
	cout<<endl;
}

Problem :

//PrOgAmErS@2015
//GRAPHS
#include<set>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<utility>
#include<iostream>
#include<algorithm>
//#include<sAi> // lAzY ProGrAmEr :)
using namespace std;
#define MX 10000007
#define LL long long
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define FOR(i,a,n) for(int i=a;i<n;i++)
#define FORE(i,a,n) for(int i=a;i<=n;i++)
template<class T1> inline T1 maxi(T1 a,T1 b){return a>b?a:b;}
template<class T2> inline T2 mini(T2 a,T2 b){return a<b?a:b;}
int dx[]={1,-1,0,0,0,0};
int dy[]={0,0,1,-1,0,0};
int dz[]={0,0,0,0,1,-1};
struct node
{
 int x,y,z;
};
int main()
{
 int l,r,c;
 ri(l),ri(r),ri(c);
 while(l|r|c)
 {
  vector< vector<string> >v1;
  vector<string>v2;
  v1.clear();
  int ans=0;
  FOR(i,0,l)
  {
   v2.clear();
   FOR(j,0,r)
   {
    string s;
    cin>>s;
    v2.push_back(s);
   }
   v1.push_back(v2);
  }
  int st_i,st_j,st_k,vis[l+1][r+1][c+1];
  node N;
  memset(vis,0,sizeof vis);
  FOR(i,0,l)
  {
   FOR(j,0,r)
   {
    FOR(k,0,c)
    if(v1[i][j][k]=='S')
    {
     N.x=i,N.y=j,N.z=k;break;
    }
 
   }
  }
  pair<node,int>P,top;
  queue< pair<node,int> >Q;
  Q.push(make_pair(N,0));
  vis[N.x][N.y][N.z]=1;
  while(!Q.empty())
  {
   node K;
   top=Q.front();
   st_i=Q.front().first.x;
   st_j=Q.front().first.y;
   st_k=Q.front().first.z;
   int dist=Q.front().second;
   Q.pop();
   if(v1[st_i][st_j][st_k]=='E')
   {
    ans=dist;break;
   }
   FOR(i,0,6)
   {
    int x1=st_i+dx[i];
    int y1=st_j+dy[i];
    int z1=st_k+dz[i];
    if((x1>=0 and y1>=0 and z1>=0) and (x1<l and y1<r and z1<c) and !vis[x1][y1][z1] and (v1[x1][y1][z1]=='.' or v1[x1][y1][z1]=='E'))
    {
     vis[x1][y1][z1]=1;
     K.x=x1,K.y=y1,K.z=z1;
     Q.push(make_pair(K,dist+1));
    }
   }
 
  }
  if(ans==0)
  cout<<"Trapped!\n";
  else
  cout<<"Escaped in "<<ans<<" minute(s)."<<endl;
  ri(l),ri(r),ri(c);
 }
}

Problem :

#include<bits/stdc++.h>
using namespace std;
class Solution 
{
 
	public:
    	bool isHappy(int n) 
	{
		map<int,int>a;
		while(a[n]!=1)
		{
			a[n]=1;
        		int sum=0,res=0;
			while(n)
			{
				res=n%10;
				sum+=(res*res);
				n/=10;
			}
			if(sum==1)
			return true;
			else
			{
				n=sum;
			}
		}
		return false;
    	}
};
int main()
{
	Solution s;	
	cout<<s.isHappy(19)<<endl;
	cout<<s.isHappy(301)<<endl;
}