Editorial for ICPC NWERC 2011 A - Binomial Coefficients - Olympiads Online Judge

Editorial for ICPC NWERC 2011 A - Binomial Coefficients

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Find $n, k$ $n, k$ such that $\binom n k = \frac{n!}{k!(n-k)!} = x$ $(\binom{n}{k}) = \frac{n!}{k! (n - k)!} = x$
Only look for solutions with $k \le \frac n 2$ $k \leq \frac{n}{2}$ and count twice if necessary
Approach 1:
- Loop over $k$ $k$ from $0$ $0$ to $\binom{2k}{k} > x$ $(\binom{2 k}{k}) > x$
- Binary search for $n$ $n$
Approach 2:
- For $k = 1$ $k = 1$ , solution is $\binom x 1$ $(\binom{x}{1})$
- For $k = 2$ $k = 2$ , solve $x = \binom n 2 = \frac{n(n-1)}{2}$ $x = (\binom{n}{2}) = \frac{n (n - 1)}{2}$
- For $k \ge 3$ $k \geq 3$ , loop over $n$ $n$ until $\binom n k > x$ $(\binom{n}{k}) > x$
Be really careful with overflows!

Comments

There are no comments at the moment.