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:32

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.

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

Read previous message

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