How to prove that this greedy algorithm is correct?
http://pastebin.com/TLrkdX7F

Thank you!

I think that helpfull to understand algo as forming  n-1 pairs which cover all elements.
Cost of pair is it's slowest element + cost all elements covered multyptly.
1 10 5 2: (10,5) + 2*(1,2). Cost= 10+2*2+ 1+2=17.
Let we have 12 3 5 2 2  6;
1) sort : 2 2 3  5 6 12:
2) n=6 => 5 pairs: (12,6), (5,3) +3*(2,2) Cost=12+5+3*2+ 2*(2+2)=31.
for  1 25 30 30 1000 1000 better is (1000,1000)+(1,30) +(1,30) +2*(1,25)

Edited by author 12.10.2011 11:05

I continue.
Let G be a graph on n vertices formed after adding n-1 edges(pairs) without multiple edges.
We are searching for min cost graph G_opt.
Theorem 1. In G_opt there are not more than one vertice i in[1..n] with  deg>1
and this one is i=1 (with a[1]).
Proof. Let j be another such vertice. We have  a[1]<=a[j] and can replace each edge
except one of form {b,j} by the edge {b,1]} and cost of resulting graph will be not more  an it has covering property.
Corollary. G_opt is star + matching or star or matching. If multiple edges presence they all are copies of the cheapest edge from previous structure.


Edited by author 13.10.2011 12:29

Finishing!
Let we have 1 10 20 25 30
We are begin with star: (1,10),(1,20),(1,25),(1,30);
but 2*(1,10)+(30,30) < (1,10)+(1,30)+(1,30) because 2*10 < 30+1  (i.e. 2*a[1]<a[k]+a[0])
We form star+matching: 2*(1,10),(1,20) +(25,30)-optimal;
Let now we have 1 5 12 12 14 14 16 19
In this situation 2*5<12+1 and star converts to matching at hole:
4*(1,5)+(12,12),(14,14),(16,19).
For 1 10 10 10 10 10 15  18 19  we have  2*10>18+1
and star (1,10),(1,10),(1,10),(1,10),(1,15),(1,18),(1,19) is optimal

AC!! Not DP Not Greedy and any search . Just strict calculation of solution.
Many submissiond used because greedy more simple to program
than structural logics.


Edited by author 13.10.2011 12:23

Edited by author 13.10.2011 12:31

U can read about this problem on Topcoder. this problem is from TC!

i still don't understand your algorithM! can you explain one more tme more shortly and understandable)))pls!

sort array, if n > 3 then there are two ways to reduce array to n-2 size:
(1,2)->, 1<-, (n-1,n)->, 2<-
(1,n)->, 1<-, (1,n-1)->, 1<-
calculate, what way is cheapest.
After that remains elements 1 2...n-2, repeat procedure

By reducing to Graph problem is idea