UVa 530: Binomial Showdown

UVa 530: Binomial Showdown

Written by on 6 June 2012

Topics: UVa Online Judge

Problem 530 at the UVa Online Judge, also known as Binomial Showdown, asks us to compute the number of ways one can choose elements out of elements, not taking order into account. The problem is a classical one ( choose , anyone?), but with a twist. The input numbers are big, and we need to be really careful not to overflow integers in our intermediate computations. We discover a formula that has smaller intermediate values than the direct formula, and with one more small observation, we’re done.

Interpretation

We are given two integers, and , where and . It is not explicitly stated how big can be, but it is likely safe to assume it fits in a 32-bit integer (but as a general rule: don’t assume anything). The problem statement tells us to compute the number of ways one can choose elements out of elements, not taking order into account. The problem statement is of course talking about the binomial coefficients, which most people recognise as choose , , or .

The problem setter is very kind to us this time. He tells us that the result will fit into a 32-bit integer, but warns us that intermediate results may or may not fit into a 32-bit integer, all depending on the algorithm used. That most likely means that the straight-forward solution will not work, but we are still just exploring the problem, so that’s where we’ll start anyway.

Implementation

Everyone should remember the basic formula for the binomial coefficients, but in case someone has forgot, here it is:

Let’s use this formula to get a basic solution to test (we’ll also use long integers, just in case):

// computes n!
public static long Factorial(int n) {

	long res = 1;

	// n! = 1 * 2 * 3 * ... * (n - 1) * n
	for (int i = 1; i <= n; i++) {
		res *= i;
	}

	return res;
}

// computes n choose k
public static long Choose(int n, int k) {

	// n choose k = n! / (k! * (n - k)!)
	return Factorial(n) / (Factorial(k) * Factorial(n - k));
}

// the main method
public static void main(String[] args) throws Exception
{
	Scanner in = new Scanner(System.in);
	PrintWriter out = new PrintWriter(System.out, true);

	// read every test case
	while (true) {

		// read n and k
		int n = in.nextInt(),
			k = in.nextInt();

		// if n = 0 and k = 0, then we are supposed to stop
		if (n == 0 && k == 0) {
			break;
		}

		// print n choose k
		out.println(Choose(n, k));
	}
}

We can try the example test data on our current solution. We will find out that the solution works for the first two test cases, but the last one is wrong. Why? Because, like the problem setter warned us, intermediate computations are overflowing integers (and in this case, they’re even overflowing long integers). Where is the overflow happening? If you look closely, you can see that we are computing (at least in the last test case), and that is a huge number. Let’s explore the formula to see if we can’t somehow get rid of computing the whole factorial at once.

Let’s start by expanding the factorials:

If we then cancel common factors from the top and the bottom , we get:

We can rewrite this as the following programmer-friendly product:

What’s good about this formula is that it removes unnecessary factors from the computation, resulting in smaller intermediate computations. This product can easily be implemented with a for-loop. We’ll just get rid of the Factorial method and modify our Choose function.

// computes n choose k
public static long Choose(int n, int k) {

	long res = 1;

	// n choose k = the product of (n - k + i) / i for i = 1..k
	for (int i = 1; i <= k; i++) {
		res = res * (n - k + i) / i;
	}

	return res;
}

If we now try the test cases provided in the problem, we get all of them correct. Yay for us! Are we done yet? Well, almost. There is one tiny thing we have left to consider.

Analyzing algorithms is a vital skill for any programmer that needs to work with algorithms, which is every programmer. If we analyze the running time of the Choose function, we find that it runs in time, or time proportional to . That means that, as gets larger, the algorithm needs more time to finish. In our scenario, can be as big as , and is any valid positive 32-bit integer (so . choose is equal to , so it’s a perfectly valid input. If we feed this input to our current solution, it takes way too long to compute the result (more than a couple of seconds on my computer). So how can we fix this? One identity of the binomial coefficients is the following:

It can easily be derived:

This is beneficial to us, because now we can either compute choose or choose , and still get the same result. It takes less time to compute the smaller of and , so that’s the one we’ll pick. Only minor modifications are needed to implement this.

// computes n choose k
public static long Choose(int n, int k) {

	// n choose k is equal to n choose (n - k),
	// so we pick the one that is easier to compute,
	// which is the smaller one
	k = Math.min(k, n - k);

	long res = 1;

	// n choose k = the product of (n - k + i) / i for i = 1..k
	for (int i = 1; i <= k; i++) {
		res = res * (n - k + i) / i;
	}

	return res;
}

Now the solution is fast enough to get an Accepted verdict at the online judge.

Conclusion

Today’s problem was not complicated, but required clever optimizations to avoid a Time limit exceeded verdict.

You can take a look at the complete source code here.
So how would/did you solve this problem? Leave a comment and let us know.

3 Comments For This Post I'd Love to Hear Yours!

  1. atul says:

    to calculate c(n,k) . we can use DP to solve it in efficient manner

    Below code actually forms pascal triangle and return the result accordingly.

    int computeBinomial(int n, int k)
    {
    int* P = (int*)calloc(k+1, sizeof(int));
    int j,i;

    P[0] = 1;

    for(i = 1; i 0; j–)
    {
    P[j] = P[j] + P[j-1];
    }
    }

    return P[K];
    }

  2. Bjarki Ágúst says:

    Your code got a little messed up, but here is what I imagine it was supposed to look like (in C++):

    int nck2(int n, int k)
    {
    	k = min(k, n - k);
    	int* P = new int[k + 1];
    	for (int i = 0; i <= k; i++) P[i] = 1;
    
    	for (int i = 2; i <= n; i++)
    	{
    		for (int j = min(k, i - 1); j >= 1; j--)
    		{
    			P[j] += P[j - 1];
    		}
    	}
    
    	int res = P[k];
    	delete[] P;
    	return res;
    }

    Let me know if it is not what you had in mind.

    Let’s analyze the code a bit. It runs in time, and needs memory. Because and can get so big ( can go up to and up to ), this code just is not going to work. It will both be too slow, and take too much space. There are two upsides to this code though. First, it only uses addition which may be useful, and second, the intermediate results will never be bigger than the actual result.

    But thanks for the comment and the suggestion, even though the code will get a Time limit exceeded verdict at the online judge.

  3. snnn says:

    UVA 369 is similar as this problem , almost the same one !

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.