Page 10 of 10

Re: 530 woes

Posted: Fri Aug 02, 2013 11:27 pm
by brianfry713
I believe it, that's also happened to me. Try resubmitting.

Re: 530 woes

Posted: Fri Aug 02, 2013 11:37 pm
by triplemzim
YUP this time it is ACCEPTED!!!!! Thanks... :)

Re: 530 woes

Posted: Wed Mar 12, 2014 8:27 pm
by vsha041
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/