forget_it's blog

Please Help in following problem.
By forget_it, history, 5 years ago, In English

please help me in following problem , i tried to read its analysis ,but was unable to understand its optimised solution . I looked for various people solution ,they had used bfs, but i am unable to interpret that too.

Just give me the way ,through which i should approach this problem .

Google Kickstart 2019 round A . Problem 2

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it is clear till the binary search part (if not then do let me know).

For now, I'll explain how to check if it is possible to assign a new delivery office such that the max distance to a cell from the closest delivery cell is reduced to upto k.

Notice that |a|+|b| = max(|a+b|,|a-b|), where |x| = abs(x) = absolute value of x

Therefore, manhattan_distance = |x1-x2|+|y1-y2| = max(|x1-x2 + y1-y2|,|x1-x2-(y1-y2)|) 

= max(|(x1+y1)-(x2+y2)|, |(x1-y1)-(x2-y2)|)

Now, if you fix a cell as a delivery office, say (x2,y2) is fixed, you just need to find the maximum distance to a cell. Now think how can you maximize the above expression when (x2,y2) is fixed. Only when you either maximize or minimize (x1+y1) or (x1-y1) (In total 4 cases). So, precalculate the 4 cells (which do not have a delivery office and the initial distance to a delivery cell is greater than k) which satisfy either of the 4 above cases. Now for each cell as a new delivery office, calculate the distance from this cell to the 4 cells (precalculated) and take the maximum distance.

Check if this maximum distance is less than k or not.

→ Reply