please wait
dsj vjskd
Jul 10, 2019 at 10:01pm| I solved only subtask #2 |
What was your algorithm?
EDIT: Original poster has disappeared.
Last edited on Jul 13, 2019 at 12:38am
Jul 10, 2019 at 11:23pm
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.
Jul 11, 2019 at 5:22am
> 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
Jul 11, 2019 at 2:41pm
@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
Jul 11, 2019 at 2:49pm
@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 Jul 11, 2019 at 2:50pm
Jul 11, 2019 at 3:29pm
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.
Jul 11, 2019 at 3:36pm
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 |
Jul 12, 2019 at 3:20pm
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
Jul 12, 2019 at 3:34pm| 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 Jul 12, 2019 at 3:34pm
Jul 12, 2019 at 4:39pm
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
Jul 12, 2019 at 6:14pm| words are cheap ask a politician |
Most will babble endlessly without being asked.
Jul 12, 2019 at 8:05pm
greedy approach won't work here... but how to check every possible penalty sum without doing it in O(n!).
Jul 12, 2019 at 8:55pm
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.