Below is the Link of the question
and the solution
https://www.codechef.com/viewsolution/41770484
In which the Power of two raise to (subjects-1)
How it is giving ways of being successful according to given condition ie the student will successful if he will pass in number of subjects more than the number of subjects he failed
Let the subjects be N.
A student fails if he fails in N, N-1,N-2,...,N/2 subjects.
Total ways to pass
= NcN + Nc(N-1)+....+Nc(N/2)…(Eq i)
Now Nc0+Nc1+...+ Nc(N/2-1) equals Eq i
=1/2(NC0+NC1+NC2+...+NCN)
=1/2 * 2^N
=2^(N-1)
1 Like
Note that the logic only works for odd N. This follows from a simple consequence of binomial theorem.
For even N, we need to subtract 1/2 of {N} \choose {N/2} . (which actually neeeds at least O(N) to compute and can’t be solved for the given constraints.
Can You elaborate more plz
@ashish_kaur
what NcN+Nc(N−1)+…+Nc(N/2) this equation gives
what Nc0+Nc1+…+Nc(N/2−1) this equation gives
and why you are summing up those equation ?
You got it wrong. I am not summing.
I guess you know this, NcR=Nc(N-R).
So Nc0=NcN, Nc1=Nc(N-1).
Also,
2^N= Nc0+Nc1+Nc2+....+NcN
Therefore the summation from Nc0 to Nc(N/2) is equal to summation of Nc(N/2+1) to NcN. So, I am doing 1/2*(Total sum from 0 to N).
Now I Got the concept clearly .
Thanks a lot bro . @ashish_kaur
Means a lot .
1 Like
Thx for the note @cubercoder .