Number of ways to change coins with given value | Dynmaic Programming

Coin change is a classical dynamic programming problem to count the number of possible ways to get value V cents using list of denomination of n coins.

For example :

List of coin denomination : centsValue[] = 1, 5, 10, 25, 50

For value 5, there 2 possible ways to change coins : {1 + 1 + 1 + 1 + 1, 5}

Solution:
First we need to find the recurrence relation. ways(index, value), where value is the remaining amount of cents that we need to change. and the first parameter index is index of the coin type. Lets consider all cases :

  1. ways(index, 0) = 1 // There is only 1 way i.e choose nothing.
  2. ways(index, <0) = 0 // We cannot change negative value.
  3. ways(n, value) = 0 // We have considered all coins from {0…n-1} and reached index = n
  4. ways(index, value) = ways(index, value – centsValue[index]) + ways (index + 1, value) // use coin with index + ignore coin with index type.

Call ways(0,V) to get answer.

Here is the iterative solution:

// for zero value choose nothing.
ways[index][0] = 1 

// for all index from {0...n-1}
ways[index][value] = ways[index][value-centsValue[index]] + ways[index-1][value] 

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
long long int ways[5][30001];

int main()
{
	memset(ways, 0, sizeof(ways));
	
	long long int cents[5] = {1,5,10,25,50};
	//Solve initially ways array;
	for(long long int i = 0 ; i < 5; i++)
	{
		ways[i][0] = 1;
	}
	for(long long int i = 0 ; i < 5; i++)
	{
		for(long long int j = 1; j<=30000; j++)
		{
			// consider coin with index i
			ways[i][j] = (j-cents[i] >=0) ? ways[i][j-cents[i]] : 0;
			// skip coin with index i and consider previous coins
			ways[i][j] += (i-1>=0) ? ways[i-1][j] : 0;
		}
	}
	// For value 5
	cout<<ways[4][5]<<endl;
	//for value 50
	cout<<ways[4][50]<<endl;
	//for value 29999
	cout<<ways[4][29999]<<endl;
	return 0;
}

Trainsorting – Dynamic Programming

Trainsorting problem appears in uva online judge in which we need to find the longest train length. It can be solved using dynamic programming paradigm.

Uva 11456 – Trainsorting

Erin is an engineer. She drives trains. She also arranges the cars within each train. She prefers to put the cars in decreasing order of weight, with the heaviest car at the front of the train.

Unfortunately, sorting train cars is not easy. One cannot simply pick up a car and place it somewhere else. It is impractical to insert a car within an existing train. A car may only be added to the beginning and end of the train.
Cars arrive at the train station in a predetermined order. When each car arrives, Erin can add it to the beginning or end of her train, or refuse to add it at all. The resulting train should be as long as possible, but the cars within it must be ordered by weight.
Given the weights of the cars in the order in which they arrive, what is the longest train that Erin can make?

Input

The first line is the number of test cases to follow. The test cases follow, one after another; the format
of each test case is the following:
The first line contains an integer 0<=n<=2000, the number of cars. Each of the following n lines contains a non-negative integer giving the weight of a car. No two cars have the same weight.

Output

Output a single integer giving the number of cars in the longest train that can be made with the given restrictions.

Explanation

Consider the first train car selected, suppose it is car i. From that single starting point, the train will grow in two independent directions: increasing weight and decreasing weight. Decreasing weights will go in the back and increasing weights in the front. To maximize the overall size of the train, you want to maximize the size of the increasing sequence plus the size of the decreasing sequence. You should therefore calculate this quantity for each possible starting car i and see for which car it is greatest. You subtract 1 when calculating the train size because both the increasing and decreasing sequences share the first car as a starting point, so it gets double-counted if you were to just add lis (i) and lds (i). lis and lds can be solved using dynamic programming easily.

We will calculate lis and lds from the end of an array.

 

Solution :

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

int solve(vector<int> &arr)
{
	vector<int> lis(arr.size(),0);
	vector<int> lds(arr.size(),0);

	lis[0] = 1;
	lds[0] = 1;
	int max = 0;
    for(int i = 1; i < arr.size(); i++)
    {
    	lis[i] = lds[i] = 1;
        for(int j = 0; j  < i ; j++)
        {
        	//int max =
        	if(arr[i] > arr[j] && lis[i] <= lis[j] +1)
        	{
        		lis[i] = lis[j] + 1;
        		//cout<<"lis = "<<lis[i]<<endl;
        	}

        	if(arr[i] < arr[j] && lds[i] <= lds[j] + 1)
        	{
        		lds[i] = lds[j] + 1;
        		//cout<<"lds = "<<lds[i]<<endl;
        	}
        }
    }

    for(int i  =0 ; i < arr.size(); i++)
    {
    	max = std::max(max, lis[i] + lds[i] -1);
    }
    cout<<max<<endl;

}

int main( )
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		if(n>0)
		{
    	vector<int> arr;
	    while(n--)
	    {
	    	int temp;
	    	cin>>temp;
	        arr.push_back(temp);
	        //cout<<temp<<" ";
	    }
	    //! IMPORTANT :  Start from end of an array
	    reverse(arr.begin(), arr.end());
	    	solve(arr);
		}
		else
		{
			cout<<"0"<<endl;
		}
	}
    return 0;
}

Card Sorting – Longest Increasing Subsequence

Arrange the cards in groups so that all the cards in a group are of the same color. Next, sort the cards in each group by their value. Calculate the lowest number of moves needed to arrange cards. A move consists of changing a position of one of his cards.

Input :
The first line of input file contains two integers C and N, number of cards of the same color separated by a space character.
Each of the next C*N lines contains a pair of two integers X and Y, 1 ≤ X ≤ C, 1 ≤ Y ≤ N, separated by a space character.

Example :
2 2
2 1
1 2
1 1
2 2
then output would be 2

sorting-card

Algorithm Paradigm: Longest Increasing Susequence

As the problem states that we need to find out lowest number of moves to arrange cards, it triggers that we need to find minimum Counting of moves to sort a array.
So first Lets see how to find out minimum number of moves to sort an array using lis
1. Find LIS(longest Increasing subsequence) of an array
2. Once we have found the LIS, then we know that we have to move all elements which are not in LIS, so the number of moves is length(array)-length(LIS)

Minimum number of moves to sort an array = LengthOfArray – LengthOfLIS

Now lets see the problem again , here we need to find out cheapest way of moves to sort cards in each group.
Lets understand its solution:

Suppose we have red, green, and blue cards with numbers 1 to 4.
All the same colour have to be together, and inside each group, the numbers must be sorted.
Therefore there are 3!=3*2*1=6 possible correct final orders:

0  1  2  3  4  5  6  7  8  9  10 11
R1 R2 R3 R4 B1 B2 B3 B4 G1 G2 G3 G4  (RBG)
R1 R2 R3 R4 G1 G2 G3 G4 B1 B2 B3 B4  (RGB)
B1 B2 B3 B4 R1 R2 R3 R4 G1 G2 G3 G4  (BRG)
G1 G2 G3 G4 R1 R2 R3 R4 B1 B2 B3 B4  (GRB)
B1 B2 B3 B4 G1 G2 G3 G4 R1 R2 R3 R4  (BGR)
G1 G2 G3 G4 B1 B2 B3 B4 R1 R2 R3 R4  (GBR)

Each order is determined by a permutation of the colours (shown in brackets).
This solution works by iterating over each permutation of the colours.
For each permutation:

  • we will compute array ‘v’ the correct position of each card for the given permutation.
  • Then we will find out Minimum number of moves to sort that array ‘v’ and store this value in min

Result is minimum of ‘min’ from all iterations.

For example:

Original Sequence:
R1 R2 R3 R4 G1 G2 G3 G4 B1 B2 B4 B3
If we have chosen (RGB) as one of the permutation , then array 'v' would be:
0  1  2  3  4  5  6  7  8  9  11 10
the longest increasing subsequence would be:
0  1  2  3  4  5  6  7  8  9 10
which is of length 11, so the answer is 12-11=1

Its my advise to you see this solution only if you have tried this problem many times.

C++ solution:

#include <iostream> 
#include <algorithm>
#include<climits>
#include <vector>
using namespace std; 
int BinarySearch(vector<int> &arr,int *small,int n, int value)
{
   int low = 0;
   int high = n-1;
   int mid;
   while (low < high)
   {
       mid = low + ((high - low) / 2);
       //! if array's mid value is greater then search value then select
       //! high as mid , this is where we are making it a ceil binary search
       if (arr[small[mid]] > value)
           high = mid;
       else if (arr[small[mid]] < value)
           low = mid + 1;
       else
           return mid;// found
   }
   return low;// not found
}
 
//! function to print longest Increasing Subsequence with nlog(n) complexity
int LIS(vector<int> &arr, int n)
{
    int *small = new int[n];
    int size = 0;
    for(int i=0 ; i<n ;i++)
    {
        if(i == 0)
        {
            small[size] = i;
        }
        //! Find the "index" of the smallest element in array small, which is >=than X,
        //! and change it to X. Here parent[indexOfX] = S[index - 1].
        else if(arr[i] <= arr[small[size]])
        {
            int pos = BinarySearch(arr,small,size+1,arr[i]);
            small[pos] = i;
        }
        //! parent[indexOfX] = Last Element Of S
        else
        {
            size = size+1;
            small[size] = i;
        }
    }
    delete [] small;
    return (size+1);
 
}
 
int matrix[4][100];
int main( )
{ 
    int n,c;
    //Get Numbers of different colors and number
    cin>>c>>n;
    vector<int>v(n*c);
    vector<int> color;
    vector<int> number;
    //Get color and its corresponding number
    for(int i = 0;i<n*c;i++)
    {
        int num,col;
        cin>>col>>num;
        color.push_back(col);
        number.push_back(num);
    }
    
    //per is used to do permutation of given number of colors
    vector<int> per;
    for(int i=0; i<c; i++)
    {
    	per.push_back(i);
    }
    int mini = INT_MAX;
    //For each permutation we will find minimum number of moves required to
    // sort array v'.
    do
	{
    	int count = 0;
		for(int i=0; i<c; i++)
		{
			for(int j=0; j<n; j++)
			{
				matrix[per[i]][j] = count++;
			}
		}
		//Generate array 'v'
		for(int i=0; i<n*c; i++)
		{
			v[i] = matrix[color[i]-1][number[i]-1];
		}
		//Get minimum of all permutation in variable mini
		mini = std::min(mini, (n*c) - LIS(v,n*c));
    }while(next_permutation(per.begin(), per.end()));
    
    cout<<mini;

    return 0;
}

Gist Link

References:
http://www.spoj.com/problems/MCARDS/ – MCARDS

Longest Increasing Subsequence in O(nlogn)

Today we are going to discuss longest increasing subsequence of an array using efficient algorithm with O(nlogn) complexity.

As we all know lis can also be solved by dynamic programming paradigm but that algorithm take O(n^2) time.

Let assume that arr[i] is input array from i = 0 to n

Let S[i] be defined as the smallest integer that ends an increasing sequence of length i.

Now iterate through every integer X of the input set arr[] and do the following:

1) If X > last element in S, then append X to the end of S. This essentially means we have found a new largest LIS.

2) Otherwise find the smallest element in S, which is greater then or equal ( >= ) to X, and change it to X. Because S is sorted at any time, the element can be found using binary search in log(N).

So, total runtime – N integers and a binary search for each of them – N * log(N) = O(N log N)

Now let’s understand above algorithm using real example:

Set of integers: 2 6 3 4 1 2 7 9 5 8
Just iterate through each integer in above array.

Steps:

0. S = {} - Initialize S to the empty set
1. S = {2} - New largest LIS
2. S = {2, 6} - New largest LIS
3. S = {2, 3} - Changed 6 to 3
4. S = {2, 3, 4} - New largest LIS
5. S = {1, 3, 4} - Changed 2 to 1
6. S = {1, 2, 4} - Changed 3 to 2
7. S = {1, 2, 4, 7} - New Largest LIS
8. S = {1, 2, 4, 7, 9} - New largest LIS
9. S = {1, 2, 4, 5, 9} - Changed 7 to 5
10. S = {1, 2, 4, 5, 8} - Changed 8 to 9

So the length of the LIS is 5 (the size of S).

Above algorithm is used to find length of LIS. To print the actual elements of LIS let’s modify algorithm to find the length and element of LIS.

To reconstruct the actual LIS we will use a parent[] array of length equal to input array. Where parent[i] be the predecessor of element with index i in the LIS ending at element with index i.

Also in the array S, we will not keep the actual integers, but their indices(positions) in the set. We do not keep {1, 2, 4, 5, 8}, but keep{4, 5, 3, 8, 9}.
2 6 3 4 1 2 7 9 5 8
So how do we update array parent[] let’s look at the above two points again:

Iterate through each element X of an input array arr[]
1) If X > last element in S, then parent[indexOfX] = LastElementOfS. This means the parent of the newest element is the last element of array S and then we will just prepend X to the end of S.

2) Otherwise find the index of the smallest element in S, which is >=than X, and change it to X. Here parent[indexOfX] = S[index – 1].

Here is a commented c++ program so go through each line one by one and let me know in case there is any doubt.

#include <iostream>
using namespace std;
//! @author : Rajul
//! code is poetry
 
//Program to find longest Increasing Subsequence in nlog(n) time
 
//! Function to do ceil binary search
//! Usage: To return either position of search's value or position of smallest
//! elememt in array which is greater then value of search
//! Here n = size of array small
int BinarySearch(int *arr,int *small,int n, int value)
{
   int low = 0;
   int high = n-1;
   int mid;
   while (low < high)
   {
       mid = low + ((high - low) / 2);
       //! if array's mid value is greater then search value then select
       //! high as mid , this is where we are making it a ceil binary search
       if (arr[small[mid]] > value)
           high = mid;
       else if (arr[small[mid]] < value)
           low = mid + 1;
       else
           return mid;// found
   }
   return low;// not found
}
 
//! function to print longest Increasing Subsequence with nlog(n) complexity
int LIS(int *arr, int n)
{
    int *small = new int[n];
    int *parent = new int[n];
    int size = 0;
    for(int i=0 ; i<n ;i++)
    {
        if(i == 0)
        {
            small[size] = i;
            parent[i] = -1;
        }
        //! Find the "index" of the smallest element in array small, which is >=than X,
        //! and change it to X. Here parent[indexOfX] = S[index - 1].
        else if(arr[i] <= arr[small[size]])
        {
            int pos = BinarySearch(arr,small,size+1,arr[i]);
            small[pos] = i;
            if(pos != 0)
            {
                 parent[i] = small[pos-1];
            }
    	}
        //! parent[indexOfX] = Last Element Of S
        else
        {
            size = size+1;
            small[size] = i;
            parent[i] = small[size-1];
        }
    }
    cout<<"Length of Longest Increasing Subsequence = "<<size+1<<endl;
 
    int pos = small[size];
    //! print Longest Increasing Subsequence
    while(size >=0)
    {
        cout<<arr[pos]<<endl;
        pos = parent[pos];
        size--;
    }
}
 
int main( )
{
    int arr[] = {99, -7, 10, 9, 2, 3, 8, 8, 1, 2, 3};
    unsigned int size = sizeof(arr)/sizeof(int);
    LIS(arr,size);
    return 0;
}

Github Gist Link

 

Beautiful People | Dynamic programming Set 5

There is a club with N members.This is a very prestigious club, its members are very rich and therefore extraordinary people, so they often extremely hate each other. Strictly speaking, i-th member of the club Mr X hates j-th member of the club Mr Y if Si ≤ Sj and Bi ≥ Bj or if Si ≥ Sj and Bi ≤ Bj (if both properties of Mr X are greater then corresponding properties of Mr Y, he doesn’t even notice him, on the other hand, if both of his properties are less, he respects Mr Y very much).Your task it to invite as many people as possible.

print the maximum number of the people that can be invited to the party and also print numbers of members to be invited in arbitrary order. If several solutions exist, output any one.

Example:
Strength[] = {1, 1, 2, 2}
Beauty[] = {1, 2, 1, 2}

In above case we can invite maximum 2 people with index 1 and 4 i.e {1,1} , {2,2}
So Output is
2
1 4

Solution:
Above problem can be solved using dynamic programming paradigm and specifically using Longest Increasing Subsequence technique.

1) Optimal Sub Structure
Let array member[] contains a members Strength and Beauty factor. D[i] contain the maximum number of people club can invite till index i such that member[i] is part of invitation and memeber[i] is the last element of invitation, then D[i] can be written as

D(i) = { 1 + Max ( D(j) ) } where j < i and D[i] = max{ D[j] +1 }for j < i and Strength[j] < Strength[i] and Beauty[j] < Beauty[i] , if there is no such j then D(i) = 1

To get Maximum number of people we need to return max(D[i]) , where 0 < i < n and while updating D[i] , take an array P[i] which will store position or index of member which can be invited in party. Time Complexity : O(n2) c++ program: [code language="cpp" gutter="false"] #include <iostream> #include <vector> #include <algorithm> using namespace std; //Structure to store person informartion typedef struct person{ long int s; long int b; int ind; person(long int s,long int b,int ind); } person; //! where s = strength, b = beauty factor. ind = index of memeber person::person(long int s, long int b, int ind): s(s),b(b),ind(ind) {} int compare(const person &a, const person &b) { return a.s < b.s; } int main( ) { vector<person> member; member.push_back(person(1,1,0)); member.push_back(person(1,2,1)); member.push_back(person(2,1,2)); member.push_back(person(2,2,3)); int n = (int)member.size(); //! Take a array d[] which store maximum number of people can be invited in a party vector<long int> d(n,1); //! Take array p[] to store position of member invited in a party vector<long int> p(n,-1); long int max = -1; long int bestEnd = -1; sort (member.begin(), member.end(), compare); for(int i = 1 ; i < n ;i++) { for(int j = i-1 ; j>=0 ; j--) { if(((d[j] + 1) > d[i]) and (member[j].b < member[i].b) and (member[j].s < member[i].s)) { d[i] = d[j]+1; p[i] = j; } } if(max < d[i]) { max = d[i]; bestEnd = i; } } cout<<max<<endl; if(bestEnd != -1) //! print position of members while(bestEnd not_eq -1) { cout<<member[bestEnd].ind+1<<" "; bestEnd = p[bestEnd]; } return 0; } [/code] References: http://acm.sgu.ru/problem.php?contest=0&problem=199

Number of intersections between pairs of diagonals in a convex polygon

Consider a convex polygon with N vertices, with the additional property that no three diagonals intersect in a single point. Find the number of intersections between pairs of diagonals in such a polygon.

The figure below shows one such polygon with 6 vertices.

-en-img-0001

Note that a polygon is convex if all of its interior angles are less than 180 degrees.

Input

The first and only line of input contains a single integer N,3N100 denoting the number of vertices.

Output

(Number of intersections of diagonals) mod 1000000007

 

For Example :

For N =3 , Output = 0

For N = 4, Output = 1

For N= 6, Output = 15

 

Solution:

A diagonal is a line segment that joins non-adjacent vertices.

So we have to choose any 4 vertices from given vertices.

There are (nC4) ways to choose 4 vertices. If the polygon is strictly convex, then exactly one pair of the lines joining the vertices meets in the interior of the polygon. So the required number of intersection points of diagonals is (nC4).

It is easy to calculate nCr in any programming language.

We recommend to write program by yourself.

C++ implementation to  find Number of intersections between pairs of diagonals in a convex polygon.

#include<iostream>

using namespace std;
const long long int mod = 1000000007;

long long modPow(long long a, long long x, long long p) {
    //calculates a^x mod p in logarithmic time.
    long long res = 1;
    while(x > 0) {
        if( x % 2 != 0) {
            res = (res * a) % p;
        }
        a = (a * a) % p;
        x /= 2;
    }
    return res;
}

long long modInverse(long long a, long long p) {
    //calculates the modular multiplicative of a mod m.
    //(assuming p is prime).
    return modPow(a, p-2, p);
}

// Main function to calculate nCr
long long GetNumberOfIntersection(long long n, long long k, long long p) {
// calculates C(n,k) mod p (assuming p is prime).

    long long numerator = 1; // n * (n-1) * ... * (n-k+1)
    for (long long int i=0; i<k; i++) {
        numerator = (numerator * (n-i) ) % p;
    }

    long long denominator = 1; // k!
    for (long long int i=1; i<=k; i++) {
        denominator = (denominator * i) % p;
    }

    // numerator / denominator mod p.
    return ( numerator* modInverse(denominator,p) ) % p;
}

int main()
{
	cin>>n;
	cout<<GetNumberOfIntersection(n,4,mod)<<"\n";
	return 0;
}

Build a Wall From Bricks | Dynamic Programming Set 4

Given a value N , if we want to build a wall of size 4xN and we have an infinite supply of bricks of size 1×4 and 4×1  , In How many way we can build that wall using bricks?

For Example for N=4 ,

Wall size become 4×4 ,

There are two ways to build wall of size 4×4 = {4 bricks of size 1×4 placed vertically, 4 bricks of size 4×1 placed horizontally}

i.e answer is 2

1) Optimal Substructure
To count the total number of ways we can divide all set solution in two ways

  • Solution that contain 4×1 brick
  • Solution that contain 1×4 brick

Let Wall[n] contain the total number of ways to build a wall of size 4xN from 4×1 and 1×4 brick.
then Wall[n] can be written as Wall[n-1] + Wall[n-4]
i.e Wall[n] = Wall[n-1] + Wall[n-4]

  • When we include brick of 4×1 dimension then we need to solve for only n-1
  • When we include brick of 1×4 dimension then we have to place four bricks of same dimension , So we have to solve for n-4

So Recurrence relation become Wall[n] = Wall[n-1] + Wall[n-4]

2) Overlapping Sub-problems
Let take n = 4

                Wall[5]
               /       \
        Wall[4]         Wall[1]
        /    \           |
    Wall[3]  Wall[0]     Wall[0]

As we can see Wall[0] is solving twice so this problem has overlapping subproblem property.
Since this problem has both Optimal Substructure and Overlapping SubProblem property So this problem has both properties of Dynamic Programming.

Recomputing of same subProblem can be avoided by taking temporary array Wall[n] and build this array in a bottom up manner.


#include<iostream>
#include<vector>
using namespace std;
//We will construct this array in bottom up manner
int Wall[41] = {0};
int CountNoOfWalls(int n)
{
	if(n<0)
	return 0;
        //Base Case: For i = 0,1,2,3 , Wall[i] = 1
	for(int i=0 ; i<4;i++)
	{
		Wall[i] = 1;
	}
	if(n<4)
	{
		return Wall[n];
	}
        //Fill rest of array in bottom up manner
	for(int i=4 ; i<=n;i++)
	{
                /* Total count of solution = Solution that contain brick 4x1 size
                 * Solution that contain brick 1x4 size
                 */
		Wall[i] = Wall[i-1] + Wall[i-4];
	}
	return Wall[n];
}
int main()
{
	int t;
	int n;
	cin>>n;
	//Find Total number of ways to build wall of size 4xN
        cout<<CountNoOfWalls(n);
}

Time Complexity : O(n)

Binary Indexed Tree | Fenwick Tree

A Fenwick tree or binary indexed tree is a data structure that was first used for data compression. It is often used for storing frequencies and manipulating cumulative frequency tables.

Lets take a following problem to understand Binary Indexed Tree.

There are n shelves in a library and possible query may be:

1. Add book in ith shelf.

2. Sum total number of books from jth shelf to kth shelf.

A[] contain no. of books in ith shelf.


A[] = [5] [1] [8] [11] [52] [28] [0]

       1   2   3     4    5    6   7

Naive solution has following Time complexity for above query:

Query 1 : O(1)

Query 2 : O(n) , as in worst case(for cumulative frequency of nth element) we have to traverse whole array.

For example : cumulative frequency of 5th element is = A[1] + A[2] + A[3] + A[4] + A[5] ~ O(n)

Using Binary Index tree we can reduce down Time complexity from O(n) to O(logn).

Concept behind Binary Indexed Tree:

Lets consider frequency of 7 different element


Frequency table :  [5] [1]  [8]  [11] [52] [28]  [0]

Cumulative table : [5] [6]  [14] [25] [77] [105] [105]

                    1   2   3     4    5    6     7

Using above representation of Frequency table we can change frequency in O(1) time. Like If we want to increment frequency of 3rd element by 7 i.e from 8 to 15 then for cumulative frequency we have to add all element before 3rd element, which is pretty slow if take a large n.

After increment 3rd element by 7 frequency table and cumulative table become:


Frequency table :  [5] [1]  [15]  [11] [52] [28]  [0]

Cumulative table : [5] [6]  [21]  [32] [84] [112] [112]

                    1   2    3     4    5     6     7

The first major insight we need to get from here to a binary indexed tree is the following: rather than continuously recomputing the sum of the array elements that precede a particular element, what if we were to precompute the total sum of all the elements before specific points in the sequence? If we could do that, then we could figure out the cumulative sum at a point by just summing up the right combination of these precomputed sums.

Basic Idea is like Each integer can be represented as sum of powers of two. In the same way, cumulative frequency can be represented as sum of sets of subfrequencies.

One way to visualize this is to change the representation from being an array to being a binary tree of nodes. Each node will be annotated with a value that represents the cumulative sum of all the nodes to the left of that given node. For example, suppose we construct the following binary tree from these nodes:


             4

          /     \

         2       6

        / \     / \

       1   3   5   7

Now, we can represent each node by storing the cumulative sum of all the values including that node and its left sub-tree. For example,

value at node 4 would contain sum of its left tree’s nodes i.e [node1] + [node2] + [node3] + [node4] = 5 + 1 + 15 + 11 = 32

similarly, for node 5 there is no child so its value would be same its value i.e 52


Before:

[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]

  1     2     3     4     5     6     7

Cumulative table : [5] [6]  [21]  [32] [84] [112] [112]

                    1   2    3     4    5     6     7

After:

                 4

               [+32]

              /     \

           2           6

         [ +6]       [+80]

         /   \       /   \

        1     3     5     7

      [ +5] [+15] [+52] [ +0]

Determine the cumulative sum
Given above tree structure, it’s easy to determine the cumulative sum of any index.

Lets see how:

1. First write each index in its binary notation like this:


                100(4)

                [+32]

              /      \

         010(2)       110(6)

        [+6]           [+80]

        /   \          /   \

     001(1)  011(3) 101(5) 111(7)

      [+5] [+15]    [+52]   [+0]

Cumulative table : [5] [6]  [21]  [32] [84] [112] [112]

                    1   2    3     4    5     6     7

2. Here, Take all binary numbers one by one and find the very last 1 that was set in the number, then drop that bit off, along with all the bits that come after it. You are now left with the following:


              (empty)(4)

               [+32]

              /     \

           0(2)      1(6)

         [+6]        [+80]

         /   \       /   \

     00(1)   01(3) 10(5)  11(7)

      [+5] [+15]   [+52] [ +0]

Cumulative table : [5] [6]  [21]  [32] [84] [112] [112]

                    1   2    3     4    5     6     7

3. Treat 0 means “left” and 1 means “right”

4. If we want to look up cumulative frequency of ith index then take its bit number and then move from root to that element in downwards direction using that bit pattern. During this look up we will just care about right links.

For Example :

A) Look up of 5:

Bit number of 5 is 10 ,so path is RIGHT–>LEFT ;

i) Start from element(4) –move right—>(6) | sum = 32

ii) Element(6)–move LEFT–>Element(5) | sum = sum + 0 , as we have move left so we are ignoring 80

iii) We are at our target element(5) , so add 52 to sum | sum = sum + 52

so cumulative sum of element(5) is 84

during this we have traverse only equal to height of binary tree, So time complexity would be O(logn).

B) Look up of 3:

Bit number of 3 is 01 , so path is LEFT–>RIGHT ;

i) Start from element(4) –move LEFT–>(2) | sum = 0, as we moved left , so we are ignoring 32

ii) Element(2)–>move RIGHT–>(3) | sum = sum + 6, add current element value to sum

iii) Found target element(3) , so add 15 to sum | sum = sum + 15

So cumulative sum of element(3) become 21

Update or increment the frequency of any element


              (empty)(4)

               [+32]

              /     \

           0(2)      1(6)

         [+6]        [+80]

         /   \       /   \

     00(1)   01(3) 10(5)  11(7)

      [+5]  [+15]  [+52]   [ +0]

Given the above tree structure it is easy to update/increment frequency of any element.
1. Treat 0 means “left” and 1 means “right”

2. If we want to update frequency of ith index then take its bit number and then move from root to that element in downwards direction using that bit pattern. During this look up we will just care about left links.

For example:

A) Update frequency of  1st index by 5 :

Bit number of 1 is 00 ,so path is LEFT–>LEFT ;

i) Start from root element i.e 4 and add 5 to this node. i.e 32+5 = 37

ii) Move to left direction i.e to element(2) and add 5 to this element. i.e 6 + 5 = 11

iii) Then again move to left direction i.e to target element and add 5 to this element too. 5+5 = 10

So resultant tree become:


              (empty)(4)

               [+37]

              /     \

           0(2)      1(6)

         [+11]        [+80]

         /   \       /   \

     00(1)   01(3) 10(5)  11(7)

     [+10]   [+15] [+52]   [+0]

 

during this we have traverse only equal to height of binary tree, So time complexity would be O(logn).

How to isolate last non-zero digit

Let num be the integer whose last digit we want to isolate. In binary notation num can be represented as a1b, where a represents binary digits before the last digit and b represents zeroes after the last digit.

Integer -num is equal to (a1b)¯ + 1 = a¯0b¯ + 1. b consists of all zeroes, so b¯ consists of all ones. Finally we have
-num = (a1b)¯ + 1 = a¯0b¯ + 1 = a¯0(0…0)¯ + 1 = a¯0(1…1) + 1 = a¯1(0…0) = a¯1b.
Now, we can easily isolate the last digit, using bitwise operator AND with num and -num

       a 1b
&      a¯1b
--------------------
= (0...0)1(0...0)

In the next post will see implementation part to see How to Update and Look up cumulative frequency.

Maximum Sum Contiguous Subsequence | Dynamic Programming Set 3

Given an array A having n integers. We need to give an algorithm to find a contiguous subseqnence (A[i], A[i+1], …, A[j]) such that the sum of the elements in that subsequence is maximized. (Note that, in general, there may be more than one such optimal subsequence.

Example : {2,-4,1,2} -> 1 and {1,-3,4,-2,-1,7} -> 8

Note:If there are no negative number then the solution is just the sum of all element in the array 😛

Method:1
Algorithm Paradigm : Dynamic Programming

Let MSCS[i] represents maximum sum over all the elements ending at i including A[i]
Consider the following array

------------------------------------
|    |    |    |  ? |    |    |    |
------------------------------------
 A[0]           A[i]

For Finding maximum element we have to do one of the following and select max of them:
Either extend old sum with ith element A[i]
or Start with new Element starting with A[i]
i.e

MSCS[i] = Max{ MSCS[i-1] + A[i] , //extend old sum by A[i]
             { 0 //Start new window with A[i]

Time and Space Complexity: O(n) and O(n)

C++ implementation:

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

int MaxSumContSub(int arr[],int size)
{
    int *mscs = new int[size];
    if(size == 0)
        return 0;
    mscs[0] = arr[0];
    for(int i = 1; i <  size ;i++)
    {
        mscs[i] = std::max((mscs[i-1]+arr[i]),0);
    }
    int max = -1;
    for(int i = 0;i<size;i++)
    {
        if(max < mscs[i])
        {
            max = mscs[i];
        }
    }
    return max;
}
int main( )
{ 
    int arr[] =  {1,-3,4,-2,-1,7};
    int n = sizeof(arr)/sizeof(int);
    cout<<"sum = "<<MaxSumContSub(arr,n);
    return 0;
}