| ENG RUS | Timus Online Judge |
Discussion of Problem 1143. Electric PathAdhambek be careful [1] // Problem 1143. Electric Path 16 Nov 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 // Problem 1143. Electric Path 3 Jun 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 // Problem 1143. Electric Path 23 Sep 2011 22:26 Can someone give me some tests? I have a greedy solution. Edric Mao sample // Problem 1143. Electric Path 2 Sep 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] // Problem 1143. Electric Path 19 Oct 2002 18:00 Miguel Angel Isn't the MST, you MUST know TREE<>PATH [2] // Problem 1143. Electric Path 20 Oct 2002 01:55 > WAZZAP And WHAT is the diffrence?... [1] // Problem 1143. Electric Path 30 Dec 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?... // Problem 1143. Electric Path 26 Aug 2010 07:57 OH I see! Koala O(n^3) works... [1] // Problem 1143. Electric Path 27 Nov 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... // Problem 1143. Electric Path 28 Nov 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? // Problem 1143. Electric Path 22 Aug 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] // Problem 1143. Electric Path 1 Feb 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] // Problem 1143. Electric Path 1 Feb 2009 14:49 Just unlucky, I guess ;) Sandro (USU) Test#1 is not a sample test in this problem (-) [2] // Problem 1143. Electric Path 1 Feb 2009 16:00 Team CHANT - The TESTER Re: Test#1 is not a sample test in this problem (-) [1] // Problem 1143. Electric Path 1 Feb 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 (-) // Problem 1143. Electric Path 23 Jul 2009 12:23 Electric Path is a PATH, not TREE ! Edited by author 23.07.2009 12:30 LiWang112358 what is test 14? // Problem 1143. Electric Path 20 Jul 2009 18:49 tjj DP in O(n^2) [3] // Problem 1143. Electric Path 11 Aug 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] // Problem 1143. Electric Path 11 Aug 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) // Problem 1143. Electric Path 12 Aug 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) // Problem 1143. Electric Path 11 Oct 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] // Problem 1143. Electric Path 1 Mar 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] // Problem 1143. Electric Path 1 Mar 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 // Problem 1143. Electric Path 1 Mar 2007 19:11 I've read all the threads about this problem svr Re: why wa#2? please help [12] // Problem 1143. Electric Path 1 Mar 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] // Problem 1143. Electric Path 1 Mar 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] // Problem 1143. Electric Path 2 Mar 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] // Problem 1143. Electric Path 2 Mar 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] // Problem 1143. Electric Path 2 Mar 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 // Problem 1143. Electric Path 2 Mar 2007 14:24 Read previous message Olly Re: why wa#2? please help [6] // Problem 1143. Electric Path 2 Mar 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 // Problem 1143. Electric Path 2 Mar 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] // Problem 1143. Electric Path 2 Mar 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] // Problem 1143. Electric Path 2 Mar 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] // Problem 1143. Electric Path 2 Mar 2007 17:07 Can you send me your code? I'm interested in DP solution svr Re: why wa#2? please help [1] // Problem 1143. Electric Path 2 Mar 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 // Problem 1143. Electric Path 17 Aug 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? // Problem 1143. Electric Path 30 Aug 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 (-) // Problem 1143. Electric Path 27 Jul 2005 14:13 Fechete Dan Ionut[dany] Why is the answer 50.210?? [2] // Problem 1143. Electric Path 3 Feb 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] // Problem 1143. Electric Path 14 Feb 2005 20:59 Got it! Edited by author 14.02.2005 20:59 Edited by author 14.02.2005 21:52 Dilyan No subject // Problem 1143. Electric Path 10 Jul 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. // Problem 1143. Electric Path 11 Jun 2005 01:57 Edited by author 11.06.2005 02:01 Erwin Yang Greedy Works....... [1] // Problem 1143. Electric Path 27 Oct 2004 06:48 Dmitry 'Diman_YES' Kovalioff DP works ;) (-) // Problem 1143. Electric Path 27 Oct 2004 13:29 Maigo Akisame (maigoakisame@yahoo.com.cn) DP O(n^2), why wa on test #9? [4] // Problem 1143. Electric Path 4 Aug 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] // Problem 1143. Electric Path 4 Aug 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. // Problem 1143. Electric Path 4 Aug 2004 20:43 Vladimir Yakovlev (USU) My AC is also DP O(n^2) (+) [1] // Problem 1143. Electric Path 5 Aug 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. // Problem 1143. Electric Path 5 Aug 2004 10:01 Fu Jieyun It's not very hard to make a O(N^2) algorithm... // Problem 1143. Electric Path 5 Apr 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] // Problem 1143. Electric Path 4 Apr 2004 12:45 mkd Re: How to slove it with DP? O(n^3)?? [2] // Problem 1143. Electric Path 5 Apr 2004 00:42 It can be solved in O(n^2) time. tbtbtb Re: How to slove it with DP? O(n^3)?? [1] // Problem 1143. Electric Path 5 Apr 2004 10:20 How?? Give me some hints? tbtbtb Re: How to slove it with DP? O(n^3)?? // Problem 1143. Electric Path 5 Apr 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] // Problem 1143. Electric Path 7 Mar 2002 01:09 Miguel Angel No,a hamiltonian circuit (-) [2] // Problem 1143. Electric Path 7 Mar 2002 03:28 > TheBlaNK i still can't understand this problem but anyway thanx for ur help (again) :) // Problem 1143. Electric Path 7 Mar 2002 21:58 > > Tor Myklebust Path, I should think // Problem 1143. Electric Path 15 Apr 2003 20:37 > > Alyosha Popovich Isn't this problem NP-complete ? [4] // Problem 1143. Electric Path 6 May 2002 11:42 Miguel Angel Yes it is, just try a simple heuristhic and brute forze when size <=10 [1] // Problem 1143. Electric Path 10 May 2002 00:18 > Alyosha Popovich 10x a lot :) // Problem 1143. Electric Path 12 May 2002 23:49 > > Christopher Moh DP solution for convex polygon... I think [1] // Problem 1143. Electric Path 14 Jun 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 // Problem 1143. Electric Path 22 Mar 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 .
|