@ohmankur, your code is probably TLEing cause you are calculating the vector “f”, for maintaining factorials, each time you are calling your “C” function to given nCr. You can instead, precompute factorials upto 10^5 and store them in “f” for once, instead repeatedly calculating them.
Have a look at my code to understand more clearly and see where I have calculated array “f”.
@easy_ It might be possible that when you calculate nChoosek it might get big enough than what unsigned long long int can store, though not sure, and may when you do this in loops ans+=nCr(i) -> I think here also there are chances that it might be overflowing.
Maybe make some changes there and it might work!
@lohit_97 Can you tell me what will be the better way to store such big numbers, or if there is any other better way of calculating nCk?
Hi! Could anybody please suggest a test case where my solution fails? I calculated n choose k correctly(I think so).
Thanks in advance.
@devilhector your code fails on the cases when there is 0 present in the array
for eg. n=5,k=5,array=[1,2,3,0,0]
check this actual answer will be 8,but your code outputs 4.
For calculating nCr in different situations, you can refer to the following link:
https://github.com/likecs/Competitive-Coding/blob/master/C%2B%2B/Maths/combinations.cpp
@easy_ so basically we are adding nC0,nC2,nC4…if k is even
else we are adding nC1,nC3,nC5 (k odd)
is that right??
can anyone tell me why code fails for higher numbers…it is giving correct answer but dont no why i am getting only 40 marks.
pleas tell me.
https://www.codechef.com/viewsolution/10347950
sorry i pasted the solution of 4th question.
sorry i pasted the solution of 4th question.
I did this before but i was facing tle in one of the test case
There exist overflow problem for higher values.Change your data type.Use the concept of mod 10^7 for computing higher values.
@prak_blah Yes. This is the case when there is no zero in the array. If there are say p zeroes then make n -= p
and add up nC0, nC1, nC2, …nCk.(if(k > n) make k = n).
And do anyone know how to comment on answer instead of writing another one?
https://www.codechef.com/viewsolution/10412867
why did this solution get tle in the final subtask?
I was calculating the sum of alternating binomial coefficients and this ncr function seems to be good.
plz help
CodeChef: Practical coding for everyone I am unable to find the mistake in my solution. I hope I have made a subtle one. Any help is appreciated.
hat is wrong with my code if only subtask one is considered?? the third task in subtask 1 showed wrong answer?? rest other were correct…