530  Binomial Showdown
Moderator: Board moderators

 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!

 New poster
 Posts: 48
 Joined: Sat Apr 06, 2013 6:02 pm
Re: 530 woes
YUP this time it is ACCEPTED!!!!! Thanks...
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 n1 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 nr 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/
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 n1 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 nr 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/