| Show all threads Hide all threads Show all messages Hide all messages | | be careful | Adhambek | 1143. Electric Path | 3 Jun 2021 20:26 | 2 | 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. 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) | | WA #14 | Petru Trimbitas | 1143. Electric Path | 23 Sep 2011 22:26 | 1 | WA #14 Petru Trimbitas 23 Sep 2011 22:26 Can someone give me some tests? I have a greedy solution. | | sample | Edric Mao | 1143. Electric Path | 2 Sep 2010 16:41 | 1 | sample Edric Mao 2 Sep 2010 16:41 can you explain the sample for me
Thx | | I'm really mad of solving this problem... Why the minimal spanning tree doesn't work? And what is the right solution? (-) | WAZZAP | 1143. Electric Path | 26 Aug 2010 07:57 | 4 | 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?) | | O(n^3) works... | Koala | 1143. Electric Path | 28 Nov 2009 14:50 | 2 | my O(n^3) dp got accepted in 0.89sec, though i used an O(n^2) algorithm later and ran much faster. 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. | | i use O(n^3) algorthm?, but my program always WA 11, What is test 11? | xurshid_n | 1143. Electric Path | 22 Aug 2009 16:05 | 1 | | | To Admin : Why my program has WA 1 ? I tried the sample by myself it always gave the same answer as in sample | Team CHANT - The TESTER | 1143. Electric Path | 23 Jul 2009 12:23 | 5 | 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 ! Electric Path is a PATH, not TREE !
Edited by author 23.07.2009 12:30 | | what is test 14? | LiWang112358 | 1143. Electric Path | 20 Jul 2009 18:49 | 1 | | | DP in O(n^2) | tjj | 1143. Electric Path | 11 Oct 2008 17:43 | 4 | 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 Sorry, what I meant was Pi must be connected to Pi-1 or Pi+1 or both of them. 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 | | why wa#2? please help | Olly | 1143. Electric Path | 17 Aug 2007 13:07 | 16 | 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 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 I've read all the threads about this problem 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) 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:32Now 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. 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
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 my program gives the same answer to your test - 6.243
I don't see any mistakes in my algo :( 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 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. 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 Can you send me your code?
I'm interested in DP solution 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) 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 | | How to speed it? | Victor Barinov (TNU) | 1143. Electric Path | 30 Aug 2005 15:46 | 1 | 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! | | Problem 1143 "Electric Path". New tests were added to this problem. All ACs will be rejudged soon (-) | Vladimir Yakovlev (USU) | 1143. Electric Path | 27 Jul 2005 14:13 | 1 | | | Why is the answer 50.210?? | Fechete Dan Ionut[dany] | 1143. Electric Path | 10 Jul 2005 17:22 | 3 | I dont think I've understood the problem.
I cant find a path shorter than 55
Could you tell me the right path? Got it!
Edited by author 14.02.2005 20:59
Edited by author 14.02.2005 21:52
Edited by author 10.07.2005 17:26 | | My programm(O(n^2)) and use only 41 kb. | Khramov Egor(9 class) | 1143. Electric Path | 11 Jun 2005 01:57 | 1 |
Edited by author 11.06.2005 02:01 | | Greedy Works....... | Erwin Yang | 1143. Electric Path | 27 Oct 2004 13:29 | 2 | | | DP O(n^2), why wa on test #9? | Maigo Akisame (maigoakisame@yahoo.com.cn) | 1143. Electric Path | 5 Aug 2004 10:01 | 5 | [code cut out]
Edited by moderator 05.08.2004 00:19 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... | | It's not very hard to make a O(N^2) algorithm... | Fu Jieyun | 1143. Electric Path | 5 Apr 2004 18:21 | 1 | 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...
| | How to slove it with DP? O(n^3)?? | tbtbtb91 | 1143. Electric Path | 5 Apr 2004 10:58 | 4 | It can be solved in O(n^2) time. How?? Give me some hints? 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; | | does this problem want to find minimum spanning tree | TheBlaNK | 1143. Electric Path | 15 Apr 2003 20:37 | 4 | | | Isn't this problem NP-complete ? | Alyosha Popovich | 1143. Electric Path | 22 Mar 2003 16:32 | 5 | 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). 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 . |
|
|
