## 530 - Binomial Showdown

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 530 woes

I believe it, that's also happened to me. Try resubmitting.
Check input and AC output for thousands of problems on uDebug!

triplemzim
New poster
Posts: 48
Joined: Sat Apr 06, 2013 6:02 pm

### Re: 530 woes

YUP this time it is ACCEPTED!!!!! Thanks...

vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

### Re: 530 woes

Some hints for this problem:

Most important line is - "This number will always fit into an integer, i.e. it will be less than 2^31"

Now you need to know that a row n in a pascal's triangle contains the expansion of nCr. The first term in a pascal triangle is always 1 and the second term is n so you can handle this separately. For example if they give you an input case where n is 2147483647 and r is 0 then you don't need to compute anything because in pascal trainagle's row number 2147483647, the first term is 1 and so answer is 1. Similarly for n = 2147483647 and r = 1, the answer is n or 2147483647. But the most important thing to realize is that the smallest number in a pascal's triangle's row is the third term which nC2 (excluding first and second term). Now your answer will always fit into 32 bits, you just need to find which row onwards the third term will always be greater than 2147483647? I wrote a separate program and found that from row 65538 onwards the third term will always be greater than 2147483647 and so this is my conclusion.

If judge's input contains n > 65538 then r will either be 0,1,n or n-1 otherwise the answer won't fit in 32 bits. These 4 cases can be handled separately. But if judge's input is less than 65538 then you can assume that r will be such that - answer always fits in 32 bits. So now this problem can be solved by prime factorization. Just compute all prime factors up until 65538. Break n, r and n-r into prime powers and then subtract them. In the last step just multiply those. See detailed explanation here in technique 5.

http://comeoncodeon.wordpress.com/category/algorithm/