Hello, I'm trying to solve this problem a couple of days. But always get wrong answer 4. I don't know what is the problem may be and this makes me feel badly. Could somebody help me or show the 4th test for me, please? I can send my code if it's needed. Edited by author 28.10.2017 19:36 10+1 + 5+1 + 2 = 19. And there is no other way 10+1+5+1=17 So what happens with the person with time 2? How is that possible? M stands for mine detector. 1 2 5 10 M - empty 2 5 - 1 10 M (+10) 1 2 5 M - 10 (+1) 2 - 1 5 10 M (+5) 1 2 M - 5 10 (+1) empty - 1 2 5 10 (+2) 10 + 1 + 5 + 1 + 2 = 19 Which is 19, not 17. That's why we are asking how can it be 17? 1 2 5 10 | --- = 0 5 10 | 1 2 = 2 1 5 10 | 2 = 3 1 | 5 10 2 = 13 1 2 | 5 10 = 15 --- | 1 2 5 10 = 17 There is no single optimal move. There is exactly two moves, one of which is optimal. On every step of greedy, you must choose best of them. Can you explain me the first example.. why 17?? They can cross for 17 in such a way: 1,2--> <--1 5,10--> <--2 1,2--> 4 1 4 5 6 ans: 17 --> 1,4 4 <-- 1 1 --> 1,5 5 <-- 1 1 --> 1,6 6 17 sort and DP is ok can you explain DP parameters? 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 maybe something like : 5 1 2 3 4 5 )))) i think that answer will be 16 ) i got 16, but it's again wa#2 ( Right answer is 13 I think you are wrong. My AC program prints 16 too Edited by author 06.07.2011 11:00 have no idea...help..please HELP PLEASE! Try test: 5 1 30 30 30 30 i got 123. but wa #4.. OK, what about: 6 1 20 30 30 2011 2011 ? 2143 My answer is 2134: 1+20 -> 1 -> 2010+2011 -> 20 -> 1+30 -> 1 -> 1+30 -> 1 -> 1+20 what should be the output for following input? n=5 1 2 5 10 11 24 i'm too geting the same output in my machine but the server is saying wrong answer by test4. why is this so? is greedy ok? Edited by author 19.03.2011 23:56 Greedy solution works just fine. 1 2 (fisrt pair) 1 (time required to come back) 1 5 (second pair) 1 (time required to come back) 1 10 (third pair) why time required to come back isn't summed with all result time? |
|