Discussion @ 1143. Electric Path @ Timus Online Judge

DP O(n^2), why wa on test #9?

Posted by Maigo Akisame (maigoakisame@yahoo.com.cn) 4 Aug 2004 11:41

[code cut out]

Edited by moderator 05.08.2004 00:19

Re: DP O(n^2), why wa on test #9?

Posted by Macarie programatorul in actiune 4 Aug 2004 16:02

This problem is NP so your DP...
There was another one saying it's DP, CO2 I think...
People, the Hamiltonian Cycle is NP-Complete I don't know why are you trying to find DPs...
Well, in this case, the tests are really stupid so I passed them with back and greedy, but this is not relevant...

But in this prob the points are the vertices of a convex polygon, and you can prove that the best path doesn't cross itself. So I think DP is feasible.

Posted by Maigo Akisame (maigoakisame@yahoo.com.cn) 4 Aug 2004 20:43

My AC is also DP O(n^2) (+)

Posted by Vladimir Yakovlev (USU) 5 Aug 2004 00:14

Your idea is right but there are some mistakes in your code.

I use O(n^2) time and O(n) memory, see http://acm.timus.ru/status.aspx?space=1&pos=654576

Edited by author 05.08.2004 00:16

Would you please tell me your e-mail so you can point out my mistakes? And I'm curious how you use only O(n) memory.

Posted by Maigo Akisame (maigoakisame@yahoo.com.cn) 5 Aug 2004 10:01

Discussion of Problem 1143. Electric Path