### UVA Online Judge Binomial Showdown Problem

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.

 ``1234567891011121314151617181920212223242526272829303132333435363738394041`` ``````#include #include #include 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
`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
Or you may read the integer value with an integer variable.

Still, you need to analyse the input limits
Suppose as input 231 0
the answer is obviously `1', but your first loop will go all the way from 231 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<= 216, prove it)
Last edited on
I changed `long double` to `unsigned long long`, but I'm not sure how to deal with the Time limit exceeded problem.
Did you read what i said about the break on line 21?
Yeah. I changed the double to long long. It seems to break during the program itself now.
Do you still have the infinite loop?

Could be interesting to see your new code.

Cheers
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=231 it takes too long

Use them as base cases.
Topic archived. No new replies allowed.