Discussion @ 1826. Minefield @ Timus Online Judge

leviyYakor WA 4 // Problem 1826. Minefield 20 May 2018 23:30

DarkSun1997 No subject // Problem 1826. Minefield 28 Oct 2017 19:28

dalex Why the answer is 17? [11] // Problem 1826. Minefield 19 Mar 2011 13:33

Leonid Hint for greedy // Problem 1826. Minefield 1 Dec 2013 12:22

Aguero Example [1] // Problem 1826. Minefield 19 Dec 2012 01:25

AYUBXON UBAYDULLAYEV TUIT for WA #4 // Problem 1826. Minefield 27 Nov 2012 18:04

zoid some hints [1] // Problem 1826. Minefield 12 Aug 2011 00:13

Vitaliy Herasymiv (School of Rozdil) How to prove? [7] // Problem 1826. Minefield 17 Aug 2011 06:12

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

Thank you!

svr Re: How to prove? [6] // Problem 1826. Minefield 12 Oct 2011 09:50

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

svr Re: How to prove? [5] // Problem 1826. Minefield 12 Oct 2011 17:55

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

svr Re: How to prove? [4] // Problem 1826. Minefield 13 Oct 2011 10:17

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

Roman Furko Re: How to prove? [3] // Problem 1826. Minefield 1 Feb 2012 01:55

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

Dimonka Re: How to prove? [2] // Problem 1826. Minefield 16 Mar 2012 18:06

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

Olympic Bear Re: How to prove? // Problem 1826. Minefield 23 Oct 2012 21:08

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

svr Re: How to prove? // Problem 1826. Minefield 24 Oct 2012 12:34

By reducing to Graph problem is idea

Nikol@ What is the test#2? [5] // Problem 1826. Minefield 19 Mar 2011 17:40

[SESC USU] Kungurtsev give me some hints please // Problem 1826. Minefield 4 Jul 2011 10:02

sunnyjanete what is test #5? [1] // Problem 1826. Minefield 10 Apr 2011 16:25

Hrayr Wa#5 ,please give me some hints // Problem 1826. Minefield 29 May 2011 18:24

Newbies What is the test #4? [5] // Problem 1826. Minefield 19 Mar 2011 16:40

AshimaBhatia what should b the output? [5] // Problem 1826. Minefield 19 Mar 2011 14:57

Denis Astanin (KPI) No subject [1] // Problem 1826. Minefield 19 Mar 2011 17:22

Aykut why the answer is 17? [2] // Problem 1826. Minefield 19 Mar 2011 14:43

AshimaBhatia what is test? // Problem 1826. Minefield 19 Mar 2011 15:36

Discussion of Problem 1826. Minefield