ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1171. Lost in Space

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")
Posted by Huang Yizheng 26 Dec 2001 11:15
It's not a NP problem, my algorithm is O(n)
Posted by I have answers to all your questions :) 26 Dec 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...
Posted by SPbETU#1 29 Sep 2004 11:51
How to slove in O(n) ???
Posted by tbtbtb 30 Sep 2004 16:34
Re: How to slove in O(n) ???
Posted by Grebnov Ilya[Ivanovo SPU] 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
Re: AC in 0.078. wow!
Posted by Sergey Simonchik, SPbETU#1 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
Could anyone help me speed up my prog?
Posted by Maigo Akisame (maigoakisame@yahoo.com.cn) 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
Got AC in 0.359s. One condition took me as many as SIX days to debug!!!
Posted by Maigo Akisame (maigoakisame@yahoo.com.cn) 30 Oct 2004 15:16
Re: How to slove in O(n) ???
Posted by svr 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
Re: How to slove in O(n) ???
Posted by fjxmyzwd 4 Oct 2011 21:23
But how to deal with the Memory usage limit? thx a lot :)