|
|
back to boardXyz,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") It's not a NP problem, my algorithm is O(n) if u want more detail, my email addr is sephiroth_vn@yahoo.com ;) AC in 0.14 sec is not very hard... How to slove in O(n) ??? Posted by tbtbtb 30 Sep 2004 16:34 Re: How to slove in O(n) ??? 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! After optimizing my solution i can't solve it better then in 0.125 sec... http://acm.timus.ru/status.aspx?space=1&pos=698225I think it happened, because i use float numbers and my solution has O(n/precision) complexity :( Edited by author 05.10.2004 18:18Could anyone help me speed up my prog? 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!!! 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) ??? But how to deal with the Memory usage limit? thx a lot :) |
|
|