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

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

Re: 530 woes

Post by brianfry713 »

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

Post by triplemzim »

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

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

Re: 530 woes

Post 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.


Post Reply

Return to “Volume 5 (500-599)”