Обсуждение @ 1171. Lost in Space @ Timus Online Judge

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")

Послано Huang Yizheng 26 дек 2001 11:15

It's not a NP problem, my algorithm is O(n)

Послано I have answers to all your questions :) 26 дек 2001 13:03

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

AC in 0.14 sec is not very hard...

Послано SPbETU#1 29 сен 2004 11:51

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

AC in 0.078

Послано Grebnov Ilya[Ivanovo SPU] 29 сен 2004 20:36

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

How to slove in O(n) ???

Послано tbtbtb 30 сен 2004 16:34

Re: How to slove in O(n) ???

Послано Grebnov Ilya[Ivanovo SPU] 30 сен 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

Re: AC in 0.078. wow!

Послано Sergey Simonchik, SPbETU#1 5 окт 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

Could anyone help me speed up my prog?

Послано Maigo Akisame (maigoakisame@yahoo.com.cn) 24 окт 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

Got AC in 0.359s. One condition took me as many as SIX days to debug!!!

Послано Maigo Akisame (maigoakisame@yahoo.com.cn) 30 окт 2004 15:16

Re: How to slove in O(n) ???

Послано svr 28 июн 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

Re: How to slove in O(n) ???

Послано fjxmyzwd 4 окт 2011 21:23

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

Обсуждение задачи 1171. Lost in Space