Discussion @ 1695. Work for Robots @ Timus Online Judge

William Chou got tle , need help. [5] // Problem 1695. Work for Robots 11 Apr 2011 10:16

I have tried so many times , but i have no idea to avoid tle.
I use memory search to solve it , and get tle on #58.
Although i use random method when i choose a node , but it doesn't work.
I just know that somebody have accepted this problem use the same method one years ago.
Maybe he also get tle after rejudged.
e...I think this is a NP problem.
Could anybody help me?
Thank you!
sorry for my poor English.
ありがとうございます。

William Chou Re: got tle , need help. [4] // Problem 1695. Work for Robots 11 Apr 2011 10:22

I use C++ stl map to save information.
And it's a Red-Black Tree(O(logn)).
Will it be faster if i use hash(O(1)) instead of map?
If anybody know how to solve it , please tell me.
Here is my e-mail : 419481620@qq.com.

William Chou Re: got tle , need help. [3] // Problem 1695. Work for Robots 11 Apr 2011 13:11

I also have tried to use hash instead of map to save information.
But still tle #58.
Here is my code.
After i accept , i will delete my code (if i could get accept , and i wish so , haha...).
[code deleted].

Edited by author 13.04.2011 08:22

William Chou Re: got tle , need help. [2] // Problem 1695. Work for Robots 12 Apr 2011 08:06

Oh ! after i use a new way to random , i got tle #69 now.
faint.

svr Re: got tle , need help. [1] // Problem 1695. Work for Robots 12 Apr 2011 08:47

I think that jury has some ideas for quick algo without random absolutely.
Try to find mathematical ways to speed up.

William Chou Re: got tle , need help. // Problem 1695. Work for Robots 13 Apr 2011 08:25

Oh ! I got AC now.
Just a little Optimization.

Discussion of Problem 1695. Work for Robots