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

Maigo Akisame (maigoakisame@yahoo.com.cn) DP O(n^2), why wa on test #9? [4] // Задача 1143. Electric Path 4 авг 2004 11:41

[code cut out]

Edited by moderator 05.08.2004 00:19

Macarie Re: DP O(n^2), why wa on test #9? [1] // Задача 1143. Electric Path 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...

Maigo Akisame (maigoakisame@yahoo.com.cn) 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. // Задача 1143. Electric Path 4 авг 2004 20:43

Vladimir Yakovlev (USU) My AC is also DP O(n^2) (+) [1] // Задача 1143. Electric Path 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

Maigo Akisame (maigoakisame@yahoo.com.cn) 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. // Задача 1143. Electric Path 5 авг 2004 10:01

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