| ENG RUS | Timus Online Judge |
Обсуждение задачи 1143. Electric PathAdhambek be careful [1] // Задача 1143. Electric Path 16 ноя 2015 16:12 In order to achieve absolute safety providing electricity to the camps, besides an electric supplying system, the host organization set up a path from a reserved electricity generator (which is placed in one of the camps) to every camp once, this means that, thare is only and only one path from Pi camp to Pj camp. yyll Re: be careful // Задача 1143. Electric Path 3 июн 2021 20:26 The answer should be a path (successive line segments) NOT a tree (minimal spanning tree) NOT a Steiner tree (minimal spanning tree with additional points) Petru Trimbitas WA #14 // Задача 1143. Electric Path 23 сен 2011 22:26 Can someone give me some tests? I have a greedy solution. Edric Mao sample // Задача 1143. Electric Path 2 сен 2010 16:41 can you explain the sample for me Thx WAZZAP I'm really mad of solving this problem... Why the minimal spanning tree doesn't work? And what is the right solution? (-) [3] // Задача 1143. Electric Path 19 окт 2002 18:00 Miguel Angel Isn't the MST, you MUST know TREE<>PATH [2] // Задача 1143. Electric Path 20 окт 2002 01:55 > WAZZAP And WHAT is the diffrence?... [1] // Задача 1143. Electric Path 30 дек 2002 02:08 What, what is the difference? i just cannot understand - if this is a Steiner problem (if you can add the additional vertices to a graph to shorter the PATH), there is no solution acceptable (steiner problem has not been solved, hasn't it?) wsk Re: And WHAT is the diffrence?... // Задача 1143. Electric Path 26 авг 2010 07:57 OH I see! Koala O(n^3) works... [1] // Задача 1143. Electric Path 27 ноя 2009 00:04 my O(n^3) dp got accepted in 0.89sec, though i used an O(n^2) algorithm later and ran much faster. [Ural SU] GetTester Re: O(n^3) works... // Задача 1143. Electric Path 28 ноя 2009 14:50 Of course, it works. Moreover, my O(n^3) dp works in 0.48sec. And I'm sure, that it isn't limit. Obvious, that it's impossible to break O(n^3) solutions with current constraint for n. xurshid_n i use O(n^3) algorthm?, but my program always WA 11, What is test 11? // Задача 1143. Electric Path 22 авг 2009 16:05 Team CHANT - The TESTER To Admin : Why my program has WA 1 ? I tried the sample by myself it always gave the same answer as in sample [4] // Задача 1143. Electric Path 1 фев 2009 13:19 Team CHANT - Sakigake Moto Re: To Admin : Why my program has WA 1 ? I tried the sample by myself it always gave the same answer as in sample [3] // Задача 1143. Electric Path 1 фев 2009 14:49 Just unlucky, I guess ;) Sandro (USU) Test#1 is not a sample test in this problem (-) [2] // Задача 1143. Electric Path 1 фев 2009 16:00 Team CHANT - The TESTER Re: Test#1 is not a sample test in this problem (-) [1] // Задача 1143. Electric Path 1 фев 2009 16:35 Well Thanks, but i haven't figured out why minimal spanning tree is wrong, my prog gave correct answers for all the tests in the discuss. How annoying ! Häkkinen Re: Test#1 is not a sample test in this problem (-) // Задача 1143. Electric Path 23 июл 2009 12:23 Electric Path is a PATH, not TREE ! Edited by author 23.07.2009 12:30 LiWang112358 what is test 14? // Задача 1143. Electric Path 20 июл 2009 18:49 tjj DP in O(n^2) [3] // Задача 1143. Electric Path 11 авг 2006 15:21 For it is a convex polygon the best path won't self-cross, so a vertex Pi can only be connected to Pi-1 or Pi+1. Good Luck! Edited by author 11.08.2006 16:27 tjj Re: DP in O(n^2) [1] // Задача 1143. Electric Path 11 авг 2006 16:27 Sorry, what I meant was Pi must be connected to Pi-1 or Pi+1 or both of them. Denis Koshman Re: DP in O(n^2) // Задача 1143. Electric Path 12 авг 2008 16:37 Then why do you call it DP and O(N^2)? It'll be just O(N) - find shortest side and send the loop around ploygon excluding that side. Edited by author 12.08.2008 16:38 SkorKNURE Re: DP in O(n^2) // Задача 1143. Electric Path 11 окт 2008 17:43 I think it's true only when we have already fixed one edge and are trying to create path by building a part of one's before the fixed edge and another part after it. There is only 2 ways to create a path when one edge is fixed (read http://acm.timus.ru/forum/thread.aspx?space=1&num=1143&id=14857&upd=633229528200233510) And also when edge[i][j] is fixed, we can build this 2 pathes unambiguously using greedy thoughts Olly why wa#2? please help [15] // Задача 1143. Electric Path 1 мар 2007 18:05 i'm sorry for posting my code here, it will be deleted as soon as i figure out my problem. it's O(n^2) algo based on recursion with caching. the main idea is following: 1. I make an edge from first vertex to all others. Let the edge be (0,i), then optimal answer will be dist(0,i)+(optimal_answer(0,i-1))+(optimal_answer(i,n)). Here and afterwards vertex n is the same with vertex 0. Or optimal answer will be dist(0,i)+(optimal_answer(i,1))+(optimal_answer(n,i+1)). 2. Optimal_answer(fr,to) is: 2.1 min(Optimal_answer(fr+1,to)+dist(fr,fr+1),Optimal_answer(to,fr+1)+dist(fr,to)) in case fr<to 2.2 min(Optimal_answer(to,fr-1)+dist(fr,to),Optimal_answer(fr-1,to)+dist(fr,fr-1)) in case fr>to Optimal_answer(fr,to) returns length of the path _starting_ with fr and _ending_ with to. it's some kind of directed path :) based on this facts i wrote this program: [CODE WAS HERE] which is WAing on test 2 :( I don't know, maybe i have only a little stupid mistake, or my algo is incorrect at all. But my friend sais it's ok, so ... Thanks in advance Edited by author 01.03.2007 18:11 Edited by author 02.03.2007 16:07 svr Re: why wa#2? please help [14] // Задача 1143. Electric Path 1 мар 2007 19:08 Thank for ideas. This interesting problem may be rather difficult. I will search solution based on your algorithm with it's verification. But you should take in account all forum messages on this problem. Edited by author 01.03.2007 19:10 Delete Re: why wa#2? please help // Задача 1143. Electric Path 1 мар 2007 19:11 I've read all the threads about this problem svr Re: why wa#2? please help [12] // Задача 1143. Electric Path 1 мар 2007 21:19 I don’t agree with this part of your algorithm optimal=dist(0,i)+(optimal_answer(0,i-1))+(optimal_answer(i,n)). for some i I think that correct is next: Let [i,j] (j,i in[1,n-1],j>i) continuous segment of vertices doesn’t containing 0 Let p(i,k,j)=min path-length of [i, j] starting from k in [i.. j-1] and finishing in j Let h(i,j)=min(k=i,i+1,---j-1) p(i,k,j) D1=min(i=2,…n-2)(dist(0,i)+h(i+1,n-1)+h(1,i-1) D2=d(0,1)+h(2,n-1) D3=d(0,n-1)+h(1,n-1) Answer=min(D1,D2,D3) Olly Re: why wa#2? please help [11] // Задача 1143. Electric Path 1 мар 2007 22:27 I can hardly understand your idea, but it seems to be the same. My algo actually is drawing all possible non-intersecting paths, by adding edges one by one to the first one ( which is choosen in cycle for(i=1;i<n;i++) ). The vertex 0 must be connected with one of the others, so this seems correct. Or i am missing something? Can you make a test, on which my program fails? If you wish we can have a conversation via mail: alutsenko[at]bk[dot] ru ADDED: maybe you have overviewed this? t = dst[0][i] + solve(0,i-1) + solve(i,n-1); if(t<an) an = t; t = dst[0][i] + solve2(i,1) + solve2(n,i+1); if(t<an) an = t; so there is 2 ways to create a path when one edge (0,i) is fixed. Edited by author 01.03.2007 22:32 svr Re: why wa#2? please help [10] // Задача 1143. Electric Path 2 мар 2007 00:42 Now I written the Dp program where arrays only used. (You used recurcion and calling function dist(i,j)) D1[i][j]- min length of hamilton patn which cover segment [j,j+i-1] and finishing in j+i-1 D2[i][j]- min length of hamilton patn which cover segment [j,j+i-1] and starting at j if we have edge [0,i] where 2<=i<=N-2 L=min(D1[N-i][i+1]+dist[0][i]+D1[i][1]) But i have WA2 too After getting Ac I will send you my pure-Dp program to email. svr Re: why wa#2? please help [9] // Задача 1143. Electric Path 2 мар 2007 01:09 I can't find bugs in my prog. Only tests using can give result. What is your program gives on next simple test. 6 0 1 1 0 2 0 3 1 2 2 1 2 6.243- my prog svr Re: why wa#2? please help [1] // Задача 1143. Electric Path 2 мар 2007 09:21 Friend! Good news! I made broote force making all permutations on[1..n] and pass Tests 2,3!!!! but Tle4 It means: 1) The problem is searching hamilton path + 2) There are now precision and formatig tricks in T1-T3 + 3) Our main progs have logical mistakes - Now: I will compair broot and main and soon needed test will be found Edited by author 02.03.2007 14:22 svr Re: why wa#2? please help // Задача 1143. Electric Path 2 мар 2007 14:24 Read previous message Olly Re: why wa#2? please help [6] // Задача 1143. Electric Path 2 мар 2007 14:56 my program gives the same answer to your test - 6.243 I don't see any mistakes in my algo :( svr Re: why wa#2? please help // Задача 1143. Electric Path 2 мар 2007 15:38 Using broot-force program I found bugs in my main prog quickly and now it passes T2,3 and has WA4. But your program in all cases gave answers coinsize with broot-force prog. It means that I couldn't find test for you. But it's evident now that test 2 is common test without tricks and with N=5-8. Thus you may write simple broot force program yourself and to try find mistake. Edited by author 02.03.2007 15:39 Olly Re: why wa#2? please help [4] // Задача 1143. Electric Path 2 мар 2007 16:06 Finally accepted !!! this was the point: 7 0 0 1 0 2 1 2 2 -2 2 -2 1 -1 0 answer is 6.828 !!! I've added only two lines to my program and it got AC thanks for your help. For any questions mail to me. svr Re: why wa#2? please help [3] // Задача 1143. Electric Path 2 мар 2007 17:03 I am also Ac But I have(0.001) and I am leader on 1143 due pure Dp Before I found 2 stupid bugs using broot-force prog and convex-hull prog especially last. Thus your algorithm at end became very succesfull Olly Re: why wa#2? please help [2] // Задача 1143. Electric Path 2 мар 2007 17:07 Can you send me your code? I'm interested in DP solution svr Re: why wa#2? please help [1] // Задача 1143. Electric Path 2 мар 2007 17:18 Much more useful transform own code to Dynamic prog. 1) Use arrays instead of recursion; 2) use also dist[i][j] instead of function dist(i,j) wingzeroshy Re: why wa#2? please help // Задача 1143. Electric Path 17 авг 2007 13:07 I use O(n3)Dp prog ,and I'm very interested in O(n2)Alog,could you send me your code to wingzero555@hotmail.com for me ? thanks Victor Barinov (TNU) How to speed it? // Задача 1143. Electric Path 30 авг 2005 15:46 Hello everybody! I got AC, but my algo is O(n^3) and it is slow. Who can help me to find algo in O(n^2). I spent much time and best what I can think out is O(n^3). Help me please. Tanks. Bye! Vladimir Yakovlev (USU) Problem 1143 "Electric Path". New tests were added to this problem. All ACs will be rejudged soon (-) // Задача 1143. Electric Path 27 июл 2005 14:13 Fechete Dan Ionut[dany] Why is the answer 50.210?? [2] // Задача 1143. Electric Path 3 фев 2005 01:08 I dont think I've understood the problem. I cant find a path shorter than 55 Could you tell me the right path? Fechete Dan Ionut[dany] Re: Why is the answer 50.210?? [1] // Задача 1143. Electric Path 14 фев 2005 20:59 Got it! Edited by author 14.02.2005 20:59 Edited by author 14.02.2005 21:52 Dilyan No subject // Задача 1143. Electric Path 10 июл 2005 17:22 Edited by author 10.07.2005 17:26 Khramov Egor(9 class) My programm(O(n^2)) and use only 41 kb. // Задача 1143. Electric Path 11 июн 2005 01:57 Edited by author 11.06.2005 02:01 Erwin Yang Greedy Works....... [1] // Задача 1143. Electric Path 27 окт 2004 06:48 Dmitry 'Diman_YES' Kovalioff DP works ;) (-) // Задача 1143. Electric Path 27 окт 2004 13:29 Maigo Akisame (maigoakisame@yahoo.com.cn) DP O(n^2), why wa on test #9? [4] // Задача 1143. Electric Path 4 авг 2004 11:41 [code cut out] Edited by moderator 05.08.2004 00:19 Macarie programatorul in actiune Re: DP O(n^2), why wa on test #9? [1] // Задача 1143. Electric Path 4 авг 2004 16:02 This problem is NP so your DP... There was another one saying it's DP, CO2 I think... People, the Hamiltonian Cycle is NP-Complete I don't know why are you trying to find DPs... Well, in this case, the tests are really stupid so I passed them with back and greedy, but this is not relevant... Maigo Akisame (maigoakisame@yahoo.com.cn) But in this prob the points are the vertices of a convex polygon, and you can prove that the best path doesn't cross itself. So I think DP is feasible. // Задача 1143. Electric Path 4 авг 2004 20:43 Vladimir Yakovlev (USU) My AC is also DP O(n^2) (+) [1] // Задача 1143. Electric Path 5 авг 2004 00:14 Your idea is right but there are some mistakes in your code. I use O(n^2) time and O(n) memory, see http://acm.timus.ru/status.aspx?space=1&pos=654576 Edited by author 05.08.2004 00:16 Maigo Akisame (maigoakisame@yahoo.com.cn) Would you please tell me your e-mail so you can point out my mistakes? And I'm curious how you use only O(n) memory. // Задача 1143. Electric Path 5 авг 2004 10:01 Fu Jieyun It's not very hard to make a O(N^2) algorithm... // Задача 1143. Electric Path 5 апр 2004 18:21 The most important thing here is to understand the problem well. After that all are very easy. I got AC soon after I make clear about the meaning of the problem... tbtbtb91 How to slove it with DP? O(n^3)?? [3] // Задача 1143. Electric Path 4 апр 2004 12:45 mkd Re: How to slove it with DP? O(n^3)?? [2] // Задача 1143. Electric Path 5 апр 2004 00:42 It can be solved in O(n^2) time. tbtbtb Re: How to slove it with DP? O(n^3)?? [1] // Задача 1143. Electric Path 5 апр 2004 10:20 How?? Give me some hints? tbtbtb Re: How to slove it with DP? O(n^3)?? // Задача 1143. Electric Path 5 апр 2004 10:58 Is it right?? for s:=n downto 1 do begin d[s,1,1]:=0; d[s,1,0]:=0; for L:=2 to n+1-s do begin d[s,L,0]:=min(dis(s,s+1)+d[s+1,L-1,0],dis(s,s+L-1)+d[s+1,L-1,1]); d[s,L,1]:=min(dis(s+L-1,s+L-2)+d[s,L-1,1],dis(s+L-1,s)+d[s,L-1,0]); end; end; end; TheBlaNK does this problem want to find minimum spanning tree [3] // Задача 1143. Electric Path 7 мар 2002 01:09 Miguel Angel No,a hamiltonian circuit (-) [2] // Задача 1143. Electric Path 7 мар 2002 03:28 > TheBlaNK i still can't understand this problem but anyway thanx for ur help (again) :) // Задача 1143. Electric Path 7 мар 2002 21:58 > > Tor Myklebust Path, I should think // Задача 1143. Electric Path 15 апр 2003 20:37 > > Alyosha Popovich Isn't this problem NP-complete ? [4] // Задача 1143. Electric Path 6 май 2002 11:42 Miguel Angel Yes it is, just try a simple heuristhic and brute forze when size <=10 [1] // Задача 1143. Electric Path 10 май 2002 00:18 > Alyosha Popovich 10x a lot :) // Задача 1143. Electric Path 12 май 2002 23:49 > > Christopher Moh DP solution for convex polygon... I think [1] // Задача 1143. Electric Path 14 июн 2002 23:56 My accepted solution is DP (for all cases, no brute force search). The basic idea is that because all possible edges satisfy the triangle inequality, the optimal hamiltonian path cannot cross itself. Hence, because of the fact that all the vertices lie on a convex polygon, there is an implicit ordering of the points (what it is, I'll let you think) - lending itself to a tabular method (DP). XueMao Re: DP solution for convex polygon... I think // Задача 1143. Electric Path 22 мар 2003 16:32 I am sorry but I can hardly agree with you . this problem is obviously hamiltonian circuit . And it was proved to be a NP problem.so DP can not solve it .
|