dsj vjskd
| I solved only subtask #2 |
What was your algorithm?
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.
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
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
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.
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.
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
but it doesnt work for others. so if it doesnt work give a hint on what to think or what will work
| words are cheap ask a politician |
Most will babble endlessly without being asked.
greedy approach won't work here... but how to check every possible penalty sum without doing it in O(n!).
don't check every combination, check only the ones that occur between adjacent elements
there are only O(n^2) of those.
there are only O(n^2) of those.
Topic archived. No new replies allowed.