Author: abhinav92003

Faces of Fibonacci

You know about the Fibonacci numbers and you know how Matrix Exponentiation allows you to find the nth Fibonacci number in just O(logn) time.

Matrix Exponentiation is a useful tool in solving not just the questions related to Fibonacci numbers but other recurrence equations too.

The equation:
f(n) = a*f(n-1) + b*f(n-2)
can be disguised and thrown at you in numerous ways.

I’m going to use a familiar problem to show you how.


SAMPLE PROBLEM:
We have the following types of rectangles with us:
1. size 1 X 1
2. size 2 X 1
In how many ways can we form a rectangle of size N X 1 by putting the mentioned types of rectangles side by side.


To form rectangle of size 1 X 1 there is only one way. That is to use one rectangle of size 1 X 1.
To form rectangle of size 2 X 1 there are two ways: the first is to use a 2 X 1 rectangle directly and the second way is to put two 1 X 1 rectangles side by side.
To form rectangle of size 3 X 1 there are 3 ways. For 4 X 1, there are 5 ways..

Lets analyze this problem in a recursive manner:

Let f(n) be the number of ways to form an N X 1 rectangle.
An N X 1 rectangle can be formed either by adding a 1 X 1 rectangle to the end of an (N-1) X 1 rectangle
OR
by adding a 2 X 1 rectangle to the end of an (N-2) X 1 rectangle
Therefore, the number of ways to form N X 1 rectangle = (number of ways to form (N-1) X 1 rectangle) + (number of ways to form (N-2) X 1 rectangle)
f(n) = f(n-1) + f(n-2) ; with f(0)=1 and f(1)=1
Its the Fibonacci series!!

( f(0)=1 because there is 1 way to form a 0 X 1 rectangle: do not use any rectangle )

Let’s look at a variation.


SAMPLE PROBLEM:
We have the following types of rectangles with us:
1. size 1 X 1 of two different types: red- and blue-colored
2. size 2 X 1

In how many ways can we form a rectangle of size N X 1 by putting the mentioned types of rectangles side by side.


An N X 1 rectangle can be formed either by adding a 2 X 1 rectangle to the end of an (N-2) X 1 rectangle
OR
by adding a blue 1 X 1 rectangle to the end of an (N-1) X 1 rectangle
OR
by adding a red 1 X 1 rectangle to the end of an (N-1) X 1 rectangle
So, there are two ways to obtain N X 1 rectangle from an (N-1) X 1 rectangle, and only one way to get it from an (N-2) X 1 rectangle.
The equation becomes f(n) = 2*f(n-1) + 1*f(n-2) ; with f(0)=1 and f(1)=2

In general, if we have 1 X 1 rectangles of X different colors and 2 X 1 rectangles of Y different colors, we can make an N X 1 rectangle in f(n) ways, f(n) = X*f(n-1) + Y*f(n-2); with f(0)=1 and f(1)=X

We can add another twist…


SAMPLE PROBLEM:
We have the following types of rectangles with us:
1. size 1 X 1 of X different colors
2. size 2 X 1 of Y different colors
3. size 3 X 1 of Z different colors

In how many ways can we form a rectangle of size N X 1 by putting the mentioned types of rectangles side by side.


In this case the number of ways to construct an N X 1 rectangle = f(n) = X * f(n-1) + Y * f(n-2) + Z * f(n-3) ; with f(0)=1, f(1)=X,f(2)=X+Y

All of the above variations can be solved using Matrix Exponentiation. We just need to find the exponentiation matrix carefully.

Apart from ‘number of ways to form rectangles’, in a programming problem you could be asked to compute the number of ways to climb stairs or many other variations.
This page contains many interesting questions.

The ability to decompose a problem into its sub-problems and to compute its solution from the solution of its sub-problems is very useful in solving many Dynamic programming, Recurrance equation and Graph related problems.

If you have any doubt, feel free to leave a comment here.

Advertisements

Algorithm #12: Matrix Exponentiation

Please read the previous post on Binary Exponentiation before you start with this one.

Lets first understand what a recurrence relation is. You probably know about the Fibonacci Series. It is a sequence of numbers in which the first number is 0, the second number is 1 and all subsequent numbers are determined using the formula:
f(n) = f(n-1) + f(n-2)

An equation such as the one above, in which one term of a sequence is defined using the previous terms, is called a Recurrence relation. Therefore, relations like
f(n)=f(n-3) + f(n-2) + f(n-1) [ Tribonacci Series ]
or
f(n)=3*f(n-1) + 7*f(n-2) [ an arbitrary example ]
etc.
are recurrence relations.

If we are given the problem to find the nth Fibonacci number modulo a prime number M, the naive solution would be like this:

long long findFibonacci(long long n,long long M)
{
  if(n==1)
    return 0;
  if(n==2)
    return 1;
  long long i,prevterm=0,prevterm2=1,thisterm;
  for(i=3;i<=n;i++)
  {
    thisterm=(prevterm+prevterm2)%M;
    prevterm=prevterm2;
    prevterm2=thisterm;

  }
  return thisterm;
}

In fact, we can write code to find nth element of any recurrence relation in a similar manner.
The problem with the previous code is that it has O(n) i.e. linear complexity.

Matrix exponentiation is a faster method that can be used to find the nth element of a series defined by a recurrence relation.
We’ll take Fibonacci series as an example.

In matrix exponentiation, we first convert the addition in a recurrence relation to multiplication. The advantage of doing this will become clear as you read on.

So the question is: How can we convert the addition in a recurrence relation to multiplication. The answer is matrices!

The general recurrence relation for a series in which a term depends on the previous 2 terms is:
f(n) = a*f(n-1) + b*f(n-2)
( For Fibonacci, a=1 and b=1 )
The matrix form of this equation is:

| f(n)   | =  | p  q | X | f(n-1) |
| f(n-1) |    | r  s |   | f(n-2) |

For convenience let
| p  q | = Z
| r  s |

Therefore, we get
f(n) = p * f(n-1) + q * f(n-2)
and
f(n-1) = r * f(n-1) + s * f(n-2)

For each recurrence relation, the values of p,q,r and s will be different.
On solving the above equations for the Fibonacci sequence we get, p=1, q=1, r=1 and s=0.

So, the Z matrix for Fibonacci sequence is

| 1  1 |
| 1  0 |

and the matrix form for f(n) = f(n-1) + f(n-2) is:

| f(n)   | = | 1  1 | X | f(n-1) |
| f(n-1) |   | 1  0 |   | f(n-2) |

Now lets get to the method for finding the nth element.
Initially we have the matrix,

| f(2) |
| f(1) |

Using the matrix form of Fibonacci series given above, if we have to find the next Fibonacci number, i.e. f(3), we will multiply Z matrix by the above matrix:

| 1  1 |  X | f(2) | = | f(3) |
| 1  0 |    | f(1) |   | f(2) |
If we again multiply Z with | f(3) | , we'll get | f(4) |
	      	            | f(2) |             | f(3) |

So, we have the following equation for the nth Fibonacci number.

| f(n)   | = Z^(n-2) X | f(2) |
| f(n-1) |             | f(1) |

So, we have successfully changed the addition in the recurrence equation to multiplication.
But now what??
As I mentioned in my previous post, we have an algorithm called Binary Exponentiation that can perform the operation base^power in O(log n) time.
Because now our job is to find Z^(n-2), we can do this by using Binary Exponentiation in O(log n) time.

Z^(n-2) will then be multiplied by | f(2) | and we'll get | f(n)   |  
		 		   | f(1) |		  | f(n-1) |

Ofcourse there is the small matter that multiplying matrices contributes to more overhead. But that overhead is tiny as compared to the speed up that we are obtaining by reducing O(n) to O(log n)

Here is the Matrix Exponentiation code for finding the nth Fibonacci number.
Compare it with the iterative version of Binary Exponentiation. You’ll observe that the only change is that we are now performing matrix multiplication instead of simple integer multiplication.
That’s why this algorithm is called Matrix Exponentiation.

void matmult(long long  a[][2],long long  b[][2],long long c[][2],long long  M)//multiply matrix a and b. put result in c
{
	int i,j,k;
	for(i=0;i<2;i++)
	{
		for(j=0;j<2;j++)
		{
			c[i][j]=0;
			for(k=0;k<2;k++)
			{
				c[i][j]+=(a[i][k]*b[k][j]);
				c[i][j]=c[i][j]%M;
			}
		}
	}

}
void matpow(long long Z[][2],int n,long long ans[][2],long long M)
//find ( Z^n )% M and return result in ans
{

	long long temp[2][2];
	//assign ans= the identity matrix
	ans[0][0]=1;
	ans[1][0]=0;
	ans[0][1]=0;
	ans[1][1]=1;
	int i,j;
	while(n>0)
	{
		if(n&1)
		{
			matmult(ans,Z,temp,M);
			for(i=0;i<2;i++)
				for(j=0;j<2;j++)
					ans[i][j]=temp[i][j];
		}
		matmult(Z,Z,temp,M);
		for(i=0;i<2;i++)
			for(j=0;j<2;j++)
				Z[i][j]=temp[i][j];


		n=n/2;
	}
	return;
	
}
long long findFibonacci(long long n,long long M)
{
	
	long long fib;
	if(n>2)
	{
		long long int Z[2][2]={{1,1},{1,0}},result[2][2];//modify matrix a[][] for other recurrence relations
		matpow(Z,n-2,result,M);
		fib=result[0][0]*1 + result[0][1]*0;	//final multiplication of Z^(n-2) with the initial terms of the series
	}
	else
		fib=n-1;
		
	return fib;
}

The challenging part of this algorithm is to find the Z matrix for a recurrence relation.
For the recurrence relation: f(n) = f(n-1) + 2*f(n-2) + 3*f(n-3), we have

| f(n)   |    | p  q  r |   | f(n-1) |
| f(n-1) | =  | s  t  u | X | f(n-2) |
| f(n-2) |    | v  w  x |   | f(n-3) |

Write out the equations for f(n), f(n-1) and f(n-2) from the above matrix equation and you’ll find that the Z matrix is:

| 1  2  3 |
| 1  0  0 |
| 0  1  0 |

Related Problems:
CLIMBING STAIRS (Codechef)

Algorithm #11: Binary Exponentiation

Some programming problems require us to find the value of base^power modulo some positive prime number M (power>=0).
If you had to find the value of ( base^power ) % M, how would you do it??
The easiest method that comes to mind is iterating a loop.

long long findPower(long long base,long long power,long long M)
{
	long long ans=1;
	int i;
	for(i=1;i<=power;i++)
		ans=(ans*base)%M;
	return ans;
}

The above method is simple but not at all efficient. For values of power around 10^8 or more, this method will take a lot of time to run. If you increase the value of power to 10^16, you’ll pass out from college before the computation ends! Increase it to around 10^25, the sun will become a Red Giant and swallow Earth before the value is computed!!

But why would we need to find such large values :P. Yeah that’s a valid question; but it shouldn’t stop us from learning a better algorithm!

There is a much better algorithm than the linear one described above, which is the topic of this post.
I’ve already introduced Binary Exponentiation as a part of an earlier post. But, I need to formalize it for the next post.

Binary Exponentiation is based on the idea that,
to find base^power, all we need to do is find base^(power/2) and square it. And this method can be repeated in finding base^(power/2) also.

Suppose that we need to find 5^8.
5^8=5^4 * 5^4
5^4=5^2 * 5^2
5^2=5 * 5

The number of steps required to find 5^8 has been reduced from 8 to just 3.
As another example, consider 8^51
8^51 = 8^25 * 8^25 * 8
8^25 = 8^12 * 8^12 * 8
8^12 = 8^6 * 8^6
8^6 = 8^3 * 8^3
8^3 = 8 * 8 * 8

If we used the linear algorithm, we would have required 27 steps. But, using this awesome trick we required roughly 5 steps.
In a general sense, we require steps in the order of O(logbase2 n)

This algorithm can be implemented recursively as well as iteratively.

RECURSIVE IMPLEMENTATION:

long long fastPower(long long base,long long power,long long M)
{
    if(power==0)
       return 1;
    if(power==1)
    return base;
    long long halfn=fastPower(base,power/2,M);
    if(power%2==0)
        return ( halfn * halfn ) % M;
    else
        return ( ( ( halfn * halfn ) % M ) * base ) % M;
}

ITERATIVE IMPLEMENTATION:

long long int fastPower(long long base,long long power,long long M)
{
        long long result=1;
        while (power>0) 
        {
                if (power%2==1)         
                        result = (result*base)%M;
                base = (base*base)%M;
                power/=2;
        }
        return result;
}

The iterative implementation can be a little tricky to understand. Take a pen and paper and trace the values of variables through the iterations. That’s an effective way to understand and convince yourself.
The iterative version runs a little faster that the recursive version.

Binary exponentiation will find the value of base^(10^25) in about 85 steps only.. Now that’s really cool…

                        The maximum number of multiplications that are required to compute base ^ power is 2 X FLOOR(logbase2 (power)). Think why 😛

Algorithm #10: Disjoint Set Union

Disjoint Set Union (DSU) or Union-Find is a graph algorithm that is very useful in situations when you have to determine the connected components in a graph.

Suppose that we have N nodes numbered from 1 to N and M edges. The graph can be disconnected and may have multiple connected components. Our job is to find out how many connected components are there in the graph and the number of nodes in each of them.

The basic idea behind DSU is the following:
Initially, all nodes are isolated i.e. there are no edges in the graph. We add edges to the graph one by one.
While adding an edge, check if the two nodes that the edge connects are already present in the same connected component.
– if they are, then do nothing.
– if they aren’t, then make the smaller of the two connected components a part of the larger one.
(So, we are making union of disjoint connected components; therefore the name Disjoint Set Union)

To keep track of what connected component a node belongs to, we use an array named parent[ ].
parent[ i ] tells the ID of the connected component that the ith node belongs to. The ID of a connected component is one of the nodes in that connected component. This node is kind of the leader or parent of all other nodes in that connected component.
Initially, as all nodes are isolated, we have N connected components; each node being the leader of their connected component. Therefore, parent[ i ]=i for all 1<=i<=N.

To keep track of the size of a connected component, we use the size[ ] array.
size[ i ] = the number of nodes in the ith connected component.
Initially, size[ i ] =1, for all 1<=i<=N. This is because, initially, all connected components contain only one node.

When we encounter an edge that connects two nodes a and b that belong to different connected components, we first check which of the two connected components is bigger: the one that a belongs to or the one that b belongs to. The smaller connected component becomes part of the larger one. This is done to reduce the number of nodes whose parent has to be changed.

Notice that we used the function call findParent( i ) to find the parent of the ith node, instead of directly looking at parent[ i ]. The reason for this is:
The parent of a node is not changed as soon as its affiliation to a connected component is changed. We postpone this to when we actually need to find the parent of the node. Doing this avoids many useless operations. So, parent[ i ] may not contain the updated value of the connected component that i belongs to. That’s why it’s important that we use findParent( i ) instead of being lazy and taking the value directly from parent[ i ].

In the end, we need to consider those nodes i that have findParent( i )== i. This is because, these are the nodes that still belong to their initial connected component and were not assigned to a different one during execution. These represent the disjoint connected components we are looking for.

So the complete code for DSU is as follows:


#include<stdio.h>
#define MOD 1000000007
int findParent(int i,int parent[])
//function to find the connected component that the ith node belongs to
{
	if(parent[parent[i]]!=parent[i])
        parent[i]=findParent(parent[i],parent);
	return parent[i];
}
void unionNodes(int a,int b,int parent[],int size[])
//to merge the connected components of nodes a and b
{
	int parent_a=findParent(a,parent),parent_b=findParent(b,parent);
	if(parent_a==parent_b)
        return;
	if(size[parent_a]>=size[parent_b])//the larger connected component eats up the smaller one
	{
         size[parent_a]+=size[parent_b];
         parent[parent_b]=parent_a;
	}
	else
	{
         size[parent_b]+=size[parent_a];
         parent[parent_a]=parent_b;
	}
	return;
}

int main()
{

    int N,M,i,a,b;
    scanf(" %d %d",&N,&M);
    int parent[100001]={0},size[100001]={0};
    for(i=1;i<=N;i++)
    {
        parent[i]=i;
        size[i]=1;
    }

    for(i=1;i<=M;i++)
    {
        //scan each edge and merge the connected components of the two nodes
        scanf(" %d %d",&a,&b);
        unionNodes(a,b,parent,size);
    }

    for(i=1;i<=N;i++)
        printf("Node %d belongs to connected component %d\n",i,findParent(i,parent));
    long long ways=1;
    int nos=0;
    for(i=1;i<=N;i++)
    {
        if(findParent(i,parent)==i)//this condition is true only for disjoint connected components
        {
            printf("%d leader %d size\n",i,size[i]);
            nos++;
        }

    }
    printf("Total connected components : %d",nos);

	return 0;
}

Comparison between DFS and DSU:
The task that DSU achieves in this code can be done using DFS as well. You should to code the same using DFS too.

Some related problems are:
GALACTIK FOOTBALL (Codechef)
FIRE ESCAPE ROUTES (Codechef)

Keep in mind that DFS is not a replacement for DSU. DFS works well in cases when all edges are present in the graph from the beginning. But, in problems where edges are added during the execution and we need to run connectivity queries in between such additions, DSU is the better option. An example of this type of situation is the Kruskal’s algorithm to find the Minimum Spanning Tree (MST).
In Kruskal’s algorithm, before adding an edge to the MST we need to check if the addition of the edge creates a cycle or not. We can use DSU here. If the parents of the two nodes that the edge connects are same, then we know that addition of the edge will create a cycle.
Try implementing Kruskal’s algorithm for MST using DSU by yourself. It’s quite simple once you know DSU.

Problems for MST:
COAL SCAM (Codechef)

Algorithm #9 : Depth- and Breadth- First Search

This post is about the graph traversal algorithms, Depth First Search (DFS) and Breadth First Search (BFS).
BFS and DFS are one of the algorithms for graph exploration. Graph exploration means discovering the nodes of a graph by following the edges. We start at one node and then follow edges to discover all nodes in a graph. The choice of first node may be arbitrary or problem specific.

The difference between BFS and DFS is the order in which the nodes of a graph are explored.
If you are not already familiar with BFS and DFS in theory, I recommend that you read about them. Because I’m going to focus more on their implementation here.

In a nutshell, DFS continues on one path and explores it completely before going down another path.
But in BFS we progress equally in all possible paths.

The following gifs will give you a good general idea about the two.
Here, the nodes are numbered according to the order in which they are explored.

Depth First Search
DFS

Breadth First Search
BFS

[Both the images were taken from commons.wikimedia.org]

IMPLEMENTATION:
We can use any of the four graph representation methods that I introduced in my post Representation of Graphs. In this post we’ll use Adjacency list and assume that the input is the edges in form of pairs of positive integers (i.e. Type 2, if you refer to my post). The nodes are numbered from 1 to n.

For DFS:
DFS has to be implemented using a stack data structure. As recursion uses the internal stack, we can use recursion as follows:

int adjlist[101][101]={0};
int degree[101]={0};
int done[101]={0};//this array marks if a node has already been explored
void dfs(int at)
{
	if(done[at]==1)//if the node has already been explored, then return
		return;
	printf("At node %d\n",at);
	done[at]=1;
	int i=0;
	while(i<degree[at])//for each of the edges on this node
	{
		dfs(adjlist[at][i]);
		i++;
	}
	return;
}
int main()
{
    int n,m,i,a,b;
    scanf(" %d %d",&n,&m);
    i=0;
    while(i<m)
    {
        scanf(" %d %d",&a,&b);
        adjlist[a][degree[a]]=b;
        degree[a]++;
        adjlist[b][degree[b]]=a;
        degree[b]++;
        i++;
    }
    dfs(1);//start with any node. node 1 is the first node here
    return 0;
}

For BFS:
BFS needs a Queue data structure for its implementation. Here I use an array queue[] and integers front and rear to implement Queue.


int main()
{
    int n,m,i,a,b;
    int adjlist[101][101]={0};
    int degree[101]={0};
    scanf(" %d %d",&n,&m);
    i=0;
    while(i<m)
    {
        scanf(" %d %d",&a,&b);
        adjlist[a][degree[a]]=b;
        degree[a]++;
        adjlist[b][degree[b]]=a;
        degree[b]++;
        i++;
    }
    int queue[101],front=0,rear=0;
    int done[101]={0};//this array marks if a node has already been explored
    int at;
    queue[rear]=1;//start with any node. node 1 is the first node heres
    rear++;
    done[1]=1;
    while(front!=rear)
    {
        at=queue[front];
        printf("At node %d\n",at);
        front++;
        for(i=0;i<degree[at];i++)
        {
            if(done[adjlist[at][i]]!=1)
            {
                queue[rear]=adjlist[at][i];
                rear++;
                done[adjlist[at][i]]=1;
            }
        }
    }
    return 0;
}

The array done[] is used to mark the nodes that have already been visited. This has to be done to stop the code from re-discovering already visited nodes and running forever.

Above is a bare-bones implementation of the two algorithms. They do nothing more than exploring the graph. Apart from only exploring the graph, DFS and BFS can also be used to compute other information too.
For example, if we have a tree as input, we can modify the above DFS code to compute the depth of each node in the tree, and also the size of the sub-tree rooted at each node.

int adjlist[101][101]={0};
int degree[101]={0};
int depth[101]={0};
int sizeofsubtree[101]={0};
int done[101]={0};//this array marks which node has already been explored
int dfs(int at,int currentdepth)
{
	if(done[at]==1)//if the node has already been explored, then return
		return 0;
	depth[at]=currentdepth;
	printf("Node %d at depth %d\n",at,depth[at]);
	done[at]=1;
	int i=0,size=1;//initialised to 1 as current node is also part of the sub-tree rooted at current node
	while(i<degree[at])//for each of the edges on this node
	{
		size+=dfs(adjlist[at][i],currentdepth+1);
		i++;
	}
	sizeofsubtree[at]=size;
	return sizeofsubtree[at];
}
int main()
{
    int n,m,i,a,b;
    scanf(" %d %d",&n,&m);
    i=0;
    while(i<m)
    {
        scanf(" %d %d",&a,&b);
        adjlist[a][degree[a]]=b;
        degree[a]++;
        adjlist[b][degree[b]]=a;
        degree[b]++;
        i++;
    }
    dfs(1,0);//start with root node. assuming that node 1 is the root node here
    i=1;
    printf("Depth of subtrees:\n");
    while(i<=n)
    {
        printf("Rooted at %d: %d\n",i,sizeofsubtree[i]);
        i++;
    }
    return 0;
}

A second variable currentdepth is passed to each dfs() instance that represents the depth of the current node. Notice that at line 16, currentdepth+1 has been passed to dfs(); because child of the current node has depth one more than the parent node.

Each recursive instance of dfs() returns the size of the sub-tree rooted at a node.
At every node, we sum up the values returned by dfs() for each child node ( This is done at line 16 ). The size of a sub-tree rooted at a node is the summation of sizes of sub-trees rooted at its children + 1. This is how the size of all sub-trees is computed.

COMPARISION BETWEEN DFS AND BFS:
If all the nodes of a graph have to be discovered, then BFS and DFS both take equal amount of time. But, if we want to search for a specific node, both algorithms may differ in execution time.

DFS is more risky compared to BFS. If a node has more than one edge leading from it, the choice of which edge to follow first is arbitrary.
As we don’t have any intelligently way of choosing which edge to follow first, it may be possible that the required node is present down the first edge that we choose and it is also possible that the required node is present down the last edge that we choose from that node. In the former case, DFS will find the node very quickly, but in the latter case DFS will take a lot of time. If we take a wrong path at some node, DFS will have to completely traverse the whole path before it can go down another path. That’s why DFS is more risky than BFS.

In BFS, all paths are explored equally. So, in some cases the search may be a little slower than DFS but the advantage of BFS is that it doesn’t arbitrary favor one path over the other.

BFS is very useful in problems where you have the find the shortest path. This is because BFS explores closer nodes first. So, when we find the node the first time, we can be sure that this is the shortest path to it. Whereas in DFS, we’ll have to find all possible paths and then select the shortest path.
BFS can also be used in checking if the graph is bipartite.

DFS is useful in problems where we have to check connectivity of graph and in topological sorting.

Suppose we have an infinite graph. If we use DFS to find a specific node, the search will never end if the node is not in the first path that the algorithm chooses. But, given sufficient time, BFS will be able to find it.

COMPLEXITY OF BFS AND DFS:
The complexity of DFS and BFS is O(E), where E is the number of edges.
Of course, the choice of graph representation also matters. If an adjacency matrix is used, they will take O(N^2) time (N^2 is the maximum number of edges that can be present). If an adjacency list is used, DFS/BFS will take O(E) time.

Related Problems:

Codechef : Fire Escape Routes
Hackerearth : Quidditch Practice Problem
Hackerearth : Close call

Representation of Graphs

Graph is a very versatile data structure. It can be used to solve a large number of problems. You’d be surprised to see how easy the problems become once they are interpreted in terms of a graph.

Before I can start with graph algorithms like DFS, BFS, Disjoint Set Union, Segment trees, etc. it is important to know how a graph can be represented in memory.

I’m assuming that you have knowledge of elementary graph theory and the concepts of node, edge, tree etc.

Two things are essential to a graph: its nodes and edges. As you know, each edge connects two nodes.
For all future references lets take N as the number of nodes and M as the number of edges. Each edge is of the form (a,b) denoting that nodes a and b are connected (1<=a,b<=N ) .
Following are two ways to store a graph. I’ll show you how to implement them:

1. Adjacency Matrix: Use a 2-D array of size N x N. Let’s call this matrix adjmat[N][N]. adjmat[i][j]=1 iff there is an edge from i to j.
For every undirected edge (a,b) in the graph, mark adjmat[a][b]=1 and adjmat[b][a]=1. If you have a directed edge from a to b, then mark only adjmat[a][b]=1.

2. Adjacency List: Use a 1-D array for each node. For every node, store in that array the nodes that it is connected to. So we’ll have N 1-D arrays, one for each node.

Lets take the following graph as example:
graph
The adjacency matrix would be:

adjmat

and the adjacency list would be:
adjlist

The adjacency list is a more efficient way to store information about a graph. It consumes lesser memory and is more time efficient as compared to adjacency matrix. The reason for this is that the adjacency matrix has one element in adjmat[][] for each possible edge in the graph i.e. N^2 possible edges. What if we have a tree? In case of a tree we have only N-1 edges. We don’t need to use N^2 amount of space just to store info about N-1 edges.
In such cases adjacency list is useful. Adjacency list can be implemented using a linked list OR dynamic array. And it consumes only that much space that is required.

Using an adjacency list also leads to lesser number of iterations in later operation (eg. during DFS, BFS, etc.). This is because the number of entries in adjacency list is 2 X M . But in case of adjacency matrix it is always N^2.

Of course in a situation where the number of edges is close to N^2, both methods will perform equally well.

In competitive programming competitions, most of the time a graph can be given as input in two ways. (Assume undirected graph)

1. The problem will give you N, and N lines will follow. In the beginning of ith line will be Di (Degree of ith node) and a list of the nodes that the ith node is connected to.
For the example graph given above, the input would look like:
5
3 2 3 4
1 1
2 1 4
2 1 3
0

2. The problem will give you N and M, and each of the next M lines will contain two integers a and b denoting an edge between nodes a and b.
For the example graph the input would be like this:
5 4
1 2
1 3
1 4
3 4

Both can be handled with either Adjacency Matrix or Adjacency List.

Type-1 with Adjacency Matrix:

int main()
{
    int n,i,j,temp;
    scanf(" %d",&n);
    int adjmat[101][101]={0};//size of this matrix should be (N+1) X (N+1) because we are using 1 based numerbing for nodes
    int degree[101]={0};
    i=1;
    while(i<=n)
    {
        scanf(" %d",&degree[i]);
        j=0;
        while(j<degree[i])
        {
            scanf(" %d",&temp);
            adjmat[i][temp]=1;
            adjmat[temp][i]=1;
            j++;
        }
        i++;
    }
    return 0;
}

Type 1 with adjacency list:

int main()
{
    int n,i,j,temp;
    scanf(" %d",&n);
    int *adjlist[101];
    int degree[101];
    i=1;
    while(i<=n)
    {
        scanf(" %d",&degree[i]);
        adjlist[i]=(int *)malloc(sizeof(int)*degree[i]);
        j=0;
        while(j<degree[i])
        {
            scanf(" %d",&temp);
            adjlist[i][j]=temp;
            j++;
        }
        i++;
    }
    return 0;
}

Type 2 with adjacency matrix:

int main()
{
    int n,m,i,a,b;
    scanf(" %d %d",&n,&m);
    int adjmat[101][101]={0};
    i=0;
    while(i<m)
    {
        scanf(" %d %d",&a,&b);
        adjmat[a][b]=1;
        adjmat[b][a]=1;
        i++;
    }
    return 0;
}

Type2 with adjacency list:

int main()
{
    int n,m,i,a,b;
    scanf(" %d %d",&n,&m);
    int adjlist[101][101]={0};
    int degree[101]={0};
    i=0;
    while(i<m)
    {
        scanf(" %d %d",&a,&b);
        adjlist[a][degree[a]]=b;
        degree[a]++;
        adjlist[b][degree[b]]=a;
        degree[b]++;
        i++;
    }
    return 0;
}

The above implementation for Type 2 with Adjacency List doesn’t use dynamic arrays ( as it would involve a lot of realloc() and would get complicated ). So it still uses a lot of memory. But the advantage of lesser iterations for later operations, as mentioned before, is still there.

If you want to use dynamic arrays, study about C++ STL Vectors. Vectors are dynamic arrays. I recommend that you read the C++ STL documentation for vectors as vectors are incredibly useful and you don’t need to worry about malloc, realloc etc. as that is handled automatically by vectors.
Follow this link. (For now, study about push_back(), size(), pop_back(), begin() and end() only)

In the next post, I’ll write about how to implement DFS and BFS.

Algorithm #8: Dynamic Programming for Subset Sum problem

Uptil now I have posted about two methods that can be used to solve the subset sum problem, Bitmasking and Backtracking. Bitmasking was a brute force approach and backtracking was a somewhat improved brute force approach.

In some cases, we can solve the subset sum problem using Dynamic Programming. (Note that I said “in some cases”). This post is an introduction to Dynamic programming.

Okay, so first questions first… What is Dynamic Programming?
Dynamic programming is not an algorithm in itself, it is a programming strategy. The basic idea behind DP is that while computing for the answer, we store the results of the intermediate computations so that we don’t need to recompute them later. We first compute the answer of smaller versions of our problem and store the answers. These intermediate answers help us compute the actual answer and as they are already stored somewhere we don’t need to recalculate them everytime we need them. This saves up a lot of time. That’s DP in a nutshell. There is much more to the definition of Dynamic Programming that you can read on Wikipedia. But for now, this simple definition will do.
This discussion on quora might help.

Let’s look at Subset Sum problem again:

We are given a set of N numbers. Our objective is to find out if it is possible to select some numbers from this set such that their sum exactly equals M. Eg. If we have the numbers {3,5,3,1} and M=8, then the answer is “yes” because of the subset {3,5}. If M=10, then the answer is “no” because no subset has sum=10.

The DP solution looks like this:

#include
int main()
{
    int N,M;
    scanf(" %d %d",&N,&M);
    int nums[N+1],i,j,ispossible[N+1][M+1];
    for(i=1;i<=N;i++)
        scanf(" %d",&nums[i]);
    for(i=0;i<=N;i++)
        for(j=0;j<=M;j++)
            ispossible[i][j]=0;//initialising to 0
    for(i=0;i<=N;i++)
        ispossible[i][0]=1;
    for(i=1;i<=N;i++)
    {
        for(j=0;j<=M;j++) { if(ispossible[i-1][j]==1) ispossible[i][j]=1; if(j-nums[i]>=0 && ispossible[i-1][j-nums[i]]==1)
                ispossible[i][j]=1;
        }
    }
    if(ispossible[N][M]==1)
        printf("Yes");
    else
        printf("No");
    return 0;
}

I’ve taken the input in nums[1], nums[2], … , nums[n]
I’ve used a 2-D array named ispossible[ ][ ]. It has size(N+1) x (M+1).
ispossible[i][j] can be either 0 or 1. Its value will be 1 if it is possible to select some numbers from the set {nums[1],nums[2],nums[3],…,nums[i]} so that their sum equals to j; otherwise it will be 0.

The logic is really simple:

Our final goal is to find the value of ispossible[N][M], which will be 1 if it is possible to obtain a subset of {nums[1],nums[2],nums[3],…,nums[N]} with sum equal to M.
To find the value of ispossible[N][M] we need to find the value of each element in the two dimensional array ispossible[ ][ ].

In general, ispossible[i][j] = 1 iff one of the following two conditions is true:

1. ispossible[i-1][j] is 1. If ispossible[i-1][j] is 1 it means that it is possible to obtain a sum of j by selecting some numbers from {nums[1],nums[2],nums[3],…,nums[i-1]}, so obviously the same is also possible with the set {nums[1],nums[2],nums[3],….,nums[i-1],nums[i]}.

2. ispossible[i-1][j-nums[i]] is 1. If ispossible[i-1][j-nums[i]] is 1 it means that it is possible to obtain a sum of (jnums[i]) by selecting numbers from {nums[1], nums[2],…,nums[i-1]}. Now if we select nums[i] too, then we can obtain a sum of (jnums[i])+nums[i] = j. Therefore ispossible[i][j] is 1.

The above two points serve as the DP equation for calculating all values in ispossible[ ][ ].

Note that first it is important to set ispossible[i][0] = 1 (for 0<=i<=N). Because obviously its possible to obtain a sum = 0 from any value of i.
This algorithm has time complexity O(N*M) and space complexity O(N*M).
The drawback of this algorithm and the reason why I said “in some cases” before is that if N*M is too large, then an array of the required size cannot be declared. So, this method works well only in those cases where N*M is around 10^8.

As I said earlier, Dynamic Programming is not a single algorithm but it is a programming strategy. A programming strategy that can be mastered only by practice. Dynamic programming questions are always unique and new. Each question has its own equation. By practicing enough DP questions you’ll learn how to recognize DP questions and how to think of their equation and solution.

RELATED PROBLEM:
Paying up ( Codechef ): This is a really simple DP problem that is exactly as the problem described in this post.
Fence ( Codeforces )
More questions can be found on Codeforces here.