ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1143. Electric Path

why wa#2? please help
Posted by Olly 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
Re: why wa#2? please help
Posted by svr 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
Re: why wa#2? please help
Posted by Delete 1 Mar 2007 19:11
I've read all the threads about this problem
Re: why wa#2? please help
Posted by svr 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)
Re: why wa#2? please help
Posted by Olly 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
Re: why wa#2? please help
Posted by svr 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.
Re: why wa#2? please help
Posted by svr 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
Re: why wa#2? please help
Posted by svr 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
Re: why wa#2? please help
Posted by svr 2 Mar 2007 14:24
Read previous message
Re: why wa#2? please help
Posted by Olly 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 :(
Re: why wa#2? please help
Posted by svr 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
Re: why wa#2? please help
Posted by Olly 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.
Re: why wa#2? please help
Posted by svr 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
Re: why wa#2? please help
Posted by Olly 2 Mar 2007 17:07
Can you send me your code?
I'm interested in DP solution
Re: why wa#2? please help
Posted by svr 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)
Re: why wa#2? please help
Posted by wingzeroshy 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