### dsj vjskd

EDIT: Original poster has disappeared.
Last edited on
If you are "deleting" the pair by literally removing them from the array (or vector) then that can be very expensive. Don't do that. Think of some other way.

It should also be possible to speed up the finding of the next minimum pair, perhaps with a priority queue.
> I tried to find min sum pair and delete the pair and insert their sum.
consider the case [4, 3, 3, 4]
you do
[4, 3, 3, 4] -> [4, 6, 4], penalty: 6
[4, 6, 4] -> [10, 4], penalty: 16
[10, 4] -> [14], penalty: 30
but the optimum is
[4, 3, 3, 4] -> [7, 3, 4], penalty: 7
[7, 3, 4] -> [7, 7], penalty: 14
[7, 7] -> [14], penalty: 28
@Sean34: yes, good catch, the example was wrong
consider instead the case [1000, 4, 3, 3, 4]
now the greedy approach will give you 1030 as penalty, but it may be done in 1028
@ne555,

I think greed is good here.

Just saying it can be done in 1028 doesn't prove it. Show your steps. (I can't figure it out.)

And the greedy answer is 1044, not 1030.

 ```1000 4 3 3 4 1000 4 6 4 : 6 1000 10 4 : 10 1000 14 : 14 1014 : 1014 ==== 1044```

Last edited on
I added the last value incorrectly
it's the same example that I showed before, just put the 1000 so the [4, 4] join would not be possible

[1000, 4, 3, 3, 4] -> [1000, 7, 3, 4], penalty: 7
[1000, 7, 3, 4] -> [1000, 7, 7], penalty: 7 + 7 = 14
[1000, 7, 7] -> [1000, 14], penalty: 7 + 7 + 14 = 28
[1000, 14] -> [1014], penalty 7 + 7 + 14 + 1014 = 1042

see how it's 2 less than the greedy approach.
Good example. You are absolutely correct.

 ```1000 4 3 3 4 1000 7 3 4 : 7 1000 7 7 : 7 1000 14 : 14 1014 : 1014 ==== 1042```

example is correct but how will greedy work when there are duplicates in array it only works when every element is present at most once
siyaram wrote:
example is correct but how will greedy work when there are duplicates in array it only works when every element is present at most once

You're babbling. The point is that greedy doesn't work.
Last edited on
the second subtask passes by greedy man beacause the elements are unique.
but it doesnt work for others. so if it doesnt work give a hint on what to think or what will work
is it dynamic ..?
my life? to be honest, not very
GOT IT BRO .XD
words are cheap