We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
So, funny story: I spent many hours over the last two days poring over identities involving binomial coefficients, in hopes of massaging a sum that took O(K^2) into a sum that takes O(K). I assumed that there had to be some kind of combinatorial trick involving Pascal's triangle, because otherwise how could this challenge be possible? Anyway, I finally found one, and everything passes.
Lo and behold, the editorial mentions the same formula that I ended up finding --- as an alternative solution (submitted by bayleef). The intended method of solution from the editorial did not occur to me even once, and I'm sure I wouldn't ever have considered it even if I spent another two weeks on this problem. :-) Perhaps if I were more familiar with particular large primes, I might have taken the "unusual" modulus as a hint, but it was totally lost on me. :-)
Anyway, kevinsogo mentions in the editorial that he couldn't see a proof that bayleef's formula gives the same answer as the naive (and slow) formula involving Stirling numbers; the comments in my submission outline the combinatorial argument that shows why the two formulas are equivalent.
Please feel free to drop me a line if I can offer any assistance with solving this challenge in an apparently completely unintended way. :-)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
An unexpected error occurred. Please try reloading the page. If problem persists, please contact support@hackerrank.com
Costly Graphs
You are viewing a single comment's thread. Return to all comments →
So, funny story: I spent many hours over the last two days poring over identities involving binomial coefficients, in hopes of massaging a sum that took O(K^2) into a sum that takes O(K). I assumed that there had to be some kind of combinatorial trick involving Pascal's triangle, because otherwise how could this challenge be possible? Anyway, I finally found one, and everything passes.
Lo and behold, the editorial mentions the same formula that I ended up finding --- as an alternative solution (submitted by bayleef). The intended method of solution from the editorial did not occur to me even once, and I'm sure I wouldn't ever have considered it even if I spent another two weeks on this problem. :-) Perhaps if I were more familiar with particular large primes, I might have taken the "unusual" modulus as a hint, but it was totally lost on me. :-)
Anyway, kevinsogo mentions in the editorial that he couldn't see a proof that bayleef's formula gives the same answer as the naive (and slow) formula involving Stirling numbers; the comments in my submission outline the combinatorial argument that shows why the two formulas are equivalent.
Please feel free to drop me a line if I can offer any assistance with solving this challenge in an apparently completely unintended way. :-)