Discussion @ 1716. Alternative Solution @ Timus Online Judge

svr Unexpected helphull problem [5] // Problem 1716. Alternative Solution 27 Oct 2009 10:45

During 3 days I couldn’t find appropriate way
to work with big binomials having lost of order
or overflow. Simple and clever routine was found and
gave satisfaction.

dd (mp dpt USTU) Re: Unexpected helphull problem // Problem 1716. Alternative Solution 27 Oct 2009 12:57

I congratulate. thanks for instructions (http://acm.timus.ru/forum/thread.aspx?id=19224&upd=633922277282410000).

Pavel Khaustov [Tomsk PU] Re: Unexpected helphull problem [3] // Problem 1716. Alternative Solution 29 Aug 2010 22:15

Could you give any hint: what kind of "simple routine" have you found? I also have got overflow / lost of order? Is it possible to avoid such problem in O(N^2) solution?

Vedernikoff Sergey (HSE: АОП) Re: Unexpected helphull problem [2] // Problem 1716. Alternative Solution 30 Aug 2010 00:43

I don't know what your algo is, but my dynamic O(N^2) solution hasn't problems with overflows - all numbers is of order N

Pavel Khaustov [Tomsk PU] Re: Unexpected helphull problem [1] // Problem 1716. Alternative Solution 30 Aug 2010 02:27

Thanks! I've got AC with O(N^2) DP. Every value was not exceeding N. But it's still interesting - how did some people get AC with 0.015sec and minimum of memory.

Vedernikoff Sergey (HSE: АОП) Re: Unexpected helphull problem // Problem 1716. Alternative Solution 30 Aug 2010 12:34

I suppose there exists some formula, but it is not trivial (like in this problem: http://acm.timus.ru/problem.aspx?space=1&num=1762)

Discussion of Problem 1716. Alternative Solution