Introduction to competitive programming

Articulation Points in a Graph

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

UVA:532 - Dungeon Master

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

LeetCode:Happy Numbers

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

SPOJ:ABCDEF

Problem :

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define rl(x) scanf("%lld",&x)
ll  a1[105];
ll  arr1[2000000];
int main()
{
 ll n,temp1=0,v,ans=0;
 rl(n);
 for(int i=0;i<n;i++)
 rl(a1[i]);
 for(int a=0;a<n;a++)
     if(a1[a])
            for(int b=0;b<n;b++)
        for(int c=0;c<n;c++)
           arr1[temp1++]=(a1[a]*(a1[b]+a1[c]));
        sort(arr1,arr1+temp1);
 for(int d=0;d<n;d++)
           for(int e=0;e<n;e++)
       for(int f=0;f<n;f++)
              {
    v=a1[d]*a1[e]+a1[f];
    ans+=(upper_bound(arr1,arr1+temp1,v))-(lower_bound(arr1,arr1+temp1,v));
              }
 cout<<ans<<endl;
 
} 
 

SPOJ:ADDREV

Problem :

#include<iostream>
using namespace std;
long long phi(long long n) 
{ 
 long  long result = n; 
        for(long  long i=2;i*i <= n;i++) 
        { 
  if (n%i==0) 
  result-=result/i; 
         while (n%i==0) 
  n/=i; 
        } 
        if (n>1) 
 result-=result/n; 
        return result; 
} 
int main()
{
 long long t,n;
 cin>>t; 
 while(t--)
 {
  cin>>n;
  cout<<phi(n)<<endl;
 }
} 

SPOJ:ETF

Problem :

#include<iostream>
using namespace std;
long long phi(long long n) 
{ 
	long  long result = n; 
        for(long  long i=2;i*i <= n;i++) 
        { 
		if (n%i==0) 
		result-=result/i; 
        	while (n%i==0) 
		n/=i; 
        } 
        if (n>1) 
	result-=result/n; 
        return result; 
} 
int main()
{
	long long t,n;
	cin>>t;	
	while(t--)
	{
		cin>>n;
		cout<<phi(n)<<endl;
	}
} 

SPOJ:NAKANJ(Minimum Knight Moves !!!)

Problem:

The problem is a simple application of BFS,even though the problem can be solved in different methods BFS is easy to implement>
The algorithm is to keep track of all the neighbouring vertices in a queue by checking the boundary cases and incrementing the corresponding distace.Whenever we find the destination point we return the distace at that point

Below code is the c++ implementation for the above problem

 
    #include<set>
    #include<map>
    #include<list>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<vector>
    #include<cstdio>
    #include<cctype>
    #include<deque>
    #include<bitset>
    #include<utility>
    #include<climits>
    #include<cstdlib>
    #include<cstring>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    //#include<sai> tHe lAzY PrOgRmMeR :)
    #define rl(T) scanf("%lld",&T)
    #define ri(T) scanf("%d",&T)
    #define rs(T) scanf("%s",T)
    #define rc(T) scanf("%c",&T)
    #define loop(i,a,n) for(long long i=a;i<n;i++)
    #define loopn(i,a,n) for(long long i=1;i<=n;i++)
    #define ll long long
    int x[10]={0,-1,-1,-2,-2,2,2,1,1};
    int y[10]={0,-2,2,-1,1,-1,1,-2,2};
    using namespace std;
    int bfs(int a1,int b1,int a2,int b2)
    {
         int moves[9][9],vis[9][9],m,n;
         pair<int,int>p1;
         queue< pair<int,int> >q;
         p1.first=a1;
         p1.second=b1;
         q.push(p1);
         memset(moves,0,sizeof moves);
         memset(vis,0,sizeof vis);
         vis[a1][b1]=0;
         while(!q.empty())
         {
             p1=q.front();
             q.pop();
             if(p1.first==a2 && p1.second==b2)
             return moves[a2][b2];
             for(int i=1;i<=8;i++)
             {
                 m=p1.first+x[i],n=p1.second+y[i];
                 if(m>8 || m<1 || n>8 || n<1)
                 continue;
                 else
                 {
                     vis[m][n]=1;
                     moves[m][n]=moves[p1.first][p1.second]+1;
                     q.push(make_pair(m,n));
                 }
             }
         }
    }
    int main()
    {
       char a1,a2;
       ll b1,b2,t;
       rl(t);
       while(t--)
       {
          cin>>a1>>b1>>a2>>b2;
          cout<<bfs(a1-'a'+1,b1,a2-'a'+1,b2)<<endl;
       } 
    } 

LeetCode :Palindrome Number

Problem:

Link

#include<bits/stdc++.h>
using namespace std;
class Solution 
{
    public:
    bool isPalindrome(int x) 
    {
        if(x<0)
 return false;
 stringstream ss;
 ss<<x;
 string s1="",s,temp;
 s=ss.str();
 for(int i=0;i<s.length();i++)
 {
  if(s[i]!=' ')
  s1+=s[i];
 }
 temp=s1;
 reverse(s1.begin(),s1.end());
 return s1==temp?true:false;
    }
};
int main()
{
 Solution s;
 cout<<s.isPalindrome(131)<<endl;
 cout<<s.isPalindrome(-456)<<endl;
}

LeetCode :Excel Sheet Column Number

Problem:

Link

#include<bits/stdc++.h>
using namespace std;
class Solution 
{
	public:
  	int titleToNumber(string s) 
	{
        	int n=s.length(),ans=0;
		for(int i=0;i<n;i++)
		{
			ans+=(pow(26,n-i-1))*(s[i]-'A'+1);
 
		}
		return ans;
    	}
};

LeetCode :Factorial Trailing Zeroes

Problem:

Reference : http://www.mytechinterviews.com/how-many-trailing-zeros-in-100-factorial

#include<iostream>
using namespace std;
class Solution 
{
public:
      int trailingZeroes(int n) {
        int count = 0;
        long k = 5;
        while(n >= k)
        {
            count+=n/k;
            k*=5;
        }
        return count;
    }
};
int main()
{
	Solution s;
	cout<<s.trailingZeroes(100)<<endl;
}

LeetCode :Reverse Integer

Problem:

#include<bits/stdc++.h>
using namespace std;
class Solution 
{
 public:
     int reverse(int x) 
 { 
  int res=0,ans=0,f=0;
  while(x)
  {
   if(ans>(INT_MAX/10) || ans<(INT_MIN/10))
   return 0;
   ans=ans*10+x%10;
   x/=10;
 
  }
 
  return ans;
 
   }
};

LeetCode :Spiral Matrix

Problem:

#include<bits/stdc++.h>
using namespace std;
class Solution 
{
	public:
    	vector<int> spiralOrder(vector<vector<int> > &matrix) 
	{
		vector<int>v;
		if(matrix.size()==0)
		return v;
 
        	int t=0,b=matrix.size()-1,l=0,r=matrix[0].size()-1;
		while(1)
		{
			for(int i=t;i<=r;i++)
			v.push_back(matrix[t][i]);t++;
			if(l>r || t>b) break;
			for(int i=t;i<=b;i++)
			v.push_back(matrix[i][r]);r--;
			if(l>r || t>b) break;
			for(int i=r;i>=l;i--)
			v.push_back(matrix[b][i]);b--;
			if(l>r || t>b) break;
			for(int i=b;i>=t;i--)
			v.push_back(matrix[i][l]);l++;
			if(l>r || t>b) break;
 
 
 
		}
	return v;
    	}
};

LeetCode:ReverseBits

Problem:

My brute force solutions get accepted,the algorithm is to push all the remainders into a stack and then multiplying each bit with corresponding power of 2

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
 int reverseBits(int n) 
 {
         int x=1,i=0;
  long long res=0;
  stack<int>st;
  while(x<=32)
  {
   st.push(abs(n%2));
   n>>=1;
   x++;
  }
  res=0;
  while(!st.empty())
  { 
   res+=(st.top()*(pow(2,i)));
   i++;
   st.pop();
  }
  return res;
   }
};

Reference :

Method 2

#include<bits/stdc++.h>
#define INT_SIZE 32
using namespace std;
class Solution 
{
 public:
 int reverseBits(unsigned int num)
 {
  int i=INT_SIZE-1;
  unsigned int rev_num=0;
  while(i>=0 && num)
  {
   if(num & 1)
   rev_num |= (1<<i);
   num>>=1;
   i--;
  }
 return rev_num;
 }
};
int main()
{
 Solution s;
 cout<<s.reverseBits(8)<<endl;
}

MST: Kruskal's Algorithm

Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph.
It finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.
This algorithm needs to sort edges in non-decreasing order and uses a disjoint-set data structure to keep track which vertex is in which component.

Algorithm:Kruskal

MST-KRUSKAL(G,w)
1  A = φ
2. for each vertex 2 ∈ G:V
3. Make_set{}
4. Sort the edges in non-decreasing order by weight
5. for each edge(u,v) ∈ G,E is taken from non-decreasing order by weight
6. if(find_set(u)!=find_set(v)
7. A=A U {(u,v)}
8. Union(u,v)
9. return A

Here is the C++ implementation of Kruskal algorithm

#include<bits/stdc++.h>
using namespace std;
#define MAX 100
#define edge pair< int,int >
vector< pair<int,edge> >G,MST;
int parent[MAX];
void reset(int n)
{
 G.clear();
 MST.clear();
 for(int i=0;i<=n;i++)
 parent[i]=i;
 
}
int find(int x)
{
 if(x!=parent[x])
 parent[x]=find(parent[x]);
 return parent[x];
}
int main()
{
 int n,e,u,v,w,pu,pv,total=0;
 cin>>n>>e;
 reset(n);
 for(int i=0;i<e;i++)
 {
  cin>>u>>v>>w;
  G.push_back(pair<int,edge >(w,make_pair(u,v)));// w(u,v) format
 }
 sort(G.begin(),G.end());    //sort will be done in increasing order of weight
 for(int i=0;i<e;i++)
 {
  pu=find(G[i].second.first); 
  pv=find(G[i].second.second);
  if((pu)!=(pv))
  {
   MST.push_back(G[i]);
   total+=G[i].first;
   parent[pu]=parent[pv];
  }
 }
 for(int i=0;i<MST.size();i++)
 {
  cout<<"("<<MST[i].second.first<<" "<<MST[i].second.second<<" ) :"<<MST[i].first<<endl;
 }
 cout<<"Mimimum cost for spanning tree is :"<<total<<endl;
}