PACMAN help

sriram_gadde · January 9, 2020, 3:33am

can anyone help how to deal with magical points in this problem?
i know that it can be solved using simple dfs and diameter concept without magical points.

code_dad · January 9, 2020, 5:59am

Can u share the approach how to solve without magical points, I don’t know how to solve…
Please share any similar question.
Thanks

sriram_gadde · January 9, 2020, 6:21am

take any random point a and search for the maximum manhattan distance point from that point (say b) … and again search maximum distance point from b (say c) … now lets say distance between b and c is x … our answer will be ceil(x/2);
it takes linear time O(N).
Try this one - CodeChef: Practical coding for everyone

code_dad · January 9, 2020, 6:55am

but in this question there is no point in 2-d.Do you know nay question where 20d point is given and then we find a integer point…
thanks

sriram_gadde · January 9, 2020, 7:13am

idea is same…take maximum distance between any two nodes in graph in all connected components separately…it will be distance between two end points of diameter in each connected component…and take maximum among all connected components

I dont remember any 2d point question

code_dad · January 9, 2020, 7:18am

Thanks for replying and sharing question.