Talk:UVa 10213

From Algorithmist
Jump to navigation Jump to search

Has anyone actually programmed a solution to this problem? I'm having trouble getting it to work for the particularly large cases. --Kentaro 14:14, 24 Mar 2005 (EST)

what's "k"? I haven't attempted this problem, but I remember discussions where BigInt would suffice, especially if you use the closed form equivalent of the combinatorical formulas..

Larry 14:19, 24 Mar 2005 (EST)

Oops! The k is in error. That should be a 4. --Kentaro 14:20, 24 Mar 2005 (EST)

The formula can also be expressed in terms of a polynomial in n. I'm wondering if maybe calculating that with BigNums is the answer?

Ah, ya, then you can definitely simplify your expression into a polynomial, and calculate it that way.. Larry 14:22, 24 Mar 2005 (EST)

Ya, BigInt appears to be needed, since the answer is in the ~ n^4 range, where n can be pretty big.. Larry 14:24, 24 Mar 2005 (EST)

Actually, it might be beneficial to just calculate it as it is then. Because then there's no need for exponentiation. All that would be needed are the four basic operations. --Kentaro 21:38, 24 Mar 2005 (EST)

I finally got AC for this problem. BigNum in base 10 is not good enough. Changing to a higher radix like on the BigNum page, I shaved a whole 9 CPU seconds off my solution using base 10. Incredible. I'll have to keep working on my BigNum code. --Kentaro 23:24, 26 Mar 2005 (EST)