The bruteforce is only correct way to solve this problem
you are to write function that will generate all permutations of(0,1) length n(where n-number of stones in pile)
than you have calculate weight of all stones that you took in concrete permutation and find minimal difference between 2 piles. that's all
sorry for poor eng

Brute force is the easiest to implement here but not the only way. You can also develop a DP scheme to solve this problem, especially if you were given not 20 but, say, 100 stones...

Could you explain, what does the abbreviation «DP» mean here, please?

As usual, DP == Dynamic Programming

Thank you so much for the hint. I did try with brute force. Not sure why I am getting #WA 1. Could you please kindly help me with some test cases?

Hi All,
    Thank you for all your support and help. Just got AC with brute force method.

regards
Anupam

I found i really fast and simple solution for this one.
Main idea is:
1.Get 2 arrays(first one to store weights and sec to store 0 or 1 as includes in sum or not)
2.Find what sum would be best case
3.Go trough array and add to the sum until you get more than best sum
4.Now you need to make sum optimal,you do that this way:
    1.If current sum is greater than best you remove one element that is closest to current sum - best sum but only if by doing that you get better solution than the one you've got before
    2.If current sum is lest that optimal than you need to add one element that was not in sum and also you do that only if by doing that you get better solution than the one you've got before
5.If there were no changes in last pass you print result as abs(main sum - 2*current sum)

Hope you like it :)

i've got AC (0,015s and 212kb memory) using this algorithm

Edited by author 27.01.2012 20:35

I dont think brute force would be the best approach.

Because when the input is 20, maximum number of elements to be considered is 10.

So that would leave us with something like this

(20!)/(20-10)! = 20*19*18*17*16*15*14*13*12*11

I am not quite sure whether we would be able to check the last permutation (worst case) within the two seconds time limit.

Please correct me if I am wrong..

Every stone can be in group A or in group B. Just brute every variant of every stone. O(2^N * N).

Oops... I was wrong. On a second thought, we should not find the permutations but the combinations. But still that crosses 1.5 millions... :(

Accepted    0.015    120 KB

start:
for each stone
  put stone in the other pile
  if the difference is greater than before
    then put it back
    else let it stay in this pile
end for
if the difference is smaller than before the for loop
  then goto start (do another pass)

make sure that you don't get an infinite loop. it happened and I got TLE at test 2

Edited by author 15.06.2012 18:22

Edited by author 15.06.2012 18:22

Hm...I developed another solution, but don't know why it is wrong. "Put" means add to the sum, like: left += element;
1. Sort stones in their weight from bigger to lower.
2. If there is only 1 stone - it is an answer.
3. If there are 2 stones - absolute of their difference is an answer.
4. Else: put first stone to left (or right) and second to ther right (or left).
5. Put next stone to the side which is lowerю
6. Repeat 5 until number of stones will be reached.
7. Print the absolute value of difference of the left and right.

Where I'm wrong?

Edited by author 30.06.2012 23:35

Edited by author 30.06.2012 23:41

5
10 9 8 7 2

For Novosad.
I go in that way to, but what's wrong with this solution?

The flaw Hypбол is that this algorithm (which I did first, too, by the way) *always* places the largest and 2nd largest stones in different piles.    Inputs like 5 4 6 7 8 9 require the 9 and 8 to be together in one pile.    I'm not aware of any algorithm smarter than "try all combinations and choose the smallest difference).   Any heuristic solution that doesn't try all combinations will fail to input specially crafted to fit the "blind spot" of the heuristic, like in this case.

This problem does NOT belong in the beginner's section IMO!

> This problem does NOT belong in the beginner's section IMO!

OK, I see the simple O(2^n) algorithm, but still, I wouldn't call this a beginner's problem, since this technique of partitioning via binary strings is definitely not obvious to beginners.    It's absolutely a very important technique, but someone who just picked up coding would take some while to think this up.

Edited by author 15.09.2012 18:46

Edited by author 15.09.2012 18:46

The easiest one is brute-force

There are 2 cycles, one of them is generating (0, 1) sequence, (1 if we include the stone in 1-st set of stones and 0 if not), there are 2^n permutations. The second cycle checks, if we should include the stone in the 1-st set and adds its weight to the current set weight. We should find the best difference between 2 sets' weights, the weight of one set is current_weight, of the second, obviously, sum - current_weight (sum is weight of all the stones), and the difference is abs(current_weight - (sum - current_weight)) = abs(sum - 2 * current_weight).

But this is bad algorithm since it's complicity is O(n * 2^n), which is over 20 million in this problem in worst case. The DP algo complicity is O(n * sum), which is better in most of problems except this one, because if there are 20 stones and weight of each is 100000, then n * sum = 40 million, which is 2 times worse.

Edited by author 29.03.2013 14:57