COME ON CODE ON

A blog about programming and more programming.

All Pair Shortest Path (APSP)

with one comment

Question : Find shortest paths between all pairs of vertices in a graph.

Floyd-Warshall Algorithm
It is one of the easiest algorithms, and just involves simple dynamic programming. The algorithm can be read from this wikipedia page.

#define SIZE 31
#define INF 1e8
double dis[SIZE][SIZE];
void init(int N)
{
	for (k=0;k<N;k++)
		for (i=0;i<N;i++)
			dis[i][j]=INF;
}
void floyd_warshall(int N)
{
        int i,j,k;
        for (k=0;k<N;k++)
                for (i=0;i<N;i++)
                        for (j=0;j<N;j++)
                                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}

int main()
{
	//input size N
	init(N);
	//set values for dis[i][j]
	floyd_warshall(N);
}

We can also use the algorithm to

  1. find the shortest path
    • we can use another matrix called predecessor matrix to construct the shortest path.
  2. find negative cycles in a graph.
    • If the value of any of the diagonal elements is less than zero after calling the floyd-warshall algorithm then there is a negative cycle in the graph.
  3. find transitive closure
    • to find if there is a path between two vertices we can use a boolean matrix and use and-& and or-| operators in the floyd_warshall algorithm.
    • to find the number of paths between any two vertices we can use a similar algorithm.

NJOY!!
-fR0DDY

Written by fR0DDY

August 7, 2010 at 1:53 PM

Number of Cycles in a Graph

with 2 comments

Question : Find the number of simple cycles in a simple graph.

Simple Graph – An undirected graph that has no loops and no more than one edge between any two different vertices.
Simple Cycle – A closed (simple) path, with no other repeated vertices or edges other than the starting and ending vertices.

Given a graph of N vertices and M edges, we will look at an algorithm with time complexity O(2NN2). We will use dynamic programming to do so. Let there be a matrix map, such that map[i][j] is equal to 1 if there is a edge between i and j and 0 otherwise. Let there be another array f[1<<N][N] which denotes the number of simple paths.

Let,
i denote a subset S of our vertices
k be the smallest set bit of i
then f[i][j] is the number of simple paths from j to k that 
contains vertices only from the set S. 

In our algorithm first we will find f[i][j] and then check if there is a edge between k and j, if yes, we can complete every simple path from j to k into a simple cycle and hence we add f[i][j] to our result of total number of simple cycles.Now how to find f[i][j].

For very subset i we iterate through all edges j. Once we have set k, we look for all vertices 'l' that can be neighbors of j in our subset S. So if l is a vertex in subset S and there is edge from j to l then f[i][j] = f[i][j] + the number of simple paths from l to i in the subset {S – j}. Since a simple graph is undirected or bidirectional, we have counted every cycle twice and so we divide our result by 2. Here's a sample C++ code which takes N, M and the edges as input.

#include<iostream>
using namespace std;

#define SIZE 20

bool map[SIZE][SIZE],F;
long long f[1<<SIZE][SIZE],res=0;

int main()
{
    int n,m,i,j,k,l,x,y;
    scanf("%d%d",&n,&m);
    for (i=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        x--;y--;
        if (x>y)
           swap(x,y);
        map[x][y]=map[y][x]=1;
        f[(1<<x)+(1<<y)][y]=1;
    }
    
    for (i=7;i<(1<<n);i++)
    {
        F=1;
        for (j=0;j<n;j++)
            if (i&(1<<j) && f[i][j]==0)
            {
               if (F)
               {
                  F=0;
                  k=j;
                  continue;
               }
               for (l=k+1;l<n;l++)
               {
                   if (i&(1<<l) && map[j][l])
                      f[i][j]+=f[i-(1<<j)][l];
               }
               if (map[k][j])
                  res+=f[i][j];
            }
    }
    printf("%lld\n",res/2);
}

NJOY!
-fR0DDY

Written by fR0DDY

June 7, 2010 at 1:14 PM

Longest Common Increasing Subsequence (LCIS)

with 10 comments

Given 2 sequences of integers, we need to find a longest sub-sequence which is common to both the sequences, and the numbers of such a sub-sequence are in strictly increasing order.
For example,
2 3 1 6 5 4 6
1 3 5 6
the LCIS is 3 5 6.

The sequence a1, a2, …, an is called increasing, if ai<ai+1 for i<n.The sequence s1, s2, …, sk is called the subsequence of the sequence a1, a2, …, an, if there exist such a set of indexes 1 ≤ i1 < i2 < … < ik ≤ n that aij = sj. In other words, the sequence s can be derived from the sequence a by crossing out some elements.

A nice tutorial on the algorithm is given on CodeChef blog here. If you read the blog you can see that instead of looking for LCIS in a candidate matrix, we can keep an array that stores the length of LCIS ending at that particular element. Also we keep a lookup previous array that gives the index of the previous element of the LCIS, which is used to reconstruct the LCIS.

For every element in the two arrays
1> If they are equal we check whether the LCIS formed will be bigger than any previous such LCIS ending at that element. If yes we change the data.
2> If the jth element of array B is smaller than ith element of array A, we check whether it has a LCIS greater than current LCIS length, if yes we store it as previous value and it’s LCIS length as current LCIS length.

Here’s a C++ code.

#include<iostream>
using namespace std;
#include<vector>

void LCIS(vector<int> A, vector<int> B)
{
    int N=A.size(),M=B.size(),i,j;
    vector<int> C(M,0);
    vector<int> prev(M,0);
    vector<int> res;
    
    for (i=0;i<N;i++)
    {
        int cur=0,last=-1;
        for (j=0;j<M;j++)
        {
            if (A[i]==B[j] && cur+1>C[j])
            {
               C[j]=cur+1;
               prev[j]=last;
            }
            if (B[j]<A[i] && cur<C[j])
            {
               cur=C[j];
               last=j;
            }
        }
    }
    
    int length=0,index=-1;
    for (i=0;i<M;i++)
        if (C[i]>length)
        {
           length=C[i];
           index=i;
        }
    printf("The length of LCIS is %d\n",length);
    if (length>0)
    {
       printf("The LCIS is \n");
       while (index!=-1)
       {
             res.push_back(B[index]);
             index=prev[index];
       }
       reverse(res.begin(),res.end());
       for (i=0;i<length;i++)
           printf("%d%s",res[i],i==length-1?"\n":" ");
    }
}


int main()
{
    int n,m,i;
    scanf ("%d", &n);
    vector<int> A(n,0);
    for (i = 0; i < n; i++)
        scanf ("%d", &A[i]);
    scanf ("%d", &m);
    vector<int> B(m,0);
    for (i = 0; i < m; i++)
        scanf ("%d", &B[i]);
    LCIS(A,B);
}

NJOY!
-fR0DDY

Written by fR0DDY

June 1, 2010 at 12:47 PM

Number of Binary Trees

with 4 comments

Question : What is the number of rooted plane binary trees with n nodes and height h?

Solution :
Let tn,h denote the number of binary trees with n nodes and height h.

Lets take a binary search tree of n nodes with height equal to h. Let the number written at its root be the mthnumber in sorted order, 1 ≤ m ≤ n. Therefore, the left subtree is a binary search tree on m-1 nodes, and the right subtree is a binary search tree on n-m nodes. The maximum height of the left and the right subtrees must be equal to h-1. Now there are two cases :

  1. The height of left subtree is h-1 and the height of right subtree is less than equal to h-1 i.e from 0 to h-1.
  2. The height of right subtree is h-1 and the height of left subtree is less than equal to h-2 i.e from 0 to h-2, since we have considered the case when the left and right subtrees have the same height h-1 in case 1.

Therefore tn,h is equal to the sum of number of trees in case 1 and case 2. Let’s find the number of trees in case 1 and case 2.

  1. The height of the left subtree is equal to h-1. There are tm-1,h-1 such trees. The right subtree can have any height from 0 to h-1, so there are \displaystyle\sum_{i=0}^{h-1}t_{n-m,i} such trees. Therefore the total number of such tress are t_{m-1,h-1}\displaystyle\sum_{i=0}^{h-1}t_{n-m,i}.
  2. The height of the right subtree is equal to h-1. There are tn-m,h-1 such trees. The left subtree can have any height from 0 to h-2, so there are \displaystyle\sum_{i=0}^{h-2}t_{m-1,i} such trees. Therefore the total number of such tress are t_{n-m,h-1}\displaystyle\sum_{i=0}^{h-2}t_{m-1,i}.

Hence we get the recurrent relation
t_{n,h}= \displaystyle\sum_{m=1}^{n}{(t_{m-1,h-1}\displaystyle\sum_{i=0}^{h-1}t_{n-m,i})} + \displaystyle\sum_{m=1}^{n}{(t_{n-m,h-1}\displaystyle\sum_{i=0}^{h-2}t_{m-1,i})}
or
t_{n,h}= \displaystyle\sum_{m=1}^{n}{(t_{m-1,h-1}\displaystyle\sum_{i=0}^{h-1}t_{n-m,i} + t_{n-m,h-1}\displaystyle\sum_{i=0}^{h-2}t_{m-1,i})}
where t0,0=1 and t0,i=ti,0=0 for i>0.
Here’s a sample C++ code.

#include<iostream>
using namespace std;

#define MAXN 35

int main()
{
    long long t[MAXN+1][MAXN+1]={0},n,h,m,i;
    
    t[0][0]=1;
    for (n=1;n<=MAXN;n++)
        for (h=1;h<=n;h++)
            for (m=1;m<=n;m++)
            {
                for (i=0;i<h;i++)
                    t[n][h]+=t[m-1][h-1]*t[n-m][i];
                
                for (i=0;i<h-1;i++)
                    t[n][h]+=t[n-m][h-1]*t[m-1][i];
            }
            
    while (scanf("%lld%lld",&n,&h))
          printf("%lld\n",t[n][h]);
}

Note :

  1. The total number of binary trees with n nodes is \frac{2n!}{n!(n+1)!}, also known as Catalan numbers or Segner numbers.
  2. tn,n = 2n-1.
  3. The number of trees with height not lower than h is \displaystyle\sum_{i=h}^{n}{t_{n,i}}.
  4. There are other recurrence relation as well such as
    t_{n,h}= \displaystyle\sum_{i=0}^{h-1}{(t_{n-1,h-1-i}(2*\displaystyle\sum_{j=0}^{n-2}t_{j,i} + t_{n-1,i}))}.

NJOY!
-fR0DDY

Written by fR0DDY

April 13, 2010 at 11:44 AM

Posted in Algorithm, Maths, Programming

Tagged with , , , , ,

Multiply two Numbers Without Using * Operator

with 7 comments

Lets have a fun question. Multiply two numbers without using the * operator.
Here’s the code in C/C++:

main(a,b,m)
{
    while (~scanf("%d%d",&a,&b))
    {
          m=0;
          while (a)
          {
                if (a&1)
                   m+=b;
                a>>=1;
                b<<=1;
          }
          printf("%d\n",m);
    }
}

The above code is a implementation of an algorithm better known as the Ethiopian Multiplication or the Russian Peasant Multiplication.
Here’s the algorithm :

  1. Let the two numbers to be multiplied be a and b.
  2. If a is zero then break and print the result.
  3. If a is odd then add b to the result.
  4. Half a, Double b. Goto Step 2.


NJOY!
-fR0DDY

Written by fR0DDY

April 8, 2010 at 10:05 AM

Posted in Beautiful Codes

Tagged with , ,

Convert a number from decimal base to any Base

with 6 comments

Convert a given decmal number to any other base (either positive or negative).

For example, 100 in Base 2 is 1100100 and in Base -2 is 110100100.

Here’s a simple algorithm to convert numbers from Decimal to Negative Bases :

def tonegativeBase(N,B):
   digits = []
   while i != 0:
	i, remainder = divmod (i, B)
	if (remainder < 0):
	    i, remainder = i + 1, remainder + B*-1
	digits.insert (0, str (remainder))
   return ''.join (digits)

We can just tweak the above algorithm a bit to convert a decimal to any Base. Here’s a sample code :

#include<iostream>
using namespace std;

void convert10tob(int N,int b)
{
     if (N==0)
        return;
     
     int x = N%b;
     N/=b;
     if (x<0)
        N+=1;
        
     convert10tob(N,b);
     printf("%d",x<0?x+(b*-1):x);
     return;
}


int main()
{
    int N,b;
    while (scanf("%d%d",&N,&b)==2)
    {
          if (N!=0)
          {
              convert10tob(N,b);
              printf("\n");
          }
          else
              printf("0\n");
    }
}

NJOY!
-fR0DDY

Written by fR0DDY

February 17, 2010 at 6:06 PM

Posted in Algorithm, Maths, Programming

Tagged with , , , , ,

Number of zeores and digits in N Factorial in Base B

with 2 comments

Question : What is the number of trailing zeroes and the number of digits in N factorial in Base B.

For example,
20! can be written as 2432902008176640000 in decimal number system while it is equal to “207033167620255000000” in octal number system and “21C3677C82B40000” in hexadecimal number system. That means that 10 factorial has 4 trailing zeroes in Base 10 while it has 6 trailing zeroes in Base 8 and 4 trailing zeroes in Base 16. Also 10 factorial has 19 digits in Base 10 while it has 21 digits in Base 8 and 16 digits in Base 16. Now the question remains how to find it?

Now we can break the Base B as a product of primes :
B = ap1 * bp2 * cp3 * …
Then the number of trailing zeroes in N factorial in Base B is given by the formulae
min{1/p1(n/a + n/(a*a) + ….), 1/p2(n/b + n/(b*b) + ..), ….}.

And the number of digits in N factorial is :
floor (ln(n!)/ln(B) + 1)

Here’s a sample C++ code :

#include<iostream>
using namespace std;
#include<math.h>

int main()
{
    int N,B,i,j,p,c,noz,k;
    while (scanf("%d%d",&N,&B)!=EOF)
    {
          noz=N;
          j=B;
          for (i=2;i<=B;i++)
          {
              if (j%i==0)
              {   
                 p=0;
                 while (j%i==0)
                 {
                       p++;
                       j/=i;
                 }
                 c=0;
                 k=N;
                 while (k/i>0)
                 {
                       c+=k/i;
                       k/=i;
                 }
                 noz=min(noz,c/p);
              }
          }
          double ans=0;
          for (i=1;i<=N;i++)
          {
              ans+=log(i);
          }
          ans/=log(B);ans+=1.0;
          ans=floor(ans);
          printf("%d %.0lf\n",noz,ans);
    }
}

NJOY!
-fR0DDY

Written by fR0DDY

February 17, 2010 at 5:47 PM

Posted in Maths, Programming

Tagged with , , , , , ,

%d bloggers like this: