What is Logic Behind?

Below is the Link of the question

https://www.codechef.com/BSP22021/problems/BS2DP3

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

Which part?

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 .