UVA Online Judge Binomial Showdown Problem

[miguel11795]

I don't know how to make this more efficient. My answers seem to be correct, but I get a "Time Limit Exceeded" error all the time. Can anyone help me with this? Thanks.

#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

int main()
{
	long double n, r, amount, small, diff, comb;
	for(;;)
	{
		cin >> amount;
		cin >> small;
		if(amount == 0 && small == 0)
			break;
		diff = amount - small;	
		n = 1;
		for(int i = amount; i != diff; i--)
		{
			if(amount == 0)
				break;
			n = n*i;
		}

		for(int i = 0; i <= small; i++)
		{
			if(i == 0)
				r = 1;
			else
				r = r*i;
		}

		comb = n/r;
		cout << comb << endl;
		
		
	}
	
	
	return 0;
}

http://uva.onlinejudge.org/external/5/530.html

[TheIdeasMan]

if(amount == 0)

This will almost certainly be false, because doubles are stored as binary fractions and cannot represent every real number. This means there is no exit from the infinite for loop - hence the time limit problem.

To fix this, you need an arbitrary precision value such as :

double MyPrecision = 0.001;

if amount is less than MyPrecision then that is the end condition. Your break only breaks from the for loop that it is in, so you need a better way. Try a while loop instead.

HTH

[ne555]

Or you may read the integer value with an integer variable.

Still, you need to analyse the input limits
Suppose as input 2³¹ 0
the answer is obviously `1', but your first loop will go all the way from 2³¹ to 0 (waste of time)


Then you will realize that double is not precise. Check out Tartaglia's triangle.
The order will be O(n), where n=min(small, diff) (however n<= 2¹⁶, prove it)

[miguel11795]

I changed long double to unsigned long long, but I'm not sure how to deal with the Time limit exceeded problem.

[TheIdeasMan]

Did you read what i said about the break on line 21?

[miguel11795]

Yeah. I changed the double to long long. It seems to break during the program itself now.

[TheIdeasMan]

Do you still have the infinite loop?

Could be interesting to see your new code.

Cheers

[ne555]

As I said
n 0
n 1
n n
n n-1
are all valid inputs.

The result is trivial (1, n, 1, n) but you iterate to compute it.
With n=2³¹ it takes too long

Use them as base cases.