In this problem only there are only 20 stones(elements). So we can generate all possible variants of rearrange the stones into two piles. There will be 1,048,576 variants for 20 stones. Realization of such algorithm will work about 1 second(less than Time limit - 2 seconds). But I meet alike problem where can be about 60 elements. And in such case count of varians will decrease to 1,152,921,504,606,846,976. As you understand time limit in such way will be exeeded. I think than we have to use dinamic programming. Can anybody tell how to solve this problem with dinamic programming?

for DP method, the optimal result is just a pile with the closet weight to half of all the stones.

suppose use a function named "getmid(beg,mid)" to find the most closet pile's weight when given two parameters ("beg", and "mid"). "beg" means the start index of stone in the left stone collection, "mid" means the perfect half value(you try to reach). the formula is as below:

|- If mid <= 0 Then getmid(beg, mid) = 0;
|
|- If mid < Weight[beg] Then getmid(beg, mid) = getmid(beg+1, mid)
|
|- If mid >= Weight[beg] Then getmid(beg, mid) = MaxOptimal[ Weight[beg] + getmid(beg+1, mid-Weight[beg]), 0+ getmid(beg+1, mid ]

I have generated all possible variants, and I have not got TL. AC in 0,296 seconds. But I think DP is better)

acmp.ru AC
acm.timus.ru WA2
Can you help me?
I have generated all possible variants
may be something wrong?
(Binar Sistem of Counting)

Edited by author 07.10.2010 19:50

Edited by author 07.10.2010 19:51

This problem so decides; sorts stones, then looking for the difference modulo!