Month: February 2014

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.

Advertisements

“Output the answer modulo 10^9 + 7”

You might have noticed that many programming problems ask you to output the answer “modulo 1000000007 (10^9 + 7)”. In this post I’m going to discuss what this means and the right way to deal with this type of questions. I should have covered this topic earlier because questions involving this are not uncommon. Anyways, here it is…

First of all, I’d like to go through some prerequisites.

The modulo operation is the same as ‘ the remainder of the division ’. If I say a modulo b is c, it means that the remainder when a is divided by b is c. The modulo operation is represented by the ‘%’ operator in most programming languages (including C/C++/Java/Python). So, 5 % 2 = 1, 17 % 5 = 2, 7 % 9 = 7 and so on.


WHY IS MODULO NEEDED..

The largest integer data type in C/C++ is the long long int; its size is 64 bits and can store integers from ( –2^63 ) to ( +2^63 -1 ) . Integers as large as 9 X 10^18 can be stored in a long long int.

But in certain problems, for instance when calculating the number of permutations of a size n array, even this large range may prove insufficient. We know that the number of permutations of a size n array is n!. Even for a small value of n, the answer can be very large. Eg, for n=21, the answer is 21! which is about 5 x 10^19 and too large for a long long int variable to store. This makes calculating values of large factorials difficult.

So, instead of asking the exact value of the answer, the problem setters ask the answer modulo some number M; so that the answer still remain in the range that can be stored easily in a variable.

Some languages such as Java and Python offer data types that are capable of storing infinitely large numbers. But data type size is not the only problem. As the size of the number increases the time required to perform mathematical operations on them also increases.

There are certain requirements on the choice of M:
1. It should just be large enough to fit in an int data type.
2. It should be a prime number.
10^9 + 7 fits both criteria; which is why you nearly always find 10^9 + 7 in modulo type questions.
I’ve explained the logic behind the 2nd point in NOTES.

HOW TO HANDLE QUESTIONS INVOLVING MODULO:

Some basic knowledge of modulo arithmetic is required to understand this part.

A few distributive properties of modulo are as follows:
1. ( a + b ) % c = ( ( a % c ) + ( b % c ) ) % c
2. ( a * b ) % c = ( ( a % c ) * ( b % c ) ) % c
3. ( a – b ) % c = ( ( a % c ) – ( b % c ) ) % c ( see note )
4. ( a / b ) % c NOT EQUAL TO ( ( a % c ) / ( b % c ) ) % c
So, modulo is distributive over +, * and – but not / .

One observation that I’d like to make here is that the result of ( a % b ) will always be less than b.

If I were to write the code to find factorial of a number n, it would look something like this:

long long factorial(int n,int M)
{
	long long ans=1;
	while(n&gt;=1)
	{
		ans=(ans*n)%M;
		n--;
	}
	return ans;
}

Notice that on line 6, I performed the modulo operation at EACH intermediate stage.
It doesn’t make any difference if we first multiply all numbers and then modulo it by M, or we modulo at each stage of multiplication.
( a * b * c ) % M is the same as ( ( ( a * b ) % M ) * c ) % M

But in case of computer programs, due to size of variable limitations we avoid the first approach and perform modulo M at each intermediate stage so that range overflow never occurs.
So the following approach is wrong:

long long factorial(int n,int M)//WRONG APPROACH!!!
{
	long long ans=1;
	while(n&gt;=1)
	{
		ans=ans*n;
		n--;
	}
        ans=ans%M;
	return ans;
}

The same procedure can be followed for addition too.
( a + b + c ) % M is the same as ( ( ( a + b ) % M ) + c ) % M
Again we prefer the second way while writing programs. Perform % M every time a number is added so as to avoid overflow.

The rules are a little different for division. This is the main part of this post;
As I mentioned earlier,
( a / b ) % c NOT EQUAL TO ( ( a % c ) / ( b % c ) ) % c which means that modulo operation is not distributive over division.
The following concept is most important to find nCr (ways of selecting r objects from n objects) modulo M. (As an example, I’ve included the code to find nCr modulo M at the end of this post)
To perform division in modulo arithmetic we need to first understand the concept of modulo multiplicative inverse.

Lets go over some basics first.

The multiplicative inverse of a number y is z iff (z * y) == 1.

Dividing a number x by another number y is same as multiplying x with the multiplicative inverse of y.

x / y == x * y^(-1) == x * z (where z is multiplicative inverse of y)

In normal arithmetic, the multiplicative inverse of y is y^(-1); which will correspond to some float value. Eg. Multiplicative inverse of 5 is 0.2, of 3 is 0.333… etc.
But in modulo arithmetic the definition of multiplicative inverse of a number y is a little different. The modulo multiplicative inverse ( MMI ) of a number y is z iff (z * y) % M == 1.

Eg. if M= 7 the MMI of 4 is 2 as ( 4 * 2 ) %7 ==1,
if M=11, the MMI of 7 is 8 as ( 7 * 8 )%11 ==1,
if M=13, the MMI of 7 is 2 as ( 7 * 2 ) % 13==1.
Observe that the MMI of a number may be different for different M.
So, if we are performing modulo arithmetic in our program and we need the result of the operation x / y, we should NOT perform

z=(x/y)%M;

instead we should perform

y2=findMMI(y,M);
z=(x*y2)%M;

Now one question remains.. How to find the MMI of a number n.
The brute force approach would look something like this

int findMMI_bruteforce(int n,int M)
{
	int i=1;
	while(i&lt;M)// we need to go only uptil M-1
	{
		if(( (long long)i * n ) % M ==1)
			return i;
		i++;
	}
	return -1;//MMI doesn't exist
}

The complexity of this approach is O(M) and as M is commonly equal to 10^9 + 7, this method is not efficient enough.

There exist two other algorithms to find MMI of a number. First is the Extended Eucledian algorithm and the second using Fermat’s Little Theorem.

If you are new to modulo arithmetic, you’ll probably not find these topics easy to understand.
These algorithms require prerequisites. If you want to read them they are very well explained on many online sources and some of you will study them in depth in your college’s algorithm course too.
I’ll keep this post simple for now and only give the code using Fermat Little Theorem.

int fast_pow(long long base, long long n,long long M) 
{
    if(n==0)
       return 1;
    if(n==1)
	return base;
    long long halfn=fast_pow(base,n/2,M);
    if(n%2==0)
        return ( halfn * halfn ) % M;
    else
        return ( ( ( halfn * halfn ) % M ) * base ) % M;
}
int findMMI_fermat(int n,int M)
{
	return fast_pow(n,M-2,M);
}

This code uses a function fast_pow() that is used to calculate the value of base^p. Its complexity is O(log p). It is a very efficient method of computing power of a number.
It is based on the fact that to find a^n, we just need to find a^(n/2) and the required answer will be a^(n/2) * a^(n/2) if n is even; and a^((n-1)/2) * a^((n-1)/2) * a if n is odd ( if n is odd n/2 == (n-1)/2 in most programming languages ).

NOTE:

1. For M to be a prime number is really important. Because if it is not a prime number then it is possible that the result of a modulo operation may become 0. Eg. if M=12 and we perform ( 8 * 3 ) % 12, we’ll get 0. But if M is prime then ( ( a % M ) * ( b % M ) ) % M can never be 0 (unless a or b == 0)
[EDIT: Remember that in programming contests, M is greater than all the other values provided. So a case like (14*3)%7 can never occur. ]

2. If M is prime then we can find MMI for any number n such that 1<=n<M
3. ( a – b ) % c = ( ( a % c ) – ( b % c ) ) %c is fine mathematically. But, while programming, don’t use

// if b&gt;a, you'll get wrong result this way 
a=(a%c);
b=(b%c);
ans = ( a - b ) % c; 

instead use

a=a%c;
b=b%c;
ans =  ( a - b + c ) % c;

% works differently with -ve numbers

IMPORTANT:
1. If n1,n2 are int type variables and M=10^9+7, then the result of ( n1 * n2 ) % M will surely be < M ( and capable of fitting in a simple int variable). BUT the value of ( n1 * n2 ) can be greater than the capacity of an int variable. Internally, first ( n1 * n2 ) is computed. So, to avoid overflow either declare n and / or m as long long int OR use explicit type casting (( long long ) n * m ) % M.

As an example, here is the code to find nCr modulo 1000000007, (0<=r<=n<=100000)


int fast_pow(long long base, long long n,long long M)
{
    if(n==0)
       return 1;
    if(n==1)
    return base;
    long long halfn=fast_pow(base,n/2,M);
    if(n%2==0)
        return ( halfn * halfn ) % M;
    else
        return ( ( ( halfn * halfn ) % M ) * base ) % M;
}
int findMMI_fermat(int n,int M)
{
    return fast_pow(n,M-2,M);
}
int main()
{
    long long fact[100001];
    fact[0]=1;
    int i=1;
    int MOD=1000000007;
    while(i&lt;=100000)
    {
        fact[i]=(fact[i-1]*i)%MOD;
        i++;
    }
    while(1)
    {
        int n,r;
        printf(&quot;Enter n: &quot;);
        scanf(&quot; %d&quot;,&amp;n);
        printf(&quot;Enter r: &quot;);
        scanf(&quot; %d&quot;,&amp;r);
        long long numerator,denominator,mmi_denominator,ans;
        //I declared these variable as long long so that there is no need to use explicit typecasting
        numerator=fact[n];
        denominator=(fact[r]*fact[n-r])%MOD;
        mmi_denominator=findMMI_fermat(denominator,MOD);
        ans=(numerator*mmi_denominator)%MOD;
        printf(&quot;%lld\n&quot;,ans);
    }
    return 0;
}

Feedback

I have posted a total of ten algorithm/programming related topics on CodeAccepted now. I’d like to get your feedback on my posts so far. My aim in starting this blog was that programmers who are new to competitive programming could benefit from it; I’d like to know how much successful or unsuccessful I’ve been.
Your feedback is very essential. You may choose to remain anonymous.

Click FEEDBACK FORM to view the form.

Algorithm #6: Backtracking

I think we are ready to discuss Backtracking now. Last time I posted about recursion; I hope it’ll help you with this topic.
When I told you about Bit Masking, I said that it is a brute force approach to solve the Subset Sum problem. And better algorithms than Bit Masking exist. Backtracking is one of those methods.

In my post about Bitmasking I discussed the Subset Sum problem. Subset sum problem is an NP complete problem. In a nutshell, NP complete is a set of computational problems for which no efficient solution that will give a reasonably good run time for very large test cases has yet been found. The complexity of Bitmasking is O(2^n) and it becomes useless at n>25 due to the dramatic increase in the number of subsets that need to be analysed.

In subset sum problem, we are given a set of positive numbers. We are asked if it is possible to find a subset of this set such that the sum of numbers of the selected subset is exactly m ( a positive number).
Backtracking can be viewed as an attempt to improve the Bitmasking algorithm. Just to remind you, in Bitmasking we analyse all the possible subsets of the given set to find a possible solution subset.
But in backtracking, we will intelligently reject the subsets that we know for sure will not lead to a solution.

For example, suppose we have n=5 and the set is {5,31,3,7,6}. We have to select a subset such that the sum of numbers of the selected subset is 11. Now it is obvious that no subset containing the number 31 can have a sum of 11. So, no subset involving the number 31 will lead to a solution. So, we should not consider those subsets that have 31 in them. We should not waste our time analyzing those subsets. This is the principle of Backtracking. As soon as we come to know that selecting 31 will not lead to a solution, we do not continue analysing subsets with 31 in them.

Below is the code to solve the subset sum problem using backtracking:
backtrack() is a function that takes the set of numbers ( nums[ ] ), the total number of elements ( n ), and the sum that we require ( requiredsum ).
It returns 1 if it is possible to obtain a sum of exactly requiredsum, and 0 if it is not possible to do so.

int backtrack(int nums[],int at,int n,int sumrequired)
{
    if(sumrequired==0)
        return 1;
    if(sumrequired<0)
        return 0;
    if(at==n)
        return 0;
    if(backtrack(nums,at+1,n,sumrequired-nums[at])==1)
        return 1;
    if(backtrack(nums,at+1,n,sumrequired)==1)
        return 1;
    return 0;
}

I mentioned in my post about recursion that programs implemented using recursion can be incredibly short and incredibly difficult to understand. This is an example of that!

Following are the important points about this algorithm:

1. The at variable tells which number’s fate we are deciding. If in a recursive instance at is i, it means that we are currently deciding the fate of the ith number.
2. If the sumrequired variable is 0, it means that we do not need to select any more numbers, so we return the success code (which is 1).
3. A negative sum of numbers can never be achieved because all numbers can have only positive values; so if sumrequired is negative, we return the failure code (which is 0).
4. The recursive call at line 9 represents the case where we select the current number ( nums[at] ). When we select the current number, our problem reduces to selecting numbers from the set {nums[at+1], nums[at+2],…, nums[n-1]} such that their sum is (requiredsum – value[at]) .
5. The recursive call at line 11 represents the case where we don’t select the current number ( nums[at] ). If we don’t select the current number, our problem reduces to selecting numbers from the set {nums[at+1], nums[at+2],…, nums[n-1]} such that their sum is requiredsum itself.

I defined in my previous post that recursion is when we decompose a problem into a smaller problem.
See points 4 and 5 carefully. I am reducing my current problem of finding a solution subset from the set {nums[at],nums[at+1],nums[at+2],…,nums[n-1]} to finding a solution subset from the set {nums[at+1], nums[at+2],…, nums[n-1]}.
Whenever I find a solution (i.e. when requiredsum =0), all recursive calls will terminate one by one and 1 will be returned at each level.

At any time if requiredsum becomes less than 0, it means that the numbers that we have selected till now have their sum greater than the initial requiredsum already . So there’s no point in going furthur. Therefore, we return 0; which denotes that the current choices of elements will not lead to any solution.

In the test case I discussed before (with n=5 and the set of numbers as {5,31,3,7,6} and requiredsum=11),
if we select the number 31, the value of requiredsum will become < 0 in the next recursive call. And that recursive instance will immediately return 0; ( see point 2 )it will not go on deciding the fate of the rest of the numbers. In this way we simply discarded the subsets including the number 31.

The worst case complexity of this algorithm is same as Bitmasking i.e. O(2^n). But it offers a better execution time as it deliberately and intelligently skips some subsets.

PROBLEMS:
PAYING UP (on Codechef)

As it is with all recursive solutions, the code may seem overwhelming at first. I suggest that you look at the order of recursive calls I showed in the last post ( here ) and try to trace the way recursive calls are made in this case.