Discussion @ 1143. Electric Path @ Timus Online Judge

ConnorChang Question about sample // Problem 1143. Electric Path 28 Apr 2025 05:03

Adhambek be careful [1] // Problem 1143. Electric Path 16 Nov 2015 16:12

Petru Trimbitas WA #14 // Problem 1143. Electric Path 23 Sep 2011 22:26

Edric Mao sample // Problem 1143. Electric Path 2 Sep 2010 16:41

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

Koala O(n^3) works... [1] // Problem 1143. Electric Path 27 Nov 2009 00:04

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

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

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

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

Khramov Egor(9 class) My programm(O(n^2)) and use only 41 kb. // Problem 1143. Electric Path 11 Jun 2005 01:57

Erwin Yang Greedy Works....... [1] // Problem 1143. Electric Path 27 Oct 2004 06:48

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

Fu Jieyun It's not very hard to make a O(N^2) algorithm... // Problem 1143. Electric Path 5 Apr 2004 18:21

tbtbtb91 How to slove it with DP? O(n^3)?? [3] // Problem 1143. Electric Path 4 Apr 2004 12:45

TheBlaNK does this problem want to find minimum spanning tree [3] // Problem 1143. Electric Path 7 Mar 2002 01:09

Discussion of Problem 1143. Electric Path