Обсуждение @ 1143. Electric Path @ Timus Online Judge

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

Послано Maigo Akisame (maigoakisame@yahoo.com.cn) 4 авг 2004 11:41

[code cut out]

Edited by moderator 05.08.2004 00:19

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

Послано Macarie programatorul in actiune 4 авг 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.

Послано Maigo Akisame (maigoakisame@yahoo.com.cn) 4 авг 2004 20:43

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

Послано Vladimir Yakovlev (USU) 5 авг 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.

Послано Maigo Akisame (maigoakisame@yahoo.com.cn) 5 авг 2004 10:01

Обсуждение задачи 1143. Electric Path