Discussion @ 1171. Lost in Space @ Timus Online Judge

Huang Yizheng Xyz,you're excellent,how can you solve this problem in only 0.25sec,300K memory.Can you help me?I find it's a NP problem.(email:"hyz12345678@163.com") [10] // Problem 1171. Lost in Space 26 Dec 2001 11:15

I have answers to all your questions :) It's not a NP problem, my algorithm is O(n) // Problem 1171. Lost in Space 26 Dec 2001 13:03

if u want more detail, my email addr is sephiroth_vn@yahoo.com ;)

SPbETU#1 AC in 0.14 sec is not very hard... [8] // Problem 1171. Lost in Space 29 Sep 2004 11:51

http://acm.timus.ru/status.aspx?space=1&pos=692129

Grebnov Ilya[Ivanovo SPU] AC in 0.078 [7] // Problem 1171. Lost in Space 29 Sep 2004 20:36

http://acm.timus.ru/status.aspx?space=1&pos=692481

tbtbtb How to slove in O(n) ??? [5] // Problem 1171. Lost in Space 30 Sep 2004 16:34

Grebnov Ilya[Ivanovo SPU] Re: How to slove in O(n) ??? [4] // Problem 1171. Lost in Space 30 Sep 2004 20:31

Use DP.

Food[Level][Day][X][Y] = Some Function (Food[Level - 1][Some Day][Some X][Some Y]).

Result = Maximum (Food[N][Some Day][X][Y]/(Some Day + 1)).

Updating of Food[Level][Day][X][Y] can be done by const time, so computing of Food[N][Day][X][Y] can be done by O(N).

Edited by author 30.09.2004 20:32

Edited by author 30.09.2004 20:37

Maigo Akisame (maigoakisame@yahoo.com.cn) Could anyone help me speed up my prog? [1] // Problem 1171. Lost in Space 24 Oct 2004 19:14

The procedure 'search' is extremely slow. But I don't think I can either reduce the quantity of searching or reduce the quantity of updating in the 'update' procedure. I need your help!

[censored]

Edited by moderator 02.11.2004 12:41

Maigo Akisame (maigoakisame@yahoo.com.cn) Got AC in 0.359s. One condition took me as many as SIX days to debug!!! // Problem 1171. Lost in Space 30 Oct 2004 15:16

svr Re: How to slove in O(n) ??? // Problem 1171. Lost in Space 28 Jun 2007 20:36

Helpful recommendation!
But to convert to Ac-program it taken 6 hours!
Have rather bad time 0.5c.
But I have reserve of optimization:
precalcular finding all simple paths in one Layer.
Now i repeate it on each level using stack-search

Edited by author 28.06.2007 20:37

Edited by author 28.06.2007 20:37

fjxmyzwd Re: How to slove in O(n) ??? // Problem 1171. Lost in Space 4 Oct 2011 21:23

But how to deal with the Memory usage limit? thx a lot :)

Sergey Simonchik, SPbETU#1 Re: AC in 0.078. wow! // Problem 1171. Lost in Space 5 Oct 2004 17:59

After optimizing my solution i can't solve it better then in 0.125 sec...
http://acm.timus.ru/status.aspx?space=1&pos=698225
I think it happened, because i use float numbers and my solution has O(n/precision) complexity :(

Edited by author 05.10.2004 18:18

Discussion of Problem 1171. Lost in Space