Discussion @ 1005. Stone Pile @ Timus Online Judge

Who solve this problem with DP,

Posted by ural_ghost 31 Oct 2007 20:40

I have solved it with Dp in 0.015.
Is there anyone fast(DP)?

Re: Who solve this problem with DP,

Posted by AlainDelon 8 Dec 2007 15:00

I'd be more interested in your memory strategy. I don't think DP alg will differ much for the same problem

Re: Who solve this problem with DP,

Posted by Skhan 9 Dec 2007 10:42

Maybe the test data are so simple, and DP is able to accept.
But I don't think DP method is right.

Re: Who solve this problem with DP,

Posted by KIRILL(ArcSTUpid coder:) 10 Dec 2007 02:24

dp(bug task) and bruteforce (2^n) are both accepted

Re: Who solve this problem with DP,

Posted by Madhav 12 Jun 2008 01:16

for me it got accepted with brute force

Re: Who solve this problem with DP,

Posted by gaston770 9 Feb 2009 03:29

Time : 0.015 (I think its the minimal time) C++ using maps and vectors

Used DP

Want d code? gaston770@gmail.com

Less than 15 lines of the algorithm

Re: Who solve this problem with DP,

Posted by yzthz 17 Mar 2009 18:54

My solution cost monstrously 0.187s using DP...

Re: Who solve this problem with DP,

Posted by ans_ 28 Sep 2013 19:10

Легко решается с динамическим програмированием. Делишь сумму камней на 2 части, потом запускаешь рюкзак до суммы камней/2, ответом будет являться abs(sum-2*maxx), где sum - сумма камней, а maxx - макс. вес, который мы можем поместить в наш "рюкзак"

Discussion of Problem 1005. Stone Pile