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

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