Обсуждение @ 1826. Минное поле @ Timus Online Judge

leviyYakor WA 4 // Задача 1826. Минное поле 20 май 2018 23:30

DarkSun1997 No subject // Задача 1826. Минное поле 28 окт 2017 19:28

dalex Why the answer is 17? [11] // Задача 1826. Минное поле 19 мар 2011 13:33

Leonid Hint for greedy // Задача 1826. Минное поле 1 дек 2013 12:22

Aguero Example [1] // Задача 1826. Минное поле 19 дек 2012 01:25

AYUBXON UBAYDULLAYEV TUIT for WA #4 // Задача 1826. Минное поле 27 ноя 2012 18:04

zoid some hints [1] // Задача 1826. Минное поле 12 авг 2011 00:13

Vitaliy Herasymiv (School of Rozdil) How to prove? [7] // Задача 1826. Минное поле 17 авг 2011 06:12

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

Thank you!

svr Re: How to prove? [6] // Задача 1826. Минное поле 12 окт 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] // Задача 1826. Минное поле 12 окт 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] // Задача 1826. Минное поле 13 окт 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] // Задача 1826. Минное поле 1 фев 2012 01:55

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

Dimonka Re: How to prove? [2] // Задача 1826. Минное поле 16 мар 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? // Задача 1826. Минное поле 23 окт 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? // Задача 1826. Минное поле 24 окт 2012 12:34

By reducing to Graph problem is idea

Nikol@ What is the test#2? [5] // Задача 1826. Минное поле 19 мар 2011 17:40

[SESC USU] Kungurtsev give me some hints please // Задача 1826. Минное поле 4 июл 2011 10:02

sunnyjanete what is test #5? [1] // Задача 1826. Минное поле 10 апр 2011 16:25

Hrayr Wa#5 ,please give me some hints // Задача 1826. Минное поле 29 май 2011 18:24

Newbies What is the test #4? [5] // Задача 1826. Минное поле 19 мар 2011 16:40

AshimaBhatia what should b the output? [5] // Задача 1826. Минное поле 19 мар 2011 14:57

Denis Astanin (KPI) No subject [1] // Задача 1826. Минное поле 19 мар 2011 17:22

Aykut why the answer is 17? [2] // Задача 1826. Минное поле 19 мар 2011 14:43

AshimaBhatia what is test? // Задача 1826. Минное поле 19 мар 2011 15:36

Обсуждение задачи 1826. Минное поле