Discussion @ 1716. Alternative Solution @ Timus Online Judge

Unexpected helphull problem

Posted by svr 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.

Re: Unexpected helphull problem

Posted by dd (mp dpt USTU) 27 Oct 2009 12:57

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

Re: Unexpected helphull problem

Posted by Pavel Khaustov [Tomsk PU] 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?

Re: Unexpected helphull problem

Posted by Vedernikoff Sergey (HSE: АОП) 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

Re: Unexpected helphull problem

Posted by Pavel Khaustov [Tomsk PU] 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.

Re: Unexpected helphull problem

Posted by Vedernikoff Sergey (HSE: АОП) 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