Discussion @ 1143. Electric Path @ Timus Online Judge

DP in O(n^2)

Posted by tjj 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

Re: DP in O(n^2)

Posted by tjj 11 Aug 2006 16:27

Sorry, what I meant was Pi must be connected to Pi-1 or Pi+1 or both of them.

Re: DP in O(n^2)

Posted by Denis Koshman 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

Re: DP in O(n^2)

Posted by SkorKNURE 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

Discussion of Problem 1143. Electric Path