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 \le \frac n 2~ and count twice if necessary
Approach 1:
- Loop over $k$ ~k~ from $0$ ~0~ to $\binom{2k}{k} > x$ ~\binom{2k}{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 \ge 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.